考察
欠損のない二行を先に通り切り、残りも「左上から右下へ進む問題」にできれば、経路を探し直す必要はない。まず市松模様の色から不可能な場合を除き、その条件を保ったまま盤面を小さくする方法を考える。
マス を、 が偶数なら黒、奇数なら白とする。一歩動くたびに色が変わり、始点 と終点 はともに黒である。
- が奇数なら、指定された移動回数 も奇数なので、黒から黒へ到達できない。
- が偶数なら、盤面の黒と白はそれぞれ マスある。黒から始まり黒で終わる交互の経路は、黒を白より一マス多く使う。従って、取り除くマスは白、つまり が奇数でなければならない。
ここまでは必要条件である。以下では が偶数かつ が奇数なら、必ず経路を構成できることを示す。
高さが四以上で欠損が一つだけなら、上と下の両方の二行に欠損があることはない。そこで、欠損を含まない側の二行を帯として取り除く。一行だけでは、左上から横断した後の接続先が右側になり、残りの始点を左上に揃えにくい。二行を往復すれば左側へ戻れるため、同じ形の問題を残せる。
残った矩形の高さと幅を 、その矩形内での欠損座標を とする。座標は毎回、残矩形の左上を として数え直す。初期値は である。縮約中は次の不変条件を保つ。
- はともに偶数であり、欠損は矩形内に一つ、 は奇数である。
- これから埋める経路の始点は残矩形の左上 、終点は右下 である。
- 元の答えは「確定した前半
prefix + 残矩形の経路 + 保留した後半(suffix を逆順に連結したもの)」と表せる。
上や左の帯を通る移動列は prefix に順に追加する。下や右の帯は残矩形を通り終えた後に使うため、移動列のまとまりとしてスタック suffix に保存する。文字 は右への移動 R を 回繰り返す意味とし、他の方向も同様に書く。各帯の移動列は次のとおりである。表の座標と は、すべてその帯を除く前の値を使う。「上・下」は二行、「左・右」は二列を表す。
例えば上二行では、一行目を右へ進み、二行目を左へ戻り、最後の D で残矩形の左上へ入る。下二行では、残矩形の右下から最初の D で帯へ入り、下から二行目を左へ、最下行を右へ進んで元の右下に着く。左二列・右二列も、縦に往復する同じ作りである。帯の内部を一度ずつ通り、残矩形との接続は一辺だけなので、縮約後の経路の向きを変えずに済む。
帯は次の順で選ぶ。
- の間、上下を選ぶ。 なら上二行に欠損がないため、上帯を
prefix に追加し、 とする。そうでなければ である。 は偶数で なので、下二行の行番号は となり、欠損を含まない。下帯を suffix に積み、 とする。どちらも は変えない。
- になったら、 の間、左右を選ぶ。 なら左帯を
prefix に追加し、 とする。そうでなければ かつ なので右二列に欠損はない。右帯を suffix に積み、 とする。どちらも は変えない。
- で止める。 が奇数なので、欠損は右上 か左下 のどちらかである。前者なら
DR、後者なら RD が、残る三マスを結ぶ基底の経路になる。
上や左を除く場合は、表の出口が新しい左上になる。下や右を除く場合は、表の入口が新しい右下になる。従って、残矩形の端点は毎回、局所座標で左上 と右下 のままである。元の盤面上の座標も保持するなら、左上を とし、上帯を除くときだけ 、左帯を除くときだけ とする。残矩形の端点は と で追える。
最後に prefix、基底の経路、suffix から取り出した帯を連結する。先に保留した帯ほど外側にあるので、後半の帯は積んだ順の逆に使う。各帯の文字列自体は表の向きのまま使い、文字順を反転させない。接続のための追加の一歩も不要である。その一歩は上・左帯の末尾、下・右帯の先頭に既に含まれている。
具体的に を追う。上二行を除くと prefix は RRRRRDLLLLLD、残矩形は となる。次は下二行を除き、DLLLLLDRRRRR を保留して にする。その後は右二列を二回除き、RURD を二つ、この順で積む。最後の欠損は なので基底は DR である。答えは次の順になる。
RRRRRDLLLLLD + DR + RURD + RURD + DLLLLLDRRRRR
+ は連結を表し、出力には含めない。元の盤面上で接続点を追うと、上帯の出口が 、基底の出口が 、二つの右帯の出口が順に 、最後の下帯の出口が となる。外側の下帯を先に連結すると、その入口 にまだ到達していない。スタックを逆順に取り出す理由がここにある。
典型の発動条件
二部 graph の色数必要条件
上下左右の移動で各マスを一度ずつ通るときは、市松模様に塗って、端点の色・経路の長さ・使う二色の個数を照合する。本問では不可能な場合を除けるが、一般の障害物付き盤面では、色数が合っても経路が存在するとは限らない。十分性は別に示す必要がある。
外周 strip の再帰構成
外側の一部を通り切った後も、残りを同じ端点条件の小問題にできるときに使う。「除く部分に欠損がない」「残りへ接続できる」「必ず小さくなる」を揃える。本問では二行・二列の往復によりこの三条件を満たせる。
問題固有の要素
偶数寸法の矩形に白の欠損が一つだけあるため、縮めたい辺の長さが四以上なら、その両端の二つの帯のうち、必ず少なくとも一方は欠損を含まない。この性質が、色数の必要条件を十分条件へ引き上げる。複数の欠損があれば両側の帯が塞がることもあり、同じ選び方は保証されない。
構成を考えるときは、完成した経路の形だけでなく「帯を通り切った後、残りのどのマスへ接続するか」に注目する。入口・出口まで固定できれば、小問題の解を組み込むだけで全体を復元できる。
正当性
移動ごとに色が変わり、両端はともに黒である。従って奇数回の移動が必要な奇数 は不可能である。偶数 では、黒から黒への交互の経路は黒を白より一マス多く使うため、欠損は白、すなわち が奇数でなければならない。
この必要条件を満たす場合を考える。 で なら上二行、 なら下二行に欠損はない。後者では偶数 より下二行は三行目以降だからである。 のときも、 なら左二列、そうでなければ右二列が欠損を含まない。従って、手順で選ぶ帯は必ず安全である。
各帯の移動列はその帯の全マスを一度ずつ通り、上・左帯なら残矩形の左上で終わり、下・右帯なら残矩形の右下から始まる。除いた帯と残矩形のマスは重ならない。接続点では移動列を連結するだけなので、そのマスを再訪する移動は生じない。寸法は二ずつ減って偶数を保ち、欠損座標から引く値も二だけなので、欠損は範囲内で白のまま残る。残矩形の始点・終点も、それぞれ左上・右下に保たれる。
各縮約は を二減らし、各辺を二未満にしないので、必ず に到達する。このとき欠損は右上か左下であり、基底の DR または RD が残る全マスを一度ずつ通る。縮約の逆順に帯を戻すと、既に得た経路の先頭または末尾へ、重複のない帯を接続できる。prefix を追加順、suffix を取り出し順に連結する処理はこの復元と一致する。従って、元の左上から右下まで、欠損以外の マスをちょうど一度ずつ通る。移動回数も となり、必要条件を満たすすべての場合で構成に成功する。
実装上の注意
- 帯の文字列は、寸法を減らす前の で作る。上帯では 、左帯では を二減らす。下帯・右帯では欠損の局所座標を変えない。
suffix は帯ごとの文字列を保存するスタックとし、帯の並びだけを逆順にする。文字列内の R と L、U と D を入れ替える処理は不要である。
prefix も文字列のリストで保持し、最後に一括で連結する。不変文字列へ何度も先頭挿入・連結すると、既存部分のコピーを繰り返して計算量が増える。
- 最小の では帯を除くループを一度も実行せず、欠損に応じて
DR または RD を出す。出力の確認では長さだけでなく、範囲内・再訪なし・欠損回避・最終座標も検査する。
復習の核
- 市松模様は「不可能」を見抜く道具である。色数が合う場合の構成を示して、初めて必要十分条件になる。
- 大きな構成は、除く部分の入口・出口を固定し、残りの問題で同じ条件を保てるかを探す。
- 答えの末尾を外側から決めたら、使う順は逆になる。帯を保存する順と、各帯の中を進む向きを区別する。
計算量と制約
時間
一テストケースあたり 。判定と初期化は 、帯を除く回数は上下・左右合わせて 回である。上下の帯は一回 文字、左右の帯は一回 文字で、基底を含む全文字数は になる。各部分を一度生成し、最後に一括連結・出力すれば、前処理から出力まで で収まる。
空間
一テストケースあたり 。prefix・suffix の文字列と最終出力を合わせて 文字、帯ごとの管理には 要素を使う。テストケースは一つずつ処理する。
制約との対応
公式制約は 、、、欠損は始点・終点以外である。全テストケースの の総和は 以下なので、全体の時間は 、保持領域は処理中の一ケース分でよい。移動列そのものが 文字あるため、出力長に見合った計算量である。
出典