AtCoder Beginner Contest 136 D - Gathering Children

私の解法をTwitterに流したらわりと好評だったので記事にまとめておきます。

解法

ある程度動きをシミュレーションしてみると、十分に時間が経った後は全ての子供が RL の2マスで振動するということが分かります。最終状態を求めるためには動きが止まってくれると考えやすいのですが、振動する動きをそのまま扱うと少し面倒です。これを扱いやすくするために、移動2ターンをセットで考えてみることにしましょう。

2ターンをセットで考えると子供の動きは以下の3パターンに分類されます。

自分が R で右隣も R：2ターンで右に2マス動く。
自分が L で左隣も L：2ターンで左に2マス動く。
それ以外：振動するので、2ターン単位で見ると動かないとみなせる。

ここで、例えば2マス右に動いた子供が次の2ターンも2マス右に動くことはあり得ます。しかし2マス右に動いた子供が次の2ターンで左に2マス動くことはありません。2マス右に動いた後に左隣にあるのは必ず R なので、2マス左に動く条件を満たさないからです。全く同様の理由で「左2→左2」はあり得ますが「左2→右2」はあり得ません。

よって、右に動く子供と左に動く子供は独立に考えることができます。具体的には、