ABC 454 E — LRUD Moving

考察

欠損のない二行を先に通り切り、残りも「左上から右下へ進む問題」にできれば、経路を探し直す必要はない。まず市松模様の色から不可能な場合を除き、その条件を保ったまま盤面を小さくする方法を考える。

マス (i,j)(i,j) を、i+ji+j が偶数なら黒、奇数なら白とする。一歩動くたびに色が変わり、始点 (1,1)(1,1) と終点 (N,N)(N,N) はともに黒である。

  • NN が奇数なら、指定された移動回数 N2−2N^2-2 も奇数なので、黒から黒へ到達できない。
  • NN が偶数なら、盤面の黒と白はそれぞれ N2/2N^2/2 マスある。黒から始まり黒で終わる交互の経路は、黒を白より一マス多く使う。従って、取り除くマスは白、つまり A+BA+B が奇数でなければならない。

ここまでは必要条件である。以下では NN が偶数かつ A+BA+B が奇数なら、必ず経路を構成できることを示す。

高さが四以上で欠損が一つだけなら、上と下の両方の二行に欠損があることはない。そこで、欠損を含まない側の二行を帯として取り除く。一行だけでは、左上から横断した後の接続先が右側になり、残りの始点を左上に揃えにくい。二行を往復すれば左側へ戻れるため、同じ形の問題を残せる。

残った矩形の高さと幅を H,WH,W、その矩形内での欠損座標を (A,B)(A,B) とする。座標は毎回、残矩形の左上を (1,1)(1,1) として数え直す。初期値は H=W=NH=W=N である。縮約中は次の不変条件を保つ。

  • H,WH,W はともに偶数であり、欠損は矩形内に一つ、A+BA+B は奇数である。
  • これから埋める経路の始点は残矩形の左上 (1,1)(1,1)、終点は右下 (H,W)(H,W) である。
  • 元の答えは「確定した前半 prefix + 残矩形の経路 + 保留した後半(suffix を逆順に連結したもの)」と表せる。

上や左の帯を通る移動列は prefix に順に追加する。下や右の帯は残矩形を通り終えた後に使うため、移動列のまとまりとしてスタック suffix に保存する。文字 Rk\mathrm{R}^k は右への移動 R を kk 回繰り返す意味とし、他の方向も同様に書く。各帯の移動列は次のとおりである。表の座標と H,WH,W は、すべてその帯を除く前の値を使う。「上・下」は二行、「左・右」は二列を表す。

帯移動列入口 → 出口更新
上RW−1DLW−1D\mathrm{R}^{W-1}\mathrm{D}\mathrm{L}^{W-1}\mathrm{D}(1,1)→(3,1)(1,1)\to(3,1)H←H−2, A←A−2H\leftarrow H-2,\ A\leftarrow A-2
下DLW−1DRW−1\mathrm{D}\mathrm{L}^{W-1}\mathrm{D}\mathrm{R}^{W-1}(H−2,W)→(H,W)(H-2,W)\to(H,W)H←H−2H\leftarrow H-2
左DH−1RUH−1R\mathrm{D}^{H-1}\mathrm{R}\mathrm{U}^{H-1}\mathrm{R}(1,1)→(1,3)(1,1)\to(1,3)W←W−2, B←B−2W\leftarrow W-2,\ B\leftarrow B-2
右RUH−1RDH−1\mathrm{R}\mathrm{U}^{H-1}\mathrm{R}\mathrm{D}^{H-1}(H,W−2)→(H,W)(H,W-2)\to(H,W)W←W−2W\leftarrow W-2

例えば上二行では、一行目を右へ進み、二行目を左へ戻り、最後の D で残矩形の左上へ入る。下二行では、残矩形の右下から最初の D で帯へ入り、下から二行目を左へ、最下行を右へ進んで元の右下に着く。左二列・右二列も、縦に往復する同じ作りである。帯の内部を一度ずつ通り、残矩形との接続は一辺だけなので、縮約後の経路の向きを変えずに済む。

