ABC 443 E — Climbing Silver

考察

ある列の一番下の壁へ到達できたら、そこから真上へ進み、同じ列の壁を下から順に壊せる。この一本道を使えば、その列の上側をまとめて到達済みにできる。移動するたびに行が一つ上がることと組み合わせ、下の行から到達可能なマスを求めよう。

壁がなければ、各マスへ来られるかは一段下の三マスから決まる。しかし今回は、それまでに壊した壁によって次の移動の成否が変わる。壊した壁の集合を経路ごとに状態へ持つと、候補が膨大になる。そこで、壁を壊す条件の「同じ列の下側がすべて空き」に注目する。

行・列の番号は問題文と同じく1始まりとする。元の盤面で、列 jj の一番下の壁の行番号を low[j]low[j] と置く。壁がない列では low[j]=0low[j]=0 とする。その列で最初に壊せる壁は、この最下壁に限られる。それより上の壁へ先に入ろうとしても、最下壁が残っているため失敗するからだ。

一方、最下壁まで到達できれば、それより下に壁はないので、その壁を壊して入れる。その後は同じ列を真上へ進み続ければよい。次の壁に着くたびに、その下側の壁はすべてこの経路で壊している。従って、最下壁への到達が分かった時点で、その列の上側の全マスにも到達できると確定する。

ここで確定するのは「各マスへ至る合法な経路が存在する」ことだ。別々の経路で壊した壁を、一枚の盤面上ですべて壊れたことにしてよいわけではない。元の盤面と lowlow は変更せず、最下壁を通って真上へ進む具体的な経路を、一括確定の根拠として使う。

dp[i][j] を、開始マスから (i,j)(i,j) へ合法に到達できるかを表す真偽値とする。初期化は公式解説と同じく、開始列全体、すなわちすべての 1≤i≤N1\leq i\leq N で dp[i][C] = true とし、それ以外を false にする。開始マス (N,C)(N,C) は空きなので、そこから真上へ進めば、途中の壁を下から順に壊せる。この初期化にも実際の経路がある。

その後は行を i=N−1,N−2,…,1i=N-1,N-2,\ldots,1 の順に調べ、各行の全列を次の手順で処理する。

  1. dp[i][j] が既に true なら、そのマスの処理を終える。開始列の初期化や、一括確定による到達性を再判定して上書きしない。
  2. 一段下の (i+1,j−1),(i+1,j),(i+1,j+1)(i+1,j-1),(i+1,j),(i+1,j+1) のうち、盤面内のどのマスも到達不能なら、false のままにする。
  3. 一段下に到達可能なマスがあり、元の (i,j)(i,j) が空きなら、dp[i][j] = true とする。
  4. 元の (i,j)(i,j) が壁なら、low[j]=ilow[j]=i の場合だけ壊せる。このとき、すべての 1≤k≤i1\leq k\leq i について dp[k][j] = true とする。low[j]≠ilow[j]\ne i なら false のままにする。

4で元の最下壁だけを判定してよいのは、上の壁へ合法に到達するには最下壁を壊す必要があり、その最下壁へ到達した時点で上側も一括確定するからだ。上の壁を後から処理するときは、既に true なので1で飛ばされる。各行を処理する前には一段下の行が計算済みであり、一括確定した値も以後の三近傍の遷移に使える。

次の3×3の盤面で、開始列による違いを追ってみよう。上から1、2、3行目を表している。

#..
#..
...

この盤面では low[1]=2low[1]=2、low[2]=low[3]=0low[2]=low[3]=0 である。

  • 開始列が1なら、(3,1)→(2,1)→(1,1)(3,1)\to(2,1)\to(1,1) と進み、同列の二つの壁を順に壊せる。開始列全体の初期化は、この経路を先取りしている。2行目では2列目へも届くので到達状況は 110、最上行ではその2列目から3列目へ進めて 111 になる。最上行の1列目は low[1]≠1low[1]\ne1 でも既に到達済みであり、false に戻してはいけない。
  • 開始列が3なら、2行目では2、3列目にだけ届き、到達状況は 011 になる。最上行の1列目へ斜めに進もうとしても、(2,1)(2,1) の壁が残っていて壊せない。最上行も 011 である。

同じ盤面で開始列を2にすると、2行目の1列目へ初めて入るときに low[1]=2low[1]=2 が成立する。そこで1列目の1、2行目を一括で true にする。次に1行目の1列目を調べるときは処理済みとして飛ばすので、上の壁について再び列を走査する必要はない。

最後に、最上行の dp[1][1] から dp[1][N] を左から読み、true なら 1、false なら 0 を並べる。これが求める長さ NN の文字列であり、各テストケースにつき一行出力する。

典型の発動条件

盤面の依存順 DP

移動のたびに必ず行が一つ上がるなら、行を下から上へ処理できる。ただし、位置以外の履歴が将来へ影響する問題では、三近傍の到達性だけで十分かを先に確かめる。本問では、壁への到達を一括確定する根拠を示してから、位置だけの真偽値へ落としている。

