ABC 379 G — Count Grid 3-coloring

考察

マスを左上から一つずつ埋めると、次の色を選ぶときに調べる相手は上と左だけになる。過去の盤面を丸ごと覚える必要はなく、これから埋めるマスと接する部分の色を残せばよい。ただし、その部分は走査途中では二行にまたがる。「一行の配色」と「直近に埋めたマスの色列」を区別することが、この問題の状態設計の要点である。

? の個数を qq とすると、全置換は 3q3^q 通りあり、最大200マスでは列挙できない。一方、盤面を転置しても隣接関係と固定色は保たれ、答えは変わらない。以後は転置後の行数・列数を H,WH,W とし、W≤HW\leq H とする。W2≤HW≤200W^2\leq HW\leq 200 なので W≤14W\leq 14 である。この短辺だけに対して指数となる状態を探す。

直近のマスはどこにあるか

行・列を0始まりとし、上の行から順に、各行を左から右へ埋める。次に埋めるマスを (i,j)(i,j)、既に埋めたマス数を t=iW+jt=iW+j とする。状態には、走査順で直近の min⁡(t,W)\min(t,W) マスの色を古い順に残す。この色列を frontier と呼ぶ。

最初の一行を埋めている間は、状態はその行の埋めた部分だけである。2行目以降で (i,j)(i,j) を埋める直前には、次の順で WW マスが並ぶ。

(i−1,j),…,(i−1,W−1),(i,0),…,(i,j−1)(i-1,j),\ldots,(i-1,W-1),\quad (i,0),\ldots,(i,j-1)

前半は前の行の右側、後半は現在行の左側で、j=0j=0 では後半は空である。先頭が次のマスの上、j>0j>0 なら末尾が左に当たる。この WW マスより古いマスは、未処理領域と辺を共有しないので忘れられる。

ここで、色列の隣り合う要素が、盤面でも隣り合うとは限らない。たとえば、次の固定盤面はすべての隣接色が異なるので、答えは1である。

12
21

下段左の 2 まで処理すると、直近二色は上段右の 2 と下段左の 2、すなわち (2,2)(2,2) になる。この二マスは対角なので同色でよい。横隣接条件を満たす「一行の配色」だけを状態候補にすると、この合法盤面まで除いてしまう。

境界の形から状態数を数える

WW マスが完全な一行をなすときは、最初の色が3通り、以降は左と異なる2通りずつなので、配色は 3⋅2W−13\cdot 2^{W-1} 通りである。

W≥2W\geq 2 で行の途中、つまり 0<j<W0<j<W なら、frontier は長さ W−jW-j と jj の二本の水平な列に分かれる。それぞれの列内には横隣接の制約があるが、二本の列の間には辺がない。したがって、この境界だけの配色数は

(3⋅2W−j−1)(3⋅2j−1)=9⋅2W−2\bigl(3\cdot 2^{W-j-1}\bigr)\bigl(3\cdot 2^{j-1}\bigr) =9\cdot 2^{W-2}

となる。過去の縦隣接条件や固定色によって到達できない配色もあるので、これはDPの状態数の上界である。最初の行の短い色列もこの上界に収まる。W=1W=1 では一本の列を縦に進むだけであり、保持する色は高々3通りである。

採用する候補は、到達した frontier だけを疎に保持するDPである。全 3W3^W 通りの色列を用意して各マスで走査するのではなく、空状態から合法な遷移だけを生成する。こうすれば一層の状態数は定数倍の 2W2^W に抑えられる。

整数キーで状態を更新する

色列を毎回コピーすると幅に比例する費用がかかるため、ここでは各色を4進数の桁に入れた整数 kk をハッシュ表のキーにする。色は 1,2,3 をそのまま使い、未処理の桁だけを 0 とする。最大 WW 桁で、先頭が最も古い色、末尾が最も新しい色である。最初の行では左を0で埋める。層 tt が決まれば実際の色列の長さも決まるので、先頭の0と実際の色を混同しない。

dp[k]dp[k] を、処理済みの固定色・隣接条件を満たし、色列のキーが kk である配色数とする。値はすべて 998244353998244353 で割った余りで持つ。初期状態は空領域を表す dp[0]=1dp[0]=1 だけである。B=4W−1B=4^{W-1} をあらかじめ求め、各マス (i,j)(i,j) で次の処理を行う。

  1. 次層用のハッシュ表 next を空にする。現在の dp にあるキーだけを列挙する。
  2. マスが固定色ならその一色、? なら三色を候補 cc とする。
  3. i>0i>0 なら上の色 ⌊k/B⌋\lfloor k/B\rfloor と、j>0j>0 なら左の色 k mod 4k\bmod 4 と比較し、cc がどちらかと等しければ捨てる。最初の行には上判定を、行頭には左判定を行わない。
  4. 合法なら、最古の桁を落として残りを一桁ずらし、末尾に cc を入れる。
k′=4(k mod B)+ck'=4(k\bmod B)+c

そして next のキー k′k' の値へ dp[k]dp[k] を加算する。同じキーへ来た配色はこの加算でまとめる。色名 1,2,3 は固定マスと対応するため、色を出現順に付け直す正規化はしない。

全キー・全候補の処理後に dp を next へ置き換え、次のマスへ進む。全 HWHW マスを処理した後は、残った色列に追加の条件はない。答えは終層の全キーの値の和を 998244353998244353 で割った余りである。

