8/1 解いた問題 - yamake's blog

解説ACです。解説の解法が鮮やかすぎて感動しました。

こういう問題を解けるようになりたいです。

解説に移ります。

$1, ..., N$ 番目のロボットを順番に1マスずつ開けて再配置することを考えます。

ロボットを1マス間隔で配置できている間は、配置された全てのロボットは任意のタイミングでゴールできます。

ロボットが2マス連続になってしまった瞬間について考えましょう。

このとき、後ろに配置される予定の任意のロボットは既に配置されたロボットが少なくとも一体ゴールしない限りゴールできません。

逆にこのとき既に配置されている任意のロボットは次にゴールすることができます。

ロボットが一体ゴールすると、既に配置されたロボットたちを整理することで1マス間隔にできます。

ロボットが2マス連なるたびに同じ操作を繰り返していきます。

全ての操作が終わったときに1マス間隔で配置されたロボットが残り、これらのロボットは任意の順番でゴールできます。

従って、ロボットをstackなどに入れておき

2マス連なるたびに答えに $stack.size()$ を乗じ、

操作終了後の答えに $stack.size()!$ を乗じることで数え上げることができます。

そして、えでゅふぉ79のバチャとAtCoder Problemsのバチャをしました。