【CODE FESTIVAL 2015】D - 壊れた電車【予選A】

問題概要

それぞれX_i両目の車両にいるM人の整備士が、N両編成の電車をすべて点検し終えるのに最短で何分かかるか求めよ。但し、点検には時間はかからないが、隣の車両に移動するのには1分かかるものとする。

制約

• 1 <= N <= 10⁹
• 1 <= M <= 10⁵
• M <= N
• 1 <= X_i <= N

考察

方針

求める値をansとして、ansを0,1,2...と地道に増やしていくのだと、それだけでO(N)だから間に合わなさそう。

→ ansを二分探索すれば、そこはO(logN)くらいで収められる

点検できるかの判定

左(車両番号の小さい方)の整備士から順に点検していくとして、最終的な位置がなるべく右にあった方がうれしい。l両目まで点検済みで、c両目にいる整備士がt分点検するとする。

• c <= l のとき、整備士はc+t両目まで点検できるため、l=max(l,c+t)
• そうでないなら、左を経由して右に進む場合と、右を経由して左に進む場合をそれぞれ考えて、より右に進んだ方を選べばよい。但し、最終位置の左側に点検し残した部分がある場合、すなわちc-(l+1)>tのとき、すべて点検し終えることは絶対にできないので省く。

左を経由して右に進む場合、(c)→(l+1)→(r)と移動するため、(c-(l+1))+(r-(l+1))=t、整理してr=t-c+2(l+1)

右を経由して左に進む場合、(c)→(r)→(l+1)と移動するため、(r-c)+(r-(l+1))=t、整理してr=(t+c+l+1)/2

ゆえに、l=max(t-c+2(l+1), (t+c+l+1)/2)

この操作をすべてのcに対して行い、最終的にl>=N-1となれば点検が完了していると分かる。

点検部分は多分O(M)なので、合わせてO(MlogN)だから間に合いそう！

ACコード(C++🔆)

#define reps(i,a,b) for(int (i)=(a); (i)<(b); ++(i))
#define rep(i,n) reps(i,0,(n))
#define chmax(x,y) x=max(x,y)
#define P(p) cout << (p) << endl;

ll N,M,X[100100];

bool tenken(ll minute) {
  ll left = -1;
  rep(i,M) {
    ll c = X[i]-1;
    if (c <= left) {
      chmax(left,c+minute);
    } else {
      if (c-left-1 > minute) return false;
      ll r1 = minute - c + 2 * (left+1);
      ll r2 = (minute + c + left + 1) / 2;
      chmax(left,max(r1,r2));
    }
  }
  return left>=N-1;
}

signed main() {
  cin >> N >> M;
  rep(i,M) cin >> X[i];
  ll low = 0, high = 2 * N;
  while (low<=high) {
    ll mid = (low + high) / 2;
    if (tenken(mid)) {
      high = mid - 1;
    } else {
      low = mid + 1;
    }
  }
  P(low);
}

https://beta.atcoder.jp/contests/code-festival-2015-quala/submissions/3062027