ARC 007 (virtual) 解法

コンテストページ

AtCoder Regular Contest 007 - AtCoder

解法

✔A - 帰ってきた器物損壊！高橋君

s を前から順に見ていって、毎回 std::find をすればよいです。

✔B - 迷子のCDケース

今聞いているものが CD ケース 0 に入っているとして、CD ケースを添え字、CD を値とする配列で管理です。次に聞きたい CD を毎回 std::find で探して swap です。

✔C - 節約生活

時刻 0 から N - 1 まで、それぞれテレビをつけ始めるかどうかを決めます。このパターンは 2 の N 乗個ですから、全探索です。

✖D - 破れた宿題

ポイントは、「どんな初項を選んだとしても、第 2 項に巨大を持ってくればオーバーキルできますから、初項は好きなだけ小さくして良いです」です。

まず、もともと 0 しかない場合は例外です。また、先頭が 0 の場合は頭に 1 をつけておきます。すると、初項は初めの数字に 0 をたくさんつけたものです。

さて、異常場合分けコーナーの始まりです（泣）パターンは大きく 2 つあって、 - 第 2 項が欠けていない - 全部で 2 項しかないの 2 通りです。（ただし排他的な場合わけではありません。）

第 2 項が欠けていない場合

こちらのほうが簡単で、第 2 項の桁数を全探索です。初項の選び方から、第 2 項は必ずパースできるのでします。すると第 3 項以降は次に来てほしいものがわかるので、それを期待しながらパースをして、最後に到達したら勝ちです。

全部で 2 項しかない場合

第 2 項として、もとの文字列の最後までをパースして、初項より大きいかどうかを見てみます。大きければこれで良いです。大きくなければ、後ろに 000.... をつけましょう。

怪しい場合として、a0 = 2384, a1 = 23 のときに、これだと 23000 になってしまい、答えである 2385 とは違ってしまします。これを恐れて私は a1 が a0 の proper prefix でかつ後ろのほうが 999... でない場合に特別処理をしたのですが、よく考えたら a0 は 1 桁の数の後ろに 0000... をつけただけですから、この分岐は不要です。