CodeQUEEN 2025 予選 (AtCoder Beginner Contest 410) F,G問題メモ

CodeQUEEN 2025 予選 (AtCoder Beginner Contest 410)

F - Balanced Rectangles

問題文

$H \times W$ のグリッドが与えられ、各マスには # か . のどちらかが書かれています。
このグリッドに対し、以下の条件を全て満たす長方領域がいくつあるか求めてください。
- 長方領域に含まれる # が書かれたマスの個数と . が書かれたマスの個数が等しい。

厳密には、次の条件を全て満たす $4$ つの整数の組 $(u,d,l,r)$ の数を求めてください。
- $1 \le u \le d \le H$
- $1 \le l \le r \le W$
- グリッドのうち上から $u$ 行目から $d$ 行目、左から $l$ 列目から $r$ 列目の部分を取り出す。このとき、取り出した部分に含まれる # が書かれたマスの個数と . が書かれたマスの個数が等しい。

$T$ 個のテストケースが与えられるので、それぞれについて答えを求めてください。

制約

$1 \le T \le 25000$
$1 \le H,W$
ひとつの入力に含まれる $H \times W$ の総和は $3 \times 10^5$ を超えない。
$S_i$ は # と . からなる長さ $W$ の文字列である。

解法

「.」を $-1$ 、「#」を $+1$ に置換したグリッドで、矩形和が $0$ の矩形の数を求めればよい。

まず二次元累積和の表 $Acc$ を作る。
矩形和は、 $Acc$ において矩形の周囲の4点を足したり引いたりすることで求められる。

   l           ｒ
u  ＋          －    問題の表現とは違うが、ここでは
     ┌────┐    u+1行～d行、l+1列～r列 の矩形を、
     │        │    「u,d,l,r の矩形」と表現することとする
d  －└────＋

これをもう少し様々な矩形について一度に求めることを考える。

矩形の上端と下端 $(u, d]$ を固定する。
左端と右端 $(l,r]$ について、 $Acc[u,l]-Acc[d,l]-Acc[u,r]+Acc[d,r]=0$ なら答えに1加算される。
言い換えれば、 $D_{u,d}[j] :=Acc[u,j]-Acc[d,j]$ として、 $D_{u,d}[l]=D_{u,d}[r]$ ならよい。
これは Zero Sum Ranges の考え方で、以下のように効率的に求められる。

$D_{u,d}$ の各要素の個数を数える
ある値が $k$ 個出現したら、 $k(k-1)/2$ 個の同じ値のペアがある。 $D_{u,d}$ に出現する各値について求め、答えに加算する。

だが、ここからもう少し高速化の必要がある。
上記の方法で、2行を固定し、 $D$ を計算し、同じ要素毎の個数を愚直に数えた場合の計算量を考える。

$(u,d)$ を固定するのに $O(H^2)$ 。それごとに、
- $O(W)$ かけて $D$ を計算し
- $O(W \log{W})$ かけて、個数を数える

個数を数えるときにMapなどを使ってしまうと、log や定数倍がかかってしまい、全体 $O(H^2W \log{W})$ などとなる。
$O(H^2W)$ の部分は、必要なら転置して $H \le W$ としておくことで、 $O((HW)^{1.5}) \simeq 1.6 \times 10^8$ とできる。
処理が単純で定数倍が軽いことと、実行時間制約が3秒なことを加味すれば間に合わなくはないが、ここにさらに log がかかるのは厳しい。

差分更新する。
$(u,d)$ を計算したときの情報から、 $(u,d+1)$ の情報を求める。

$u$ を決め打つ。
$d=u+1,...,H$ について、答えへの寄与を求めていく。
- $C_k:=D_{u,d}$ のうち値が $k$ である要素の個数、とする数列 $C$ を用意
- $t:=D_{u,d}$ に含まれる同じ値のペア数、とする変数 $t$ を用意
初期値として、 $d=u$ の場合の値で初期化する。（※ $D_{u,u}$ は全要素が $0$ ）
- $C_0=W+1$ 、他 $C_i=0$
- $t=W(W+1)/2$
まず、 $d=u+1$ の時の答えへの寄与を求める。
- 列 $j=0,...,W$ について更新していく。 $D_{u,d-1}[j]=x$ から $D_{u,d}[j]=y$ に更新されたとすると、
  - $C_{x}-=1$
  - $t-=C_{x}$
  - $t+=C_{y}$
  - $C_{y}+=1$
- 以上を順におこなうと、更新が正しくおこなえる。
- 各 $j$ について1行分の更新が終わったら、その時の $t$ が $(u,d)$ を固定した時の寄与分である。
- これを $d=u+2,...,H$ まで繰り返す

これなら、logがつかず $O((HW)^{1.5})$ の計算量で済む。

Python3

        
          
          
              
              import os
import sys
 
