考察
#を+1、.を-1と置けば、長方形がbalancedである条件は領域和が0であることと同値になる。転置してH≤WとするとH≤√(HW)なので、上下端O(H²)通りと横一走査O(W)を組み合わせる余地がある。
採用する候補: 短辺側の上下端を固定し、列和配列の零和連続区間を密なprefix頻度配列で数える
棄却する候補: 四辺をすべて列挙し、二次元累積和で各長方形を判定する
判定をO(1)にしても長方形がΘ(H²W²)個あり、細長くない盤面で間に合わない。
棄却する候補: 上下端ごとにprefix sumをmapまたはsortで数える
一般的な零和区間の解法だがO(H²W log W)となる。prefix値域が[-HW,HW]に限られる本問ではlog因子を除く必要がある。
必要なら盤面を転置してH≤Wにする。各uについて列和Cを0初期化し、d=u..Hで新しい行の±1をCへ加える。Cのprefix sumを左から計算し、同じ値の過去出現回数を答えへ足してから頻度を増やし、全(u,d)の寄与を合計する。
典型の発動条件
短辺の二乗全探索
発動条件: 二次元領域で面積制約があり、片方の二辺を固定すると残りを線形走査できる。
転置でH≤Wを保証し、上下端O(H²)と列走査O(W)に分解する。
prefix sumの同値対による零和区間計数
発動条件: 一次元列の総和0となる連続区間数を求めたい。
同じprefix値の既出回数を加算し、値域が狭いことを利用して密配列でO(W)計数する。
問題固有の要素
ΣHW制約だけを見ると三重ループを避けたくなるが、短辺は各testの√(HW)以下なので、向きを揃えたO(H²W)は全test合計でも成立する。
別の問題へ持ち帰る視点: 積で与えられた入力制約では、短い次元を二乗する前にmin次元≤√(積)を代入し、全testの面積和まで含めて真の上界を評価する。
正当性
上端uを固定して下端dを一段ずつ広げれば、各列の#−.の和C_jは新しい一行を足すだけで更新でき、Cを毎回高さ分走査する必要がない。 列区間[l,r]の和が0であることは、その直前と直後のprefix sumが等しいことと同値である。値域が狭いのでhashやsortではなくoffset付き配列で出現回数を即時参照できる。 各上下端に対して列を一度走査するO(H²W)となり、H≤√(HW)とΣHW≤3×10^5を使えば約√(3×10^5)·3×10^5規模に抑えられる。
実装上の注意
- 転置後のH,Wで値域offsetを確保し、prefix=0を走査前に1回登録する。頻度配列を上下端ごとに全消去すると余分な計算量になるため、触れたindexだけ戻すかtimestampを使う。答えは64 bitで持つ。
復習の核
- 小盤面の全長方形列挙と照合し、1×W、全て同じ記号、奇数面積、転置が発生する入力、同じprefix値が3回以上現れる場合、複数testで頻度状態が残らないことを確認する。
計算量と制約
時間
O(min(H,W)²max(H,W))、複数caseはcaseごとの和。
空間
O(HW)、盤面と列和、prefix頻度の値域もO(HW)。
制約との対応
公式制約の確認範囲: Time limit: 3 sec; Memory limit: 1024 MiB; Constraints: 1 \le T \le 25000; 1 \le H,W; The sum of H \times W over all test cases in one input does not exceed 3 \times 10^5.; S_i is a string of length W consisting of # and ..
出典