AGC026 参加記録
AtCoder Grand Contest 026 - AtCoder
結果は69分台3完で182位でした。パフォーマンスも2327、過去最高なので上出来です。
1100点はまあ解けないので、欲を言えば600点問題の考察をもう少し速く詰められるようになりたいですね。
解けたA～Cを振り返っていきます。
A - Colorful Slimes 2
番号の小さいほうから見ていって、色が一致している場合は「後のほうの」スライムの色を適当に変更します。前のスライムは既に両隣チェックされていますが、後のスライムはさらにその後のスライムとの比較が残っているため、こちらを変えたほうが得です。
適当にと書きましたが、実際にはさらにその後のスライムと違う色なら何でも良いです。実装上は -1 とかを代入してしまうといいと思います。
ACコード：Submission #2841191 - AtCoder Grand Contest 026
ちなみに例題情報です。同じ考え方が使えます。
B - rng_10s
クエリを処理する問題ですが、クエリごとの関連性が薄いのと、クエリが300個しかないのもあって、「前計算をしてクエリを高速に処理する」タイプではないです。1つ1つクエリを処理していきます。
まず、いくつか必敗パターンがあります。
のとき、1日目にジュースを買えない。
のとき、買われる量より補充量が少ないので、いつか必ず不足する。
これらに対しては No を出力してそのクエリを即終了します。以降、これらではない場合を考えます。
気になるのは、「ジュースの残り本数としてあり得る値のうち、補充されない（すなわち、 より大きい）範囲で最も少ないのはいくつか？」です。これが
以上であれば、ジュースを永遠に買い続けられます。
例えばサンプル1の2行目、クエリが の場合。
| 買われる前 | 買われた後 | 補充後 |
|---|---|---|
| 9 | 2 | 11 |
| 11 | 4 | 13 |
| 13 | 6 | 15 |
| 15 | 8 | (補充なし) |
| 8 | 1 | 10 |
| 10 | 3 | 12 |
| 12 | 5 | 14 |
| 14 | 7 | (補充なし) |
| 7 | 0 | 9 |
これ以降はループします。補充されない範囲で最も少ない残り本数は7です。
例えばこれを、 に置き換えてみましょう。
| 買われる前 | 買われた後 | 補充後 |
|---|---|---|
| 9 | 3 | 12 |
| 12 | 6 | 15 |
| 15 | 9 | (補充なし) |
これでループします。補充されない範囲で最も少ない残り本数は9です。また、買われた後の値は3, 6, 9しか登場しません。
残り本数の変化に注目してみます。「6減らす」と「9増やす」を繰り返したとき、その変動量の和は必ず3の倍数になっているということが分かります。より一般的に言うと、 の最大公約数（
と書きます）の倍数になります。変動量が
の倍数ということは、最初の値
からずっと
で割った余りが変化しないということですね。
対して先程の「7減らす」「9増やす」の例では最大公約数が1なので、残り本数は2, 4, 6, 8, 1, 3, 5, 7, 9, ...と、余りによる制約を受けずに変動しています。
これで方針が立ちました。考えたい条件は、「ジュースの残り本数としてあり得る値のうち、補充されない範囲で最も少ない値は 以上か？」でした。その値は、
この2つを満たす中で最小の となります。後はこれを頑張って求めましょう。
ACコード：Submission #2849231 - AtCoder Grand Contest 026
本番中は最初からクリアな考察ができていたわけではないので、もっと場合分けが細かいコードで通しています。非常に自信が持てなくなるようなコードですが、サンプルがめちゃくちゃ親切だったので助かりました…
C - String Coloring
これは完全に制約からエスパーなんですが…とりあえず制約を見ると なので、
とか
っぽいなーという気がしてきます。
文字くらいなら塗り分け方を全列挙できそうです。
文字列の前半部 個について、どちらの色に塗るか？を固定します。
前半部を塗り分けると、赤の文字列は頭から、青の文字列は反転するので末尾から埋まっていきます。そのため、「その分け方をした時に完成する文字列」がぴったり確定します。
上の図の分け方はつまり、「前半部の分け方であって、赤に2文字使っていて、完成する文字列が caba であるもの」を示します。これと「後半部の分け方であって、赤に2文字使っていて、完成する文字列が caba のもの」を組み合わせることで、条件を満たす分け方となります。
逆に言うと、「赤に何文字使ったか」と「完成する文字列」が一致していれば、それらはまとめて数えてよいです。
解法をまとめると、
- 前半部の分け方を全通り試す。「赤に
文字使っていて、完成する文字列が
であるもの」をそれぞれ数えておく。
- 後半部の分け方を全通り試す。「赤に
文字使っていて、完成する文字列が
これで解けます。こういった解法を「半分全列挙」と言います。
ACコード：Submission #2845141 - AtCoder Grand Contest 026
解説だと計算量が なんですが、2個目の
がどこから来ているのかは分かりません…
さいごに
配点を見た時にこれは3完必須だなあと思っていましたが、結構良い速度で3完できてよかったです。いつか橙パフォを出したいですね。
