D - Happy Birthday! 2 Editorial by kzrnm
\(dp_k (0 \le k \lt 200)\) を各要素の合計を \(200\) で割った余りが \(k\) となる数列と定義します。 初期状態では\(dp_k = ∅\) です。
\(A\) の各要素 \(A_i (1 \le i \le N)\)で次の判定をしながら順に見ていきます。
\(A_i\) を \(200\) で割った余りを\(r\)とします。
\(dp_r \ne ∅\) の場合
\[B = dp_r\]
\[C = (i)\]
として判定を終了します。
\(dp_r = ∅\) の場合
まず、\(dp_r = ( i )\) として更新します。
次の条件を満たす\(j\)について考えます。
- \(0 \le j < 200\)
- \(dp_j \ne ∅\)
- \(dp_jの最後の要素 \ne i\) (重複して追加してしまうのを防ぐため)
加えて、以下のように変数を定義します。
- \(j+r\)を\(200\)で割った余りを\(q\)とします。
- \(dp_j\) の後ろに \(i\) を追加した数列を\(X\)とします。
つまり、\(X = (dp_{j,1}, \dots, dp_{j, len(dp_j)}, i)\) です。
\(dp_q \ne ∅\) の場合
\[B = dp_q\]
\[C = X\]
として判定を終了します。
\(dp_q = ∅\) の場合
\(dp_q = X\)と更新します。
すべての要素を確認しても \(B, C\)が確定できなければ答えはNo
になります。
計算量については、公式解説にあるとおり \(N>8\) で必ず終了するため最大でも\(200 \times 200 \times 8=320000\)回程度、 判定を途中で終了しない場合でも \(200 \times 200 \times N\) 回程度なので十分間に合います。
posted:
last update: