ABC 279 G — At Most 2 Colors

考察

新しいマスを塗るとき、調べるのは「そのマスを右端とする窓」に3色目が入るかどうかである。直前の色以外については、最後に現れた位置が分かれば、まだ窓に残っているかを判定できる。そこで色列全体を覚えず、もう一色の最終出現位置ごとに塗り方を数える。

マスを左から順に塗る。直前の KK マスの色列をそのまま状態にすると、候補だけで CKC^K 個あり、N,K≤106N,K\leq 10^6 では扱えない。まず色名を入れ替えても合法かどうかは変わらないと気づきたい。ただし色名を捨てるだけでは、窓内の一致・不一致の並び方を大量に覚えることになる。次に「これから塗れる色を決めるには、過去の何が必要か」を考える。

既に確定した窓が合法なら、次のマスを塗って新しく確認する窓は一つだけである。そこに残る色が1色なら、同じ色と、それ以外の C−1C-1 色を選べる。2色なら、その2色のどちらかしか選べない。色が窓から消えたかどうかは最終出現位置で分かり、直前色の最終位置は必ず直前のマスなので、もう一色の位置だけを持てばよい。

塗り終えた時点の状態

位置は1始まりとする。マス ii まで塗った直後に見る窓を

Wi=[max⁡(1,i−K+1),i]W_i=[\max(1,i-K+1),i]

とする。ここでは両端を含む。i<Ki<K の間は、塗り終えた部分全体を見る。この段階でも3色は許さない。最初の KK マスに必ず含まれるため、3色を使った塗り方は完成形へ延ばせないからである。

合法な塗り方を、WiW_i に現れる色によって次のように分ける。

  • sing: WiW_i が単色である塗り方の個数。
  • dp[p]dp[p]: WiW_i が2色で、直前色とは異なる「もう一色」の最終出現位置が pp である塗り方の個数。有効な添字は max⁡(1,i−K+1)≤p≤i−1\max(1,i-K+1)\leq p\leq i-1。

色名ごとに状態を分けないが、値は具体的な色名を区別した塗り方の個数である。例えば最初のマスには CC 通りあるので、位置1を塗った直後は sing=C\mathrm{sing}=C、配列 dpdp はすべて0とする。

塗る前に期限切れを移し、色を選ぶ

i=2,…,Ni=2,\ldots,N の順にマス ii を塗る。処理の最初は、マス i−1i-1 まで塗った直後の状態である。次の二段階を区別する。

まず、新しい窓に残る既存部分へ範囲を絞る。 新しい窓 WiW_i に入る既存部分は

Vi=[max⁡(1,i−K+1),i−1]V_i=[\max(1,i-K+1),i-1]

であり、長さは高々 K−1K-1 である。もう一色の最終位置が i−Ki-K なら、その色は ViV_i から消える。従って i−K≥1i-K\geq 1 のときだけ

sing←sing+dp[i−K]\mathrm{sing}\leftarrow\mathrm{sing}+dp[i-K]

とする。この直後、sing は まだマス ii を塗っていない列について、ViV_i が単色である個数を表す。塗り終えた時点の Wi−1W_{i-1} の定義から、ここで意味が切り替わる。

例えば K=3K=3 で ABB まで塗り、位置 i=4i=4 に別の色 C を追加する場面を考える(A・B・C は互いに異なる色名)。塗る前の窓 ABB は2色で、A の最終位置は 1=i−K1=i-K。しかし新しい窓に残る既存部分は BB だけなので、この1通りは dp[1]dp[1] から sing に移る。そこから C を選ぶと ABBC となり、二つの窓 ABB・BBC はどちらも合法である。古い窓の2色をそのまま使って「3色目は禁止」とすると、この塗り方を落としてしまう。

次に、マス ii の色を選ぶ。 直前と異なる色を選ぶ遷移は、いずれも新しい dp[i−1]dp[i-1] へまとまる。

  • ViV_i が単色なら、直前色以外を C−1C-1 通りから選べる。旧直前色が「もう一色」になり、その最終位置は i−1i-1 となる。
  • ViV_i が2色なら、もう一色を選ぶ1通りだけが直前と異なる色を使う遷移である。2色の役割が交換され、やはり旧直前色の最終位置 i−1i-1 が新しい状態になる。

