解説
問題の言い換え
各行・各列について、括弧列の残高(開き括弧の個数から閉じ括弧の個数を引いたもの)をマスの辺に書くことを考えます。
あるマスの左・右・上・下の辺に書かれた整数をそれぞれ l,r,t,b とします。
このとき、杭の種類と辺値の関係は以下のようになります。
| 杭の種類 |
r−l |
b−t |
L |
1 |
0 |
R |
−1 |
0 |
U |
0 |
1 |
D |
0 |
−1 |
各行・各列の括弧列が正しい括弧列であることは、すべての辺値が非負であり、外周の辺値がすべて 0 であることに対応します。
また、あるマスを厳密に内側に含む横方向のペアの個数は min(l,r) であり、縦方向についても同様です。よって、このマスの高さは
min(l,r)+min(t,b)
となります。
各マスには杭をちょうど 1 本打つので、
∣r−l∣+∣b−t∣=1
が成り立ちます。したがって、このマスの高さを A とすると、
l+r+t+b=2min(l,r)+2min(t,b)+∣r−l∣+∣b−t∣=2A+1
を得ます。
ここで、四辺の和が 2A+1 であるとき、杭がちょうど 1 本であるための条件を考えます。
x=r−l, y=b−t とおくと、整数 x,y に対して
∣x∣+∣y∣=1
であることは、
x+y∈{−1,1},x−y∈{−1,1}
であることと同値です。
四辺の和が 2A+1 であることを用いると、
x+yx−y=2A+1−2(l+t),=2(r+t)−(2A+1)
となるため、これは
A≤l+t≤A+1,
A≤r+t≤A+1
と同値です。
以上より、元の問題は次のように言い換えられます。
すべての辺に整数を割り当て、以下の条件を満たせ。
- 外周の辺値は 0 である。
- すべての辺値は非負である。
- 各マスについて l+r+t+b=2A+1 である。
- 各マスについて A≤l+t≤A+1 および A≤r+t≤A+1 である。
四辺の和を合わせる
まず、外周の辺値と四辺の和に関する条件のみを満たす割り当てを一つ求めます。この時点では負の辺値も許すことにします。
すべての辺値を 0 で初期化し、以下の操作を行います。
- 各行について、第 N 列から第 2 列まで順に、そのマスの四辺の和が 2Ai,j+1 となるように左辺の値を決める。
- 第 1 列について、第 1 行から第 N−1 行まで順に、そのマスの四辺の和が 2Ai,1+1 となるように下辺の値を決める。
これによって、左下のマスを除くすべてのマスについて条件を満たすことができます。
各マスの四辺の和に (−1)i+j を掛けて足すと、内部の辺はすべて打ち消し合います。外周の辺値は 0 なので、この総和は常に 0 です。
解の存在が保証されていることから、
i=1∑Nj=1∑N(−1)i+j(2Ai,j+1)=0
が成り立ちます。よって、左下のマスについても四辺の和は自動的に一致します。
四辺の和を保つ変形
求めた辺値を、各マスの四辺の和を変えずに調整することを考えます。
ここで、一つの内部格子点に接する 4 本の辺に、交互に +1,−1,+1,−1 を加える操作を考えます。
この操作では、周囲の各マスについて一方の辺が 1 増え、もう一方の辺が 1 減るため、四辺の和は変化しません。
このような操作を各格子点で任意の整数回行うことを考えます。
各格子点に整数変数 z を割り当て、外周の格子点では z=0 とします。
マス (i,j) の左上・右上・左下・右下の変数をそれぞれ zTL,zTR,zBL,zBR とし、σ=(−1)i+j とおくと、四辺の補正量を次のように定めることができます。
ΔlΔrΔtΔb=σ(zTL−zBL),=σ(zBR−zTR),=σ(zTR−zTL),=σ(zBL−zBR).
隣り合うマスでは σ の符号が異なるため、共有する辺の補正量は一致します。また、
Δl+Δr+Δt+Δb=0
であるため、四辺の和は変化しません。
さらに、外周の辺値と各マスの四辺の和を保つ任意の変形は、この形で表せます。
実際、二つの辺値の割り当ての差を考えます。上端の格子点の変数をすべて 0 とし、各縦向きの辺の補正量がその差に一致するように、格子点の変数を上から順に決めます。
すると、すべての縦向きの辺の補正量が一致します。四辺の補正量の和が 0 であることから、各マスの上辺の補正量が一致していれば、下辺の補正量も一致します。したがって、横向きの辺についても補正量が一致します。
左右の外周では縦向きの辺の補正量が 0 であり、下端では横向きの辺の補正量が 0 であるため、外周の格子点の変数はすべて 0 となります。
よって、この変形によって正解の辺値を得ることができます。
差分制約への帰着
残る条件を、格子点の変数 z に関する制約として表します。
各辺の補正量は二つの変数の差であるため、辺値の非負条件は
zv−zu≤c
という形の制約になります。
次に、各マスについて
A≤l+t≤A+1
という条件を考えます。
補正量について、
Δl+Δt=σ(zTR−zBL)
が成り立ちます。同様に、
Δr+Δt=σ(zBR−zTL)
が成り立ちます。
したがって、各マスの条件は、それぞれの対角線の両端に対する
c≤zv−zu≤c+1(1)
という形の制約になります。
以上より、すべての制約を差分制約として表すことができました。
制約 zv−zu≤c に対して、頂点 u から頂点 v に重み c の有向辺を張ります。
このグラフの頂点数・辺数はともに O(N2) です。通常のベルマンフォード法では O(N4) 時間を要するため、高速化を考えます。
対角線方向の制約を用いた初期化
式 (1) の上限と下限の差が 1 であることに注目します。
外周の格子点の変数を 0 とし、内部の格子点については上の行から順に初期値を決めます。
内部の格子点 v に対して、その左上に隣接する格子点を u とすると、両者の間には
c≤zv−zu≤c+1
という制約が存在します。この上限を用いて、
zv(0)=zu(0)+c+1
と初期化します。
任意の実行可能な解を z∗ とします。
zv(0)−zv∗=zu(0)−zu∗+c+1−(zv∗−zu∗)
であり、
0≤c+1−(zv∗−zu∗)≤1
が成り立ちます。
すなわち、対角線に沿って一つ進むごとに、初期値と解との差は 0 または 1 だけ増えます。
外周では z(0)=z∗=0 であり、任意の格子点は外周から高々 N 歩で到達できるため、
0≤zv(0)−zv∗≤N
がすべての頂点 v について成り立ちます。
差分制約を解く
得られた初期値に対して、キューを用いた緩和を行います。
はじめにすべての頂点をキューに入れます。頂点 u を取り出し、u から出る重み c の辺 u→v について、
zv←min(zv,zu+c)
と更新します。値が変化した頂点がキューに入っていなければ、キューに追加します。
初期状態では zv≥zv∗ です。また、各制約について
zu+c≥zu∗+c≥zv∗
であるため、緩和によってこの大小関係が崩れることはありません。特に、外周の変数は常に 0 のままです。
各変数は更新されるたびに少なくとも 1 減少し、初期値から zv∗ までの差は高々 N です。
したがって、各頂点の更新回数は高々 N 回となります。
キューが空になれば、すべての差分制約が満たされています。
解の復元・計算量
求めた格子点の変数から各辺値を計算し、(r−l,b−t) に対応する杭を各マスに打てばよいです。
各格子点に接続する有向辺の本数は O(1) であり、各格子点の更新回数は高々 N 回です。
以上より、時間計算量 O(N3)、空間計算量 O(N2) でこの問題を解くことができました。