帯は次の順で選ぶ。

  1. H>2H>2 の間、上下を選ぶ。 A>2A>2 なら上二行に欠損がないため、上帯を prefix に追加し、H←H−2, A←A−2H\leftarrow H-2,\ A\leftarrow A-2 とする。そうでなければ A≤2A\leq2 である。HH は偶数で H≥4H\geq4 なので、下二行の行番号は H−1,H≥3H-1,H\geq3 となり、欠損を含まない。下帯を suffix に積み、H←H−2H\leftarrow H-2 とする。どちらも W,BW,B は変えない。
  2. H=2H=2 になったら、W>2W>2 の間、左右を選ぶ。 B>2B>2 なら左帯を prefix に追加し、W←W−2, B←B−2W\leftarrow W-2,\ B\leftarrow B-2 とする。そうでなければ B≤2B\leq2 かつ W≥4W\geq4 なので右二列に欠損はない。右帯を suffix に積み、W←W−2W\leftarrow W-2 とする。どちらも H,AH,A は変えない。
  3. H=W=2H=W=2 で止める。 A+BA+B が奇数なので、欠損は右上 (1,2)(1,2) か左下 (2,1)(2,1) のどちらかである。前者なら DR、後者なら RD が、残る三マスを結ぶ基底の経路になる。

上や左を除く場合は、表の出口が新しい左上になる。下や右を除く場合は、表の入口が新しい右下になる。従って、残矩形の端点は毎回、局所座標で左上 (1,1)(1,1) と右下 (H,W)(H,W) のままである。元の盤面上の座標も保持するなら、左上を (r,c)(r,c) とし、上帯を除くときだけ r←r+2r\leftarrow r+2、左帯を除くときだけ c←c+2c\leftarrow c+2 とする。残矩形の端点は (r,c)(r,c) と (r+H−1,c+W−1)(r+H-1,c+W-1) で追える。

最後に prefix、基底の経路、suffix から取り出した帯を連結する。先に保留した帯ほど外側にあるので、後半の帯は積んだ順の逆に使う。各帯の文字列自体は表の向きのまま使い、文字順を反転させない。接続のための追加の一歩も不要である。その一歩は上・左帯の末尾、下・右帯の先頭に既に含まれている。

具体的に N=6, (A,B)=(3,2)N=6,\ (A,B)=(3,2) を追う。上二行を除くと prefix は RRRRRDLLLLLD、残矩形は (H,W,A,B)=(4,6,1,2)(H,W,A,B)=(4,6,1,2) となる。次は下二行を除き、DLLLLLDRRRRR を保留して (2,6,1,2)(2,6,1,2) にする。その後は右二列を二回除き、RURD を二つ、この順で積む。最後の欠損は (1,2)(1,2) なので基底は DR である。答えは次の順になる。

RRRRRDLLLLLD + DR + RURD + RURD + DLLLLLDRRRRR

+ は連結を表し、出力には含めない。元の盤面上で接続点を追うと、上帯の出口が (3,1)(3,1)、基底の出口が (4,2)(4,2)、二つの右帯の出口が順に (4,4),(4,6)(4,4),(4,6)、最後の下帯の出口が (6,6)(6,6) となる。外側の下帯を先に連結すると、その入口 (4,6)(4,6) にまだ到達していない。スタックを逆順に取り出す理由がここにある。

典型の発動条件

二部 graph の色数必要条件

上下左右の移動で各マスを一度ずつ通るときは、市松模様に塗って、端点の色・経路の長さ・使う二色の個数を照合する。本問では不可能な場合を除けるが、一般の障害物付き盤面では、色数が合っても経路が存在するとは限らない。十分性は別に示す必要がある。

外周 strip の再帰構成

外側の一部を通り切った後も、残りを同じ端点条件の小問題にできるときに使う。「除く部分に欠損がない」「残りへ接続できる」「必ず小さくなる」を揃える。本問では二行・二列の往復によりこの三条件を満たせる。

問題固有の要素

偶数寸法の矩形に白の欠損が一つだけあるため、縮めたい辺の長さが四以上なら、その両端の二つの帯のうち、必ず少なくとも一方は欠損を含まない。この性質が、色数の必要条件を十分条件へ引き上げる。複数の欠損があれば両側の帯が塞がることもあり、同じ選び方は保証されない。

構成を考えるときは、完成した経路の形だけでなく「帯を通り切った後、残りのどのマスへ接続するか」に注目する。入口・出口まで固定できれば、小問題の解を組み込むだけで全体を復元できる。

正当性

移動ごとに色が変わり、両端はともに黒である。従って奇数回の移動が必要な奇数 NN は不可能である。偶数 NN では、黒から黒への交互の経路は黒を白より一マス多く使うため、欠損は白、すなわち A+BA+B が奇数でなければならない。

