algoNote

プログラミング関連

Codeforces Round #380 Div2 C.Road to Chinema

codeforces.com

問題概要

$n$台の車についてコスト($c_i$)と燃料の容量($v_i$)が与えられる。
$s$kmを$t$分以内に走ることの出来る車の中でコストの最小値を求めたい。
ただし、途中$k$箇所($g_i$km地点)では燃料の補給が自由に行える。(何回でも)
また、いずれの車も次の2つのモードがあり自由に切り替えて走ることが出来る。

  • normalモード : 1kmを2分、燃料1L消費
  • acceleratedモード : 1kmを1分、燃料2L消費

制約

  • $ 1 \leq n \leq 2 \cdot 10^{5} $
  • $ 1 \leq k \leq 2 \cdot 10^{5} $
  • $ 1 \leq s \leq 10^{9} $
  • $ 1 \leq t \leq 2 \cdot 10^{9} $
  • $ 1 \leq c_i,v_i \leq 10^{9} $

全探索

まず全探索を考えてみる。

$i$台目の車について$s$kmを$t$分以内に完走できるか判定して、完走出来た車の中で最小のコストを求めればよい。
できるだけ早く走った時の時間について考えればよいから、各補給場所の区間を余裕があるだけacceleratedモードで走った時の時間を考える。
すると、以下によって容量$v$の車が最短何分で走りきれるかを求められる。

各燃料補給地点の間の距離を$d$とする。

  1. $v < d$ のとき
    すべてnormalモードで走っても$d$の区間を走ることができないため容量$v$では完走不可能。

  2. $d \leq v < d \cdot 2$ のとき
    $v-d$の燃料の分だけacceleratedモードで走ると、$d$の区間をすべてnormalモードで走ったときから$v-d$分だけ短縮できる。よってこの区間を$d \cdot 2-(v-d)$分で走ることが出来る。

  3. $d \cdot 2 < v$ のとき
    すべてacceleratedモードで走ることが出来るので、この区間を$d$分で走ることが出来る。

すべての区間の最短時間の和が、その車が完走できる最短時間となる。

この全探索の計算量は$O(nk)$となり間に合わない。

二分探索

よく考えてみると、$s$kmを$t$分で完走するために必要な最小容量$v_{min}$が分かればよいことに気付く。(なぜなら$v_{min}$が求まれば$v_{min}$以上の車についてO(n)で最小コストを求められるから。)

そこで$v_{min}$を二分探索によって求める。
具体的には全探索で考えたようにすべての補給場所の区間について最速で走ったときに$t$分以内に完走できるか調べて行けばよい。

二分探索することで$O(k + n)$で解くことが出来る。(二分探索の定数倍(約30倍)に注意)

ソースコード(c++)

gに0とsを加えて扱いやすくしています。

#include <bits/stdc++.h>
using namespace std;
#define int long long
using ll=long long;
using vi=vector<int>;
using vl=vector<long long>;
using pii=pair<int,int>;
using pll=pair<ll,ll>;
#define ITR(v,c) for(auto v=begin(c);v!=end(c);++v)
#define FORE(x,c) for(auto &x:c)
#define FOR(v,a,n) for(int v=a;v<(int)(n);++v)
#define REP(v,n) FOR(v,0,n)
#define RREP(v,n) for(int v=((int)(n)-1);v>=0;--v)
#define ALL(c) begin(c),end(c)
#define RALL(c) rbegin(c),rend(c)
#define SZ(c) ((int)c.size())
#define dump(...)
const int DX[9]={0,1,0,-1,1,1,-1,-1,0}, DY[9]={-1,0,1,0,-1,1,1,-1,0};
const int INF=1e9; const long long INFLL=1e18;
template<class T> ostream& operator << (ostream &os, const vector<T> &v) {
    ITR(i,v) os<<*i<<(i==end(v)-1?"":" "); return os; }
template<class T> istream& operator >> (istream &is, vector<T> &v) {
    ITR(i,v) is>>*i; return is; }
//------------------------------------------------------------------------------

signed main() {
    // 入出力を高速化しないとTLEしたので注意
    cin.tie(0);
    ios::sync_with_stdio(false);

    ll n,k,s,t;
    cin>>n>>k>>s>>t;
    vl c(n),v(n),g(k+2);
    REP(i,n) {
        cin>>c[i]>>v[i];
    }
    REP(i,k) cin>>g[i+1];
    g[0]=0;
    g[k+1]=s;
    sort(ALL(g));

    ll left=0,right=1e9,med,pre=INFLL;
    while(true) {
        med=(left+right)/2;

        ll time=0;
        REP(i,k+1) {
            ll d=g[i+1]-g[i];
            if(d>med) {
                time=INFLL;
                break;
            }
            else if(d<=med && med<d*2) time+=d*2-(med-d);
            else if(d*2<=med) time+=d;
        }

        if(time<=t) {
            if(right==med) break;
            pre=med;
            right=med;
        }
        else {
            if(left==med+1) break;
            left=med+1;
        }
    }
    med=pre;

    ll ans=INF+1;
    REP(i,n) {
        if(med<=v[i]) ans=min(ans,c[i]);
    }
    cout<<(ans==INF+1?-1:ans)<<endl;
    return 0;
}

コンテスト中に解けなかったのは反省するべきですね…(二分探索が思いつかなかった)