あるマスから到達できるマスは、その中の他のマスから出発しても、同じ組み合わせに行き来できる。
■□■□ ❶①❷② ❶から出発して行けるマスを○にした □■□□ ③❸④□ □□■■ → □⑤❹■ ①②❷❸などから出発しても、同じ範囲に行けるし、同じ範囲にしか行けない □□■□ □□■□
その中で条件を満たす（黒マス、白マス）の組の個数は、「黒マスの個数×白マスの個数」となる。
左上から順に1マスずつ見ていき、まだ未探索のマスがあれば、そこから探索を開始する。黒・白マスの数を数えながら行けるところまで行き、それ以上どこにも行けなくなったら黒の数×白の数を答えに加算する。
一度探索したマスはそれ以降調べる必要は無い。
❶①❷② 済済済済 ③❸④□ 済済済□ ←次はここから探索スタート □⑤❹■ → □済済■ □□■□ □□■□
経路探索で使う「このマスは訪れたか？」のフラグ配列を、全探索で共有すればよい。これによって、十分間に合うようになる。
h, w = list(map(int, input().split()))
sss = ['x' * (w + 2)] + list('x' + input() + 'x' for _ in range(h)) + ['x' * (w + 2)]
checked = [[False] * (w + 2) for _ in range(h + 2)]
ans = 0
move = [(1, 0), (-1, 0), (0, 1), (0, -1)]
def dfs(i, j):
w_cnt, b_cnt = 0, 0
q = [(i, j, sss[i][j] == '.')]
while q:
y, x, is_white = q.pop()
if checked[y][x]:
continue
checked[y][x] = True
if is_white:
w_cnt += 1
else:
b_cnt += 1
for di, dj in move:
ni = y + di
nj = x + dj
if checked[ni][nj]:
continue
nc = sss[ni][nj]
if nc == 'x':
continue
elif (nc == '.') == is_white:
continue
else:
q.append((ni, nj, nc == '.'))
return w_cnt * b_cnt
for i in range(1, h + 1):
for j in range(1, w + 1):
if checked[i][j]:
continue
ans += dfs(i, j)
print(ans)
N = 10 A = 3 5 7 9 11 13 15 17 19 21 x = 10 のとき 先手: 21 19 17 15 5 → 77 後手: 9 11 7 13 3
まず、$x$ が小さい時から大きい時にどうなっていくかを考えると、上記の例を再利用して、
（カードを取る順番では無く、最終的に取ることになるカードを昇順に並べている） x = 1 のとき 先手: 13 15 17 19 21 後手: 3 5 7 9 11 x = 10 のとき 先手: 5 15 17 19 21 後手: 3 7 9 11 13 x = 13 のとき 先手: 5 9 17 19 21 後手: 3 7 11 13 15 x = 21 のとき 先手: 5 9 13 17 21 後手: 3 7 11 15 19
$x=1$ のとき綺麗に大小で2分割された状態から、数値が小さい方から順に交互になり始め、$x=21$ だと完全に交互になっている。
この変化する境界を探りたい。
そもそもなんで取るカードの組が変化するかというと（$x=1→10$ の変化を例に）$x$ がある程度大きくなると、後手はそれまで取っていた小さい方のカード（5）ではなく、先手が取っていた大きいカード（13）を先手より先に取るようになるから。
x = 10
先手: 15 17 19 21 (4手目まで)
後手: 7 9 11 (3手目まで)
場 : 3 5 13
~ ~~
xがある値未満までは5の方を先に取っていたが、
ある値以上では13の方を先に取るようになる
その境界は、ずばり5と13の中間である9である。（同率の場合は小さい方を取るため、x=9までは5を先に取る）
$x=10$ 以上では、先手が取る合計は $13-5=8$ だけ減少する。
これを繰り返して境界と、その境界での先手の合計点を確定できる。
ただし、どのカードが入れ替わるかに少し注意。
上の例を見ても分かるが、$A_i$ が小さい方から半分までのカードの中では、先手は、取るとしても大きい方から数えて奇数枚目のカードしか取らない（5,9を取り、3や7や11を取ることは無い）。取り方のルールから考えると、先手が半分以下のカードを取る時は、それより大きいカードが全て取られ、それ以下のカードが全て残っている状態だから。
なので、次に先手と後手で取るカードが入れ替わるのは、9と15である。その後、13と17、17と19と続く。要は入れ替わるカードの $i$ が、数字の小さい方は2つずつ、大きい方は1つずつ大きくなる。
変数$tmp$を、現在の境界での先手の合計とし、$x=1$の様に完全に2分された時の先手の合計点で初期化する。
クエリをソートしておく。その際、出力には元の順序が必要になるので、入力順は保持しておく。
最初に入れ替わるカードを特定する。後手→先手になるカードのindexを$l$とすると、$N$ が奇数なら$l=0$、偶数なら$l=1$。先手→後手になるカードのindexを$r$とすると、$r=\frac{N}{2}$。
境界を小さい方から1つ確定する。$\frac{A_l+A_r}{2}$ となる。$x$がこの値以下だと、先手の合計点は現在の$tmp$となる。
ソートしたクエリ配列で、境界以下の$X_i$を持つクエリまでポインタを進め（逆順ソート+pop()で実装）、それらのクエリの答えを$tmp$で確定する。その後、入れ替わるカードの値に基づいて $tmp$ を更新する。$tmp = tmp + A_l - A_r$
$l$ を2、$r$ を1加算し、$l=r$ になる直前まで繰り返す。
最後まで残ったクエリは、$x=21$の様に完全に交互になる。
ソートせずに、境界を事前計算しておいてクエリ毎に二分探索でもよいが、多分Pythonだと遅い。
import sys
n, q = list(map(int, input().split()))
aaa = list(map(int, input().split()))
xxx = sorted(((int(line), i) for i, line in enumerate(sys.stdin.readlines())), reverse=True)
total = sum(aaa)
tmp = sum(aaa[n // 2:])
ans = [sum(aaa[-1::-2])] * q
if n % 2 == 0:
l, r = 1, n // 2
else:
l, r = 0, n // 2
while l < r:
al, ar = aaa[l], aaa[r]
m = (al + ar) // 2
while xxx and xxx[-1][0] <= m:
x, i = xxx.pop()
ans[i] = tmp
if not xxx:
break
tmp += al - ar
l += 2
r += 1
print('\n'.join(map(str, ans)))
二乗の木DPというやつを使う。
今回は、条件が2つあり、それぞれに最適な切り方が異なるので、DP配列を2つ持つ。
ただし、$v$ を含む連結成分“以外”は、条件を満たすように切られているものとする。
$i$ の範囲の上限は、部分木のサイズとなる。
(B)では、連結成分の和が負にならないといけないので、辺を切った数が同じなら、和は出来るだけ低く保つのが常によい。
本来は(A)の場合は和は関係ないので、$i$ 本の時にできるかできないかのみ保持しておくだけでよかったらしい。
DPの中身の例
v以下の部分木の辺数が3なので、DP[v][i] は i=0..3 の値をとる
v →根
4 --- -7 --- 3 --- 5 ... DP1[v][0] = 不可 DP2[v][0] = 5
4 -|- -7 --- 3 --- 5 ... DP'1[v][1] = 不可 DP'2[v][1] = 1
4 --- -7 -|- 3 --- 5 ... DP'1[v][1] = 8 DP'2[v][1] = 8
4 --- -7 --- 3 -|- 5 ... × 切り方が条件を満たしていない
→ DP1[v][1] = 8 DP2[v][1] = 1
4 -|- -7 -|- 3 --- 5 ... DP'1[v][2] = 8 DP'2[v][2] = 8
4 -|- -7 --- 3 -|- 5 ... DP'1[v][2] = 5 DP'2[v][2] = 5
4 --- -7 -|- 3 -|- 5 ... DP'1[v][2] = 5 DP'2[v][2] = 5
→ DP1[v][2] = 5 DP2[v][2] = 5
4 -|- -7 -|- 3 -|- 5 ... DP1[v][3] = 5 DP2[v][3] = 5
DPの更新を楽にするため、「不可」を示す数を極端に大きな数(inf)とする。（頂点の和になり得ない数。全頂点が最大値の$10^9$であり、$N=5000$ なので、$5 \times 10^{12}$ より大きい数）
すると、上の例の DP1[v][1] のように、不可な切り方と可能な切り方が混在する場合でも、可能な切り方同士の時と同様 min を取ることで更新が行える。
葉頂点 $w$ の場合、1頂点のみなので次のようなDPとなる。
葉以外の頂点 $v$ の場合、次のように子供の結果と統合する。
まず、統合元を用意する。葉頂点と同じように作る。この時、暫定のDPを、$DP1'[v], DP2'[v]$ と表記することにする。
子を1つずつ統合する。子の1つを $u$ とし、$DP1[u], DP2[u]$ を $DP1'[v], DP2'[v]$ に統合する処理を考える。
これで欲しい情報が手に入った。
import sys
sys.setrecursionlimit(5005)
SENTINEL = 10 ** 13
n = int(input())
aaa = list(map(int, input().split()))
links = [set() for _ in [0] * n]
for line in sys.stdin.readlines():
u, v = map(int, line.split())
u -= 1
v -= 1
links[u].add(v)
links[v].add(u)
def dfs(v, p):
a = aaa[v]
ret1 = [a]
ret2 = [a]
if a < 0:
ret1[0] = SENTINEL
for u in links[v]:
if u == p:
continue
res1, res2 = dfs(u, v)
new1 = [SENTINEL] * (len(ret1) + len(res1))
new2 = [SENTINEL] * (len(ret2) + len(res2))
for i, t in enumerate(ret1):
for j, s in enumerate(res1):
new1[i + j] = min(new1[i + j], t + s)
if s < SENTINEL:
new1[i + j + 1] = min(new1[i + j + 1], t)
for j, s in enumerate(res2):
new2[i + j] = min(new2[i + j], t + s)
if s < 0:
new1[i + j + 1] = min(new1[i + j + 1], t)
for i, t in enumerate(ret2):
for j, s in enumerate(res1):
new2[i + j] = min(new2[i + j], t + s)
if s < SENTINEL:
new2[i + j + 1] = min(new2[i + j + 1], t)
for j, s in enumerate(res2):
new2[i + j] = min(new2[i + j], t + s)
if s < 0:
new2[i + j + 1] = min(new2[i + j + 1], t)
# print(' ', '1', p, v, u, ret1, res1, new1)
# print(' ', '2', p, v, u, ret2, res2, new2)
ret1, ret2 = new1, new2
return ret1, ret2
res1, res2 = dfs(0, -1)
ans = 0
for ans, (s1, s2) in enumerate(zip(res1, res2)):
if s1 < SENTINEL or s2 < 0:
break
print(ans)