この必要条件を満たす場合を考える。H>2H>2 で A>2A>2 なら上二行、A≤2A\leq2 なら下二行に欠損はない。後者では偶数 H≥4H\geq4 より下二行は三行目以降だからである。H=2, W>2H=2,\ W>2 のときも、B>2B>2 なら左二列、そうでなければ右二列が欠損を含まない。従って、手順で選ぶ帯は必ず安全である。

各帯の移動列はその帯の全マスを一度ずつ通り、上・左帯なら残矩形の左上で終わり、下・右帯なら残矩形の右下から始まる。除いた帯と残矩形のマスは重ならない。接続点では移動列を連結するだけなので、そのマスを再訪する移動は生じない。寸法は二ずつ減って偶数を保ち、欠損座標から引く値も二だけなので、欠損は範囲内で白のまま残る。残矩形の始点・終点も、それぞれ左上・右下に保たれる。

各縮約は H+WH+W を二減らし、各辺を二未満にしないので、必ず 2×22\times2 に到達する。このとき欠損は右上か左下であり、基底の DR または RD が残る全マスを一度ずつ通る。縮約の逆順に帯を戻すと、既に得た経路の先頭または末尾へ、重複のない帯を接続できる。prefix を追加順、suffix を取り出し順に連結する処理はこの復元と一致する。従って、元の左上から右下まで、欠損以外の N2−1N^2-1 マスをちょうど一度ずつ通る。移動回数も N2−2N^2-2 となり、必要条件を満たすすべての場合で構成に成功する。

実装上の注意

  • 帯の文字列は、寸法を減らす前の H,WH,W で作る。上帯では AA、左帯では BB を二減らす。下帯・右帯では欠損の局所座標を変えない。
  • suffix は帯ごとの文字列を保存するスタックとし、帯の並びだけを逆順にする。文字列内の R と L、U と D を入れ替える処理は不要である。
  • prefix も文字列のリストで保持し、最後に一括で連結する。不変文字列へ何度も先頭挿入・連結すると、既存部分のコピーを繰り返して計算量が増える。
  • 最小の N=2N=2 では帯を除くループを一度も実行せず、欠損に応じて DR または RD を出す。出力の確認では長さだけでなく、範囲内・再訪なし・欠損回避・最終座標も検査する。

復習の核

  • 市松模様は「不可能」を見抜く道具である。色数が合う場合の構成を示して、初めて必要十分条件になる。
  • 大きな構成は、除く部分の入口・出口を固定し、残りの問題で同じ条件を保てるかを探す。
  • 答えの末尾を外側から決めたら、使う順は逆になる。帯を保存する順と、各帯の中を進む向きを区別する。

計算量と制約

時間

一テストケースあたり O(N2)O(N^2)。判定と初期化は O(1)O(1)、帯を除く回数は上下・左右合わせて N−2N-2 回である。上下の帯は一回 2W2W 文字、左右の帯は一回 2H2H 文字で、基底を含む全文字数は N2−2N^2-2 になる。各部分を一度生成し、最後に一括連結・出力すれば、前処理から出力まで O(N2)O(N^2) で収まる。

空間

一テストケースあたり O(N2)O(N^2)。prefix・suffix の文字列と最終出力を合わせて O(N2)O(N^2) 文字、帯ごとの管理には O(N)O(N) 要素を使う。テストケースは一つずつ処理する。

制約との対応

公式制約は 1≤T≤50001\leq T\leq5000、2≤N≤1032\leq N\leq10^3、1≤A,B≤N1\leq A,B\leq N、欠損は始点・終点以外である。全テストケースの N2N^2 の総和は 10610^6 以下なので、全体の時間は O(∑N2)O(\sum N^2)、保持領域は処理中の一ケース分でよい。移動列そのものが N2−2N^2-2 文字あるため、出力長に見合った計算量である。

出典

分類・前提・執筆情報

掲載状態: 収録済み

LRUD Moving の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 成立証明から構成解を復元する

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

    主タグ: 構成解・witness復元

    補助タグ: 二部グラフの彩色と成分構造

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

    学習の位置

    体系上の位置: 成立証明から構成解を復元する

    • 成立証明に対応する親・局所操作・選択を記録し、要件を満たす構成を出力できる。

    先に読む単元:

    • 二部彩色と成分構造を扱う — 無向グラフを探索できることを前提に二部性と部の交換対称性を扱い、連結二部グラフの彩色重複も補正する。

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

    • 存在判定・個数計算だけで、具体的な解や操作列を復元しない問題。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題