従って、期限切れを移した後の sing を使って

dp[i−1]=sing(C−1)+∑p=max⁡(1,i−K+1)i−2dp[p]dp[i-1]=\mathrm{sing}(C-1) +\sum_{p=\max(1,i-K+1)}^{i-2}dp[p]

とする。下端が上端を超える和は0である。

残る選択肢は、直前と同じ色で塗る1通りである。この場合、sing に属する列は単色のまま、既存の dp[p]dp[p] に属する列はもう一色の最終位置が変わらない。既存の sing と有効範囲の dp[p]dp[p] をそのまま残すことが、この1通りの遷移に相当する。 リセットも2倍も不要である。新しい dp[i−1]dp[i-1] はそれまで未使用の添字なので、これらの継続分と衝突しない。

これでマス ii まで塗り終わり、状態は再び WiW_i に対する定義へ戻る。sing は末尾の高々 KK マスが単色の個数であり、列全体が単色である必要はない。期限切れの dpdp の値は配列に残してよいが、有効範囲からは除外する。

区間和を定数時間で求める

上の和を毎回走査すると、全体で O(NK)O(NK) 時間かかる。各 dp[p]dp[p] は一度作った後、同色継続によって数値が変わらないので、作成済みの値の累積和を残せる。

P[0]=0,P[r]=∑p=1rdp[p]P[0]=0,\qquad P[r]=\sum_{p=1}^{r}dp[p]

マス ii を塗る段階では P[i−2]P[i-2] まで既知なので、遷移元の区間和は

∑p=max⁡(1,i−K+1)i−2dp[p]=P[i−2]−P[max⁡(0,i−K)]\sum_{p=\max(1,i-K+1)}^{i-2}dp[p] =P[i-2]-P[\max(0,i-K)]

となる。新しい dp[i−1]dp[i-1] を求めた後に P[i−1]=P[i−2]+dp[i−1]P[i-1]=P[i-2]+dp[i-1] を追加する。期限切れの値も累積和には残るが、差を取ると除かれる。

最後の位置 NN を塗った後は、単色状態と、まだ窓に残る2色状態を足す。

answer=sing+∑p=max⁡(1,N−K+1)N−1dp[p]=sing+P[N−1]−P[max⁡(0,N−K)]\begin{aligned} \mathrm{answer} &=\mathrm{sing}+\sum_{p=\max(1,N-K+1)}^{N-1}dp[p]\\ &=\mathrm{sing}+P[N-1]-P[\max(0,N-K)] \end{aligned}

sing へ移した古い項を、再び答えへ足さないことが大切である。すべての加減乗算は法998244353で行う。

典型の発動条件

色名対称性による状態圧縮

制約が色の一致・不一致だけに依存するなら、色名そのものを状態から外せないか考える。状態をまとめた後も、具体的な色の選び方の数は残す。今回は直前色を続ける1通り、単色状態から異色を選ぶ C−1C-1 通りとして扱う。

last occurrence DP

窓内にある種類が残っているかどうかだけが必要なら、その種類の最終出現位置で判定できる。窓を進めるときは、次の要素を追加する前後のどちらの範囲を見ているかを定める。今回は追加前の末尾 K−1K-1 マスへ範囲を絞り、期限切れを移してから色を選ぶ。

問題固有の要素

窓内の2色のうち一方は必ず直前のマスに現れる。その最終位置は時刻から決まるため、残る一色の最終位置だけを状態にすればよい。さらに、異色を塗るとどの状態からも同じ新しい添字 i−1i-1 へ移るため、遷移元を一つの区間和にまとめられる。

別の問題でも、最終出現位置を複数持ちたくなったら、「現在の要素から自動的に決まる位置はどれか」「更新先が共通する遷移をまとめられるか」を調べる。

正当性

マス i−1i-1 までの塗り方が状態の定義どおりに数えられているとする。マス ii に関わる過去の範囲は ViV_i であり、直前の窓から外れる可能性がある最終出現位置は i−Ki-K だけである。この状態を sing へ移すと、ViV_i が単色の場合と2色の場合に、過去の塗り方を漏れなく重複なく分けられる。

