Mujin 2017 A. Robot Racing

atcoder.jp

考察

• 2つ前までしか移動できないので、ロボットが2つ連続で並んでいる箇所があると自由にゴールさせられない。
• 逆にいうとそういう箇所がなければ任意の順でゴールさせられる。
• あるロボットに着目し、前にあるロボットをいくつゴールさせれば自分がゴールできるか考えてみる。とりあえず最初にゴールさせられるかどうかで考える。

• ロボットより後ろのロボットをわざわざ動かす必要はない。それより前にあるロボットを2つ連続しないように動かすことができれば最初にゴールさせられる。

• 直感的に前が詰まり過ぎていると、連続を回避しようと前へ前へと動かすが最終的に座標1に近いあたりで頓挫することがわかる。

• こうならない必要条件としては、前に個ロボットがいるなら各についてが挙げられる。これは、最終的に座標1から一つおきに並んでいるギリギリの状態になったとするとそれぞれのロボットはその最終位置よりも右側にある、という条件である。

• ここでこの条件が成り立っていると仮定すると、前から順に最終位置にそろえていくことで必ず着目しているロボットを最初にゴールさせられることがわかる。

• ここまでくると各ロボットについて前のロボット達を最低何個ゴールさせなければならないか？を考えたくなる。ここで"最低"と言ったがある個をゴールさせれて着目しているロボットをゴールさせられるならば、どの個をゴールさせても適切に前に詰めることでロボットをゴールさせられることがわかる。

• 一つも動かさなくてよい場合と同様に考える。1つのロボットをゴールさせられると直感的に2マス分の余裕が生まれる。したがって、前に個ロボットがいるなら個くらい取り除く必要がある予想できる。

• 帰納法でいい感じに示せそう(雑)ということまで確認して実装するとACした。なおこの値の計算は累積maxでやるとになり、これが計算できれば順列の数の計算は簡単な掛け算でできる。

感想

• 限界の状態を考えて条件の定式化、必要条件⇒実は十分の流れがちゃんと導けたので良かった(結構苦手なタイプ)
• ただもう少しスムーズに解きたかった。
• 解説では初めにゴールさせられるか、の考察からstackを使った解法に至っていたが、実質的に上の予想を利用している(スタックの番目が以上だったら...の部分)

Submission

void solve() {
  int N;
  cin >> N;
  vector<int> x(N);
  for (int i = 0; i < N; i++) { cin >> x[i]; }
  vector<int> c(N, -1);
  c[0] = c[1] = 0;
  vector<int> cnt(N + 1, 0);
  cnt[0] = 2;
  for (int i = 2; i < N; i++) {
    int expected = 2 * i - 1;
    c[i] = max(c[i - 1], (expected - x[i - 1] + 1) / 2);
    cnt[c[i]]++;
  }
  for (int i = 1; i <= N; i++) cnt[i] += cnt[i - 1];
  mint ans(1);
  for (int i = 0; i <= N; i++) {
    if (cnt[i] - i <= 0) break;
    ans *= mint(cnt[i] - i);
  }
  cout << ans << endl; 
  return;
}