競プロ参戦記 #38 Reversi | AGC 31

久しぶりの AGC でしたが、参加しなかったので参戦記ではなく練習記です。

2時間測ってやってみたところ、ぎりぎりB完 + ペナルティ35分なので950位ぐらいでした。(コンテスト時間は160分ですが、いましがたまで120分だと思いこんでいました。)

競プロ参戦記

この連載記事では、着手した問題の考察を自分なりに書いていきます。

• 問題の詳細はリンク先を参照してください。
• 前回: 競プロ参戦記 #37 Skyscrapers | CR #545 Div.2 - Qiita

AtCoder Grand Contest 031

• 問題一覧: https://atcoder.jp/contests/agc031/tasks

A - Colorful Subsequence

問題概要: 長さ N の文字列 S が与えられる。S の空でない部分列 (区間でなくても可) のうち、文字が重複していないものの個数を mod P で求めよ。(P = 10^9 + 7)

考察:

重複がないという条件を考えると、どの文字を選んだかを記録しなければいけなくて状態数が爆発してしまいます (※誤り)。そのため、重複がある部分列を数えて部分列の総数 (2^N - 1) から引く方向で考えました。

具体例を試しているうちに、文字列はソートしていいことに気づきました。部分列中の文字の順番は「重複があるか」という条件に影響しないからです。

そのため部分列を考える代わりに「各文字種につき、それを何個使うか」を考えればいいです。特に、「2個以上使う」ケースはすべて同様なので掛け算で求まります。

また、各文字種を何個使うかではなく、重複があるかだけを状態に持っておけばいいので、全体としての状態数は O(N) に収まります。そのため、メモ化再帰によって解くことができます。

具体的にはこうです。状態 (i, dup) の意味を、文字種 0..i をそれぞれ何個使うかがすでに決まっていて、少なくとも1種類の文字を2個以上使っているときに dup = true であるということにして、このときの場合の数を dfs(i, dup) と表すことにします。

次の文字種 i を 0 個使うときは dfs(i + 1, dup) 通りです。1 個使うときは、その文字の個数を a とするとき、それをどの位置からとるかの選択肢があって a * dfs(i + 1, dup) 通りになります。2個以上使うときは、文字の選びかたの組み合わせが 2^a - (a + 1) 通りあって、重複が確定するので (2^a - a -1) * dfs(i + 1, true) 通りです。この和が答え。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/agc031/submissions/4606575

反省:

文字列をソートしていいことに気づくのが遅くて、最初の「重複を数える」方針に入り込みすぎていたようです。

公式の解説の解法はもっとスマートです。

メモ化するのを忘れて TLE を1回出しました。

B - Reversi

問題概要: N 個の石が一列に並んでいる。左から i 個目の石の色は C[i] である。以下の操作を好きな回数だけ繰り返すとき、最終的な石の色の列としてありえるものの個数を mod P で数えよ。

操作: 同じ色の石を2つ選び、その間にあるすべての石の色を選ばれた石と同じ色にする。

考察:

1, 2, 1, 1 のように並んでいるとき、左の3つに対して操作をするのと4つ全体に対して操作をするのでは結果が同じなので、必ず4つ全体で操作することにします。

これは操作範囲を決めるときに両隣に同じ色の石があるかどうかを見て範囲を広げればいいです。

また、区間が重複するような操作は行わないようにしていいです。

こうすると、区間を「石が1つの区間」と「操作によって同色化された区間」の列に分解できます。この列の個数を数えればいいです。

これは DP によってできます。dp[i] を「区間 0..i に対して行う操作がすべて決まっていて、区間i..N については全く操作が行われていない状態」における場合の数とおきます。

また、石 i と同じ色の次の石の位置を next[i] とします。(上述の理由で同じ色が連続しているときは next[i] はその最後尾にします。)

遷移を考えると、操作を行わないケースでの解は dp[i + 1] で、操作を行うケースでは dp[next[i] + 1], dp[next[next[i]] + 1], etc. の総和です。(この総和を実際にループで計算すると TLE したので、メモをとって省略する必要があります。)

初期状態 dp[N] = 1 から後ろ向きに遷移していけば最終的に dp[0] が答えとなります。

筆者の回答 (Rust, AC): https://atcoder.jp/contests/agc031/submissions/4611130

反省:

考察はスムーズに進んだんですが、実装中に3種類のランタイムエラーを起こしてパニックになりました。

• 余りを取るのを忘れてオーバーフロー
• メモ化再帰で書いてスタックオーバーフロー
• 石の色の番号が N (石の個数) を超えないと思い込んでいて、配列の長さが足りなくて範囲外エラー

落ち着こう……

今回の教訓

• A: 与えられた列をソートしたら楽になるかも
• B: 何かを数えるときは数えるものと 1:1 に対応するものを頑張って探して、それを代わりに数えるといいかも
• B: 原因が分からない RE が出たときは再現ケースを作るといいかも