単色の場合には同色1通りと異色 C−1C-1 通り、2色の場合には直前色1通りともう一色1通りが、許される色のすべてである。同色なら状態を保ち、異色なら旧直前色の最終位置 i−1i-1 を持つ新状態へ移る。どちらの場合も、塗り終えた窓 WiW_i の定義と一致する。色名をまとめても、各具体的な列からの選択肢数は同じなので、個数に必要な多重度は失われない。

生成される列は新しい窓の制約を満たし、既に確定した窓も変わらない。逆に、合法な列から末尾1マスを取り除くと遷移元と選んだ色が一意に決まるため、漏れも二重計数もない。i<Ki<K の間に3色を除くことも、それらを含む最初の長さ KK の窓が必ず不合法になるので正しい。初期値は1マスの全 CC 通りを数えており、以上を繰り返すと全合法彩色が数えられる。最後に sing と WNW_N に残る2色状態だけを合計すれば答えとなる。

実装上の注意

  • 添字 i−K<1i-K<1 のときは期限切れの移動を行わない。負添字を読まず、累積和の左側も max⁡(0,i−K)\max(0,i-K) で切り詰める。dp[0]dp[0] を用意する場合は0のままにする。
  • 更新は「期限切れを sing へ加える → 新しい dp[i−1]dp[i-1] を計算する → P[i−1]P[i-1] を作る」の順に行う。旧 dpdp と sing を消すと、同色継続の分を失う。
  • 法を取った累積和の差は負になることがあるので正規化する。C≤109C\leq 10^9 であり、sing と C−1C-1 の乗算には、剰余型または十分な整数幅を使う。
  • K=2K=2 ならどの2マスも高々2色なので、答えは CNC^N。遷移でも既存の2色状態は毎回すべて期限切れとなり、区間和は空になる。移動後の sing が直前までの総数を表すため、同色1通りと異色 C−1C-1 通りで毎回 CC 倍になる。
  • C=1C=1 なら異色遷移はなく、常に sing が1、dpdp が0で答えも1となる。
  • N=KN=K なら、調べる窓は列全体の一つだけである。期限切れの移動は起こらず、列全体で1色または2色を使う塗り方を数える。例えば N=K=C=3N=K=C=3 では、全27通りから3色すべてを使う6通りを除いた21通りになる。

復習の核

  • 窓の制約では「次を足す前に残る範囲」を書く。ABB に C を足せるのは、新しい窓に残るのが BB だけだからである。
  • 色名を捨てても、具体的な色の選択数は捨てない。単色からの異色は C−1C-1 通り、2色状態での切替は1通りである。
  • 配列の値を残す操作にも遷移の意味がある。今回は同色継続が1通りだから値を保てる。期限切れの値を保持することと、その値を現在の状態や答えに含めることは区別する。

計算量と制約

時間

各マスで、期限切れの移動・累積和差分による遷移・累積和の追加を定数時間で行う。配列の初期化と答えの集計を含めて O(N)O(N) 時間。

空間

最終出現位置ごとの配列 dpdp と累積和 PP をそれぞれ O(N)O(N) 個保持するため、O(N)O(N) 空間。

制約との対応

2≤K≤N≤1062\leq K\leq N\leq 10^6、1≤C≤1091\leq C\leq 10^9。窓の色列や色名を状態にせず、最終出現位置へ圧縮することで状態の総数を O(N)O(N) に抑える。遷移元も毎回走査せず累積和で集約し、KK や CC に比例するループをなくす。

出典

分類・前提・執筆情報

掲載状態: 収録済み

At Most 2 Colors の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 最小十分状態からDPを設計する

主題
追加で学ぶ技能
    なし
    既習技能

    主タグ: DPの最小十分状態

    補助タグ: DP遷移の集約・高速化

    執筆: abc-explanation-author1.1.1 / revision 2

    学習の位置

    体系上の位置: 最小十分状態からDPを設計する

    • 採用解法の未来を決める最小十分状態と、捨てられる履歴を説明できる。

    先に読む単元:

    この解説で扱わないこと:

    • 状態の再利用をせず、頂点を一度ずつ訪問する到達可能性探索。

    学習記録

    状況更新: 更新記録なし

    復習設定更新: 更新記録なし

    端末内の保存状態を確認しています。

    要復習一覧 / 学習記録のバックアップ / 解説に戻る

    同じ単元の問題