列条件の前計算

「ある位置より下に障害物がないか」を繰り返し判定するときは、各列の最下位置を先に求めると、毎回下側を走査せずに済む。本問では元の最下壁を保持し、破壊済みかどうかを盤面へ書き戻す代わりに、到達済みのマスを処理から除く。

問題固有の要素

最下壁へ届いた一つの経路を、その列を真上に登る経路へ延長すれば、上側の到達性をまとめて保証できる。下側の壁を壊す必要があることに加え、それを満たし続ける一本道が存在することが、履歴を省く鍵となる。

別の問題で到達状態をまとめる際も、異なる経路の操作結果を混ぜずに、まとめて確定する各状態へ実際に至る経路を構成できるかを確認したい。

正当性

まず、true にするマスには必ず合法な経路がある。開始列の初期値には、開始マスから真上へ進む経路が対応する。空きマスへの通常遷移は、到達済みの一段下のマスへの経路に一手を足せばよい。最下壁への遷移では、その下側は元から空きなので壁を壊せる。続けて同じ列を真上へ進めば、上の壁も下から順に壊せるため、一括で立てる上側の各マスにも合法な経路が存在する。これらはそれぞれ一つの経路で実現でき、別経路の破壊履歴を合流させていない。

次に、任意の合法な経路を下から追い、到達するマスを取りこぼさないことを示す。開始マスは初期化される。空きマスに進むなら、一段下の到達済みマスから通常遷移で true になる。元の最下壁へ進むなら、最下壁の判定を通って一括確定される。元の最下壁より上の壁へ進める経路は、その列の下側の壁をすべて壊しているため、既に最下壁を通っている。その最下壁への到達時に上側全体を確定するので、このマスも true になっている。下の行から処理することで、必要な遷移元は処理時にすべて利用できる。

以上より、到達済みの値を保って処理を飛ばしても漏れはなく、最上行の真偽値は各列へ到達できるかと一致する。それを左から0/1へ変換した文字列が正しい答えである。

実装上の注意

  • 本文は1始まりである。0始まりで実装するなら、開始列を一度だけ1減らし、最上行は dp[0]、壁のない列の最下壁は -1 とする。
  • 左端・右端では、一段下の三近傍のうち盤面内の列だけを参照する。最下段の開始列以外は false のままであり、同じ行への横移動はしない。
  • 元の盤面と low は固定する。既に true の壁を再判定すると、開始列や一括確定した列の上側で、正しい到達性を消してしまう。
  • 最下壁が最下段にある列は、開始列にはなれず、移動でもその最下壁へ入れない。その列の上の空きマスには横から届く場合があるが、上の壁は壊せない。

復習の核

  • 履歴を捨てる前に、「その状態へ至る一つの合法な経路」を示す。到達可能という真偽値は、別々の経路の壁破壊履歴を自由に混ぜる許可ではない。
  • 最初に通る障害を特定し、そこから連続して進めるなら、先の状態をまとめて確定できる。確定済みを再処理しない条件まで含めて計算量を評価する。

計算量と制約

時間

元の最下壁の前計算、到達表の初期化、三近傍の確認はそれぞれ O(N2)O(N^2)。一括確定は最下壁へ初めて入れたときだけ行い、その後の上側は処理済みとして飛ばす。従って一括走査は各列で高々一回、全列で合計 O(N2)O(N^2) である。答えの作成・出力の O(N)O(N) を含め、1ケースの時間は O(N2)O(N^2)、全ケースでは O(∑N2)O(\sum N^2) となる。

空間

盤面と到達表に O(N2)O(N^2)、最下壁の配列と答えの文字列に O(N)O(N) を使うため、全体で O(N2)O(N^2)。ケースごとに領域を再利用すれば、全ケース分を同時に保存する必要はない。

制約との対応

1≤T≤500001\leq T\leq 50000、2≤N≤30002\leq N\leq 3000、1≤C≤N1\leq C\leq N で、開始マスは必ず空きマスである。入力全体で ∑N2≤9×106\sum N^2\leq9\times10^6 なので、ケース数だけでなく盤面の総マス数に比例する今回の手順で処理できる。壁がない列は通常遷移だけでよく、開始列に上側の壁が何枚あっても、下から順に壊す初期化が成立する。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Climbing Silver の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: グリッド・多次元表の局所DPを設計する

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

      主タグ: グリッド・多次元表の局所DP

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

      学習の位置

      体系上の位置: グリッド・多次元表の局所DPを設計する

      • グリッドまたは多次元表の依存方向と境界状態を定め、計算済みの局所近傍からDAG順に全状態を更新できる。

      先に読む単元:

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

      • 一次元の初歩的なDP、部分集合・資源DP、および区間の分割点を列挙する区間DP。

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題