import numpy as np
 
 
def solve(h, w, field):
    if h > w:
        h, w = w, h
        field = field.T.copy()
 
    acc = np.zeros((h + 1, w + 1), dtype=np.int64)
    for i in range(h):
        for j in range(w):
            acc[i + 1, j + 1] = acc[i + 1, j] + field[i, j]
    for j in range(w):
        for i in range(h):
            acc[i + 1, j + 1] += acc[i, j + 1]
 
    ans = 0
    counts = np.zeros((acc.max() - acc.min()) * 2 + 1, np.int64)
    for i1 in range(h):
        counts.fill(0)
        counts[0] = w + 1
        tmp = w * (w + 1) // 2
        for i2 in range(i1 + 1, h + 1):
            for j in range(w + 1):
                d0 = acc[i1, j] - acc[i2 - 1, j]
                d1 = acc[i1, j] - acc[i2, j]
                counts[d0] -= 1
                tmp -= counts[d0]
                tmp += counts[d1]
                counts[d1] += 1
            ans += tmp
    return ans
 
 
SIGNATURE = '(i8,i8,i8[:,:])'
if sys.argv[-1] == 'ONLINE_JUDGE':
    from numba.pycc import CC
 
    cc = CC('my_module')
    cc.export('solve', SIGNATURE)(solve)
    cc.compile()
    exit()
 
if os.name == 'posix':
    # noinspection PyUnresolvedReferences
    from my_module import solve
else:
    from numba import njit
 
    solve = njit(SIGNATURE, cache=True)(solve)
    print('compiled', file=sys.stderr)
 
t = int(input())
for _ in range(t):
    h, w = map(int, input().split())
    field = np.fromiter(
        (1 if c == '#' else -1 for _ in range(h) for c in input()),
        dtype=np.int64,
        count=h * w,
    ).reshape(h, w)
    ans = solve(h, w, field)
    print(ans)

            

        
      

G - Longest Chord Chain

問題文

円周上に $1$ から $2N$ の番号がついた相異なる $2N$ 個の点が時計回りに並んでいます。
この円の弦が $N$ 個与えられます。 $i$ 番目の弦の端点は点 $A_i$ と点 $B_i$ です。
- $2N$ 個の値 $A_1,\ldots,A_N,B_1,\ldots,B_N$ は相異なります。
この円に対し以下の操作を一度ずつ順に行います。
1. 円の $N$ 本の弦のうち、互いに交わらないように弦を好きな個数選び、残りの弦を削除する。
2. 円に自由に弦を $1$ つ追加する。

適切に操作を行ったとき、操作を終えた後の弦同士の交点の個数として考えられる最大値を求めてください。

制約

$1 \leq N \leq 2\times 10^5$
$1 \leq A_i,B_i \leq 2N$
$2N$ 個の値 $A_1, \ldots, A_N,B_1,\ldots,B_N$ は相異なる
入力は全て整数である

解法

とりあえず、円は点 $1$ と点 $2N$ の間で切り開く。（そうしてよい理由は後述）
$A_i \gt B_i$ の場合は入れ替えて $A_i \lt B_i$ とし、区間の問題と考える。

「弦が交わらない」というのは、「区間が交差しない」、つまり「一方の区間が一方の区間に完全に内包されている」か「全く交わらない」かのいずれかという条件になる。

また、操作の2つめ「弦を好きに1本追加する」というのは、新たな区間を1つ加えることに対応する。この追加した区間が、なるべく多くの区間と交差すればよい。（追加区間の両端は整数座標じゃなくても良い点に注意）

つまり、以下のような感じ。

既存区間  |------------------|  |------------|
            |-----------|         |--------|
               |----|               
追加区間          |---------------------|      5つの区間と交差できる

「なるべく多層的に、内包関係にある区間が重なっている箇所」を2つ、それぞれの最も広い区間が重なり合わないように取ってくれば、その重なり数の合計が答えとなる。

最初に、特に断り無く円を $1$ と $2N$ の間で切り開いたが、ある最適解があったとして、切り開く位置をどこにとってもそこで分断される区間は 2つの山の一方からもう一方に移せることから、答えが変わらないことがわかる。

              v ここに切り開く位置を変えても大丈夫
|--------A---------|  |-----D------|
    |----B------|       |---E----|
       |-C--|
                    ↓

       |-C--|   |-----------B-------------/     /: 1周後の区間端
                   |--------A---------/
                      |-----D------|
                        |---E----|

区間に「レベル」を定義する。

$Lv[i]$ : 区間 $i$ に完全に内包される区間のうち、レベル最大のもの + 1
内包される区間が無いものは $1$

これは、先ほどの“重なり数”の概念と一致する。多く内包する区間ほどレベルが高い。
求め方は、セグメント木を使って以下のようにするとできる。

区間右端 $B_i$ でソートする。この順に、以下を処理する。
- $[A_i,B_i)$ の区間最大値をとる。 $Lv[i]=$ 区間最大値 $+1$ である。
- セグメント木の $A_i$ の位置の値を $Lv[i]$ とする。

あとは、一方の区間を固定しながら、それと重なり合わないもう一方のレベル最大値を取得していけば求められる。

$Ans = \max_i(Lv[i] + (セグ木の [B_i+1, 2N) の区間最大値))$

計算量は $O(N \log{N})$

Python3

$(A_i,B_i)$ の他に $(B_i,A_i+2N)$ という区間も作り、 $[0,4N)$ の範囲で同じことをやると、山を2つとか考えずとも、単にレベルの最大値が答えとなる。こちらの方が楽かも。