典型の発動条件

grid frontier DP

片方の辺長が小さく、制約が近傍のマスの間で決まるときは、走査済みと未走査の境界を状態にする候補が立つ。境界より古い情報で後続の選択肢が変わらないことを確認してから捨てる。

状態数を削るときは、境界に実在する辺の制約だけを使う。一次元の色列として保存していても、途中の行境界に横隣接の制約を足してよいわけではない。

問題固有の要素

面積制約 HW≤200HW\leq 200 を短辺へ読み替えると W≤14W\leq 14 が得られる。さらに、三色では水平な列の各マスに二択しかなく、二本に分かれる場合もその先頭にそれぞれ三択を与えるだけでよい。この二段階で、指数部分を盤面全体から短辺へ、さらに 3W3^W から定数倍の 2W2^W へ下げられる。

別の問題へ持ち帰る視点は、保存する配列の見た目ではなく、境界上のマス同士を結ぶ実際の辺を描いて状態数を数えることである。

正当性

各層で、処理済み領域の固定色と隣接条件を満たす配色を、直近の最大 WW マスの色列ごとに数える。未処理マスに接する処理済みマスはすべてこの色列に含まれ、同じ状態の配色は後続の選択肢も等しい。空領域の配色は一通りであり、次色を固定色および上・左の色で検査すれば、新たに確定する辺の条件をすべて確認できる。窓から落ちるマスには以後検査すべき辺が残らない。各合法完成盤面は走査順の一意な色追加列に対応するため、遷移は漏れも重複もなく全配色を数え、終層の全状態の和が答えになる。

実装上の注意

  • 行頭では、キーの末尾は前の行の右端である。これは現在マスの左隣ではないので、列番号を使って左判定を切る。最初の行では上判定も切る。
  • W=1W=1 では B=1B=1 なので更新後のキーは次色そのものになる。左判定は一度も行わず、上の色だけを検査すればよい。
  • キーは高々 4W−1≤228−14^W-1\leq 2^{28}-1 なので整数一語に収まる。桁列のコピーや文字列化は不要である。次層を別に用意し、同じマスを二度埋める更新を防ぐ。
  • 固定色同士が衝突すると対応する遷移がなくなる。層が空になれば答えは0である。法を取って値が0になったキーを削除しなくても、到達したキーだけを列挙すれば状態数の上界は保たれる。

復習の核

  • 幅指数のDPでは、まず未来と接する過去のマスを描き、忘れてよい情報を確かめる。
  • 「直近 WW マス」は「最後の一行」とは異なる。保存順で隣り合っても、盤面の辺で結ばれていなければ色違いを要求しない。
  • 有効状態が少ないことと、それだけを処理する実装は別である。空状態から生成したキーだけを走査して、状態数の評価を実行時間へ結び付ける。

計算量と制約

時間

一層の状態数の上界を SS とすると、W≥2W\geq 2 では S=9⋅2W−2S=9\cdot 2^{W-2}、W=1W=1 では S=3S=3 とできる。各状態で試す色は高々三つで、上・左の取得とキーの更新は整数一語の演算である。ハッシュ表の検索・加算を期待 O(1)O(1) とすると、全体の期待時間計算量は O(HWS)=O(HW2W)O(HWS)=O(HW2^W) となる。

入力と転置は O(HW)O(HW)、BB の計算は O(W)O(W)。状態集合の事前列挙や色の正規化は行わず、各層のキーの生成・重複集約・表の初期化と破棄も O(S)O(S) の範囲に含む。全 3W3^W 通りを各マスで走査する実装は O(HW3W)O(HW3^W) であり、この評価には含めない。

空間

現在層と次層の二つのハッシュ表に O(S)O(S)、入力盤面に O(HW)O(HW) を使うため、合計 O(S+HW)O(S+HW)。全整数キーに対応する密な配列は用意しない。

制約との対応

1≤H,W1\leq H,W、HW≤200HW\leq 200 より、転置後は W≤14W\leq 14。幅14でも S=9⋅212=36864S=9\cdot 2^{12}=36864 であり、高々200マスに対して一状態あたり三候補だけを調べる。固定色は候補を減らす方向にしか働かず、? だけの盤面でもこの状態数の上界を使える。

一行が完成した層は 3⋅2W−13\cdot 2^{W-1} 通りだが、途中の二本に分かれた層まで同じ数に制限しない。小盤面 12 / 21 の途中の (2,2)(2,2) を保持できることが、その区別を確かめる最小の例になる。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Count Grid 3-coloring の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: frontier/profile DP・境界状態圧縮

主題
  • frontier/profile DP・境界状態圧縮: 未処理領域へ影響する境界上の色・使用済みフラグ・接続partitionだけを残し、窓外の情報を忘れられることを証明して幅指数のprofile DPを設計できる。
追加で学ぶ技能
    なし
    既習技能

    主タグ: frontier/profile DP・境界状態圧縮

    補助タグ: DPの最小十分状態

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

    学習の位置

    体系上の位置: frontier/profile DP・境界状態圧縮

    • 未処理領域へ影響する境界上の色・使用済みフラグ・接続partitionだけを残し、窓外の情報を忘れられることを証明して幅指数のprofile DPを設計できる。

    先に読む単元:

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題