AtCoder Beginner Contest 207 D,E,F問題メモ
D - Congruence Points
問題
解法
$S,T$ から1点ずつ取り出して「この2点が一致するように操作するとき、他の点も一致するか」を考えるだけだと、平行移動と回転角度の組合せが一意に決まらない。
$S,T$ から2点ずつ取り出すと(どっちをどっちに対応させるかで2通りあるが)一意に決まる。
しかしそれでは、他の点が正しいかのチェックも合わせると $O(N^4)$ とかになってしまい、間に合わない。
まず平行移動
平行移動と回転移動は、
「回転移動の後に平行移動すると可能な配置だが、平行移動の後に回転移動では絶対になり得ない」みたいなのは存在しないので、
どちらも高々1回で済むと考えてよい。
また、$S$ だけを操作するのでなく、$T$ も操作して $S$ に寄せていくと考えても判定には影響ない。
2つの操作で変わらないものといえば、「重心と各点との位置関係」がある。
$S,T$ で $N$ 点の重心をそれぞれ取って、平行移動で原点に持ってくれば、後は回転移動だけで一致(可能なら)させられる。
これで1点同士の対応関係に持ち込める。
回転移動で判定
重心を原点に移動した点集合を $S',T'$ とする。
$S'_1$ と対応させるのを $T'_i$ と固定すると、回転させるべき角度が決まる。
その角度で $S'$ の他の点も回転させて、$T'$ と一致するか判定すればよい。
判定の方法は愚直でよい。
つまり、$S'_1~S'_N$ の回転移動後の座標を求め、
それぞれにつき $T'$ に許容誤差を満たす点があるか探すとよい。
制約が小さいので、小数のまま計算しても誤差はまず心配ない。
1つの $S'_i$ が2つ以上の $T'$ と近くなったり、その逆、ということは発生しないと思うが、
不安ならカウントしてちゃんと1対1対応になっているか調べてもよい。
計算量
判定の高速化
平行移動後、$S',T'$ の各点を偏角でソートすると両者で対応させるべき点が順に並ぶので、
どの位置から一致を確認していくかさえ決めれば判定を $O(N)$ にできる……のだが。
重心と一致する点があった場合、偏角が定義できず予測できない値となるため、
その点だけは取り除いておかないとソート位置がずれる点に注意。
また公式Editorialによると、
偏角と原点からの距離でソートした上で (偏角1, 距離1, 偏角2, 距離2, …) という数列にそれぞれ変換してやると、
文字列検索に用いられる Z-Algorithm などが使えて、どの位置から一致するかを含めて $O(N)$ で判定可能となる。
Python3
from math import atan2
def solve(n, ab, cd):
if n <= 2:
return True
ga, gb = 0, 0
for a, b in ab:
ga += a
gb += b
gc, gd = 0, 0
for c, d in cd:
gc += c
gd += d
ga /= n
gb /= n
gc /= n
gd /= n
abg = [(a - ga, b - gb) for a, b in ab]
cdg = [(c - gc, d - gd) for c, d in cd]
abt = []
cdt = []
ab0 = False
cd0 = False
eps = 1e-6
for a, b in abg:
ang = atan2(a, b)
dst = a * a + b * b
if abs(dst) > eps:
abt.append((ang, dst))
else:
assert ab0 == False
ab0 = True
for c, d in cdg:
ang = atan2(c, d)
dst = c * c + d * d
if abs(dst) > eps:
cdt.append((ang, dst))
else:
assert cd0 == False
cd0 = True
if ab0 != cd0:
return False
abt.sort()
cdt.sort()
pi = 6.28318530718
m = len(abt)
for i in range(m):
dt = cdt[i][0] - abt[0][0]
for di in range(m):
dj = (i + di) % m
if abs(cdt[dj][1] - abt[di][1]) > eps:
break
dt2 = cdt[dj][0] - abt[di][0]
if abs(dt2 - dt) > eps and abs(dt2 - dt + pi) > eps and abs(dt2 - dt - pi) > eps:
break
else:
return True
return False
n = int(input())
ab = [tuple(map(int, input().split())) for _ in range(n)]
cd = [tuple(map(int, input().split())) for _ in range(n)]
if solve(n, ab, cd):
print('Yes')
else:
print('No')
E - Mod i
問題
長さ $N$ の数列 $A_1,A_2,...,A_N$ が与えられる
以下の条件を全て満たすように、先頭から順に空でない連続する部分列に切り分ける
切り分け方の総数を $\mod{10^9+7}$ で求めよ
$1 \le N \le 3000$
解法
3乗DP
まず3乗DPは比較的素直に構築できる。
もらうDPで考えたとき、$A_{j+1}~A_i$ が $k$ の倍数になる場合のみ、以下のように遷移できる。
i 0 1 2 3 4 5 6 7 8 9 10
A 3 1 4 1 5 9 2 6 5 3 5 ...
区切り方の一例
番号 | 1 | 2 | 3 | 4 |
総和 | 3 | 22 | 6 | 8 |
他の例
番号 | 1 | 2 | 3 | 4 |
総和 | 4 | 4 | 15 | 16 |
例えば A9=3 が k=4 個目の部分列の終端となるには、
i=9から遡って累積和が4の倍数となるところから区間が始まる必要がある。
→その直前までを3個の区間に分割するパターン数が加算される
5+3 = 8 なので、DP[7][3] から遷移できる
2+6+5+3 = 16 なので、DP[5][3] から遷移できる
1+4+1+5+9+2+6+5+3 = 36 なので、DP[0][3] から遷移できる
→ DP[9][4] = DP[7][3] + DP[5][3] + DP[0][3]
だが、これだと各 $i,k$ につき $j$ の位置を全探索しないといけないので、$O(N^3)$ となる。
計算量改善
その1
公式Editorialで直感的にわかりやすいのは、kyopro_friends氏のものかと思う。
上の例で $DP[9][4]$ を求めたいとき、以下の情報を求めておけば、
この場合は $j=7$ となるが、それより前で累積和が $4$ の倍数になる $j=5$ や $j=0$ で区切ったパターンは、実は $DP[7][4]$ に既に含まれている。
だから更新は $DP[7][3]+DP[7][4]$ でいいよね、ということ。
わかれば単純なものの、気付くのは結構難しいかも知れない。
Python3
import os
import sys
import numpy as np
def solve(inp):
n = inp[0]
aaa = inp[1:]
MOD = 10 ** 9 + 7
last_multiplies = np.zeros((n + 1, n + 1), np.int64)
acc = np.zeros(n + 1, np.int64)
acc[1:] = aaa.cumsum()
for k in range(1, n + 1):
last = np.full(k, -1, np.int64)
for i in range(n + 1):
m = acc[i] % k
last_multiplies[i, k] = last[m]
last[m] = i
dp = np.zeros((n + 1, n + 1), np.int64)
dp[0, 0] = 1
max_division = 0
for i in range(1, n + 1):
for k in range(1, max_division + 1):
lm = last_multiplies[i, k]
if lm != -1:
dp[i, k] = (dp[lm, k - 1] + dp[lm, k]) % MOD
lm = last_multiplies[i, max_division + 1]
if lm != -1:
tmp = (dp[lm, max_division] + dp[lm, max_division + 1]) % MOD
if tmp > 0:
dp[i, max_division + 1] = tmp
max_division += 1
return dp[n, :].sum() % MOD
SIGNATURE = '(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)
inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print(ans)
その2
$A$ の先頭からの累積和を $C$ とする。
というのはよく出てくる言い換えである。
DPの更新にこれを適用すると、$DP[i][k]$ は、
$C_i$ と $C_j$ を $k$ で割ったあまりが等しいような $j$ について、$DP[j][k-1]$ の総和である。
再び上の例を使うと、
DP[5][4] = DP[0][3]
DP[7][4] = DP[0][3] + DP[5][3]
DP[9][4] = DP[0][3] + DP[5][3] + DP[7][3]
このように、$i$ が進むにつれ、同じグループの中ではそれまでの参照箇所は変わらず、新しいのが追加されていくことになる。
このグループごと、つまり ($k$, $C_i$ を $k$ で割ったあまり) ごとにDPの結果を合計しておけば、
必要な値がすぐに取り出せるようになる。
$DP[i][k]$ について求める際、
と、高速な更新が可能となる。
F - Tree Patrolling
問題
$N$ 頂点の木が与えられる
ある頂点に監視員を置くと「その頂点」と「それに隣接する頂点」を監視してくれる
監視員の置き方は $2^N$ 通りあるが、少なくとも1人の監視員に監視される頂点数が $k$ 個となる置き方の個数を知りたい
$k=0,1,...,N$ のそれぞれについて $\mod{10^9+7}$ で求めよ
$1 \le N \le 2000$
解法
木DPで、適当に根を決めて子の情報を統合していけばよさそう。シンプルなのは以下が思いつく。
だがこれだと情報が足りない。
このあたりを区別するには、以下の情報を追加する。
ここまではわかっても、いざ子の情報を統合するのも結構難しい。
たたみ込みの要領で行うのだが、その前後でちょっと加工してやる必要がある。
統合の基本処理
$f$ のことは簡単のために一旦無視する。情報が足りない方のDPで説明する。
$v$ の2つの子 $u_1,u_2$ を統合する処理を考える。(数値は適当)
k 0 1 2 3
DP[u1] [ 1 3 5 2 ]
DP[u2] [ 1 0 2 ]
すると、$v$ にとって(自身を除いて)監視されている頂点数がたとえば3個になるような場合の数は、
などとなり、これらを合計したものなので、
DP[u1][0]*DP[u2][3] + DP[u1][1]*DP[u2][2] + DP[u1][2]*DP[u2][1] + DP[u1][3]*DP[u2][0]
という要領で、たたみ込みになっている。
最初に $DP[v]= [1]$ と初期化して、これをベースにそれぞれの子をたたみ込んでいくとよい。
実際にはここに、子の状態 $f$ による場合分け、$v$ にも監視員を置くかの場合分けが入る。
①$f=0$ の更新
$v$ に監視員は置かれず、監視されてもいけない。
子に監視員が置かれたパターン($f=2$)は使えないが、$f=0,1$ であれば
それぞれの子がどちらであってもよく、子同士も干渉しない。
つまり、子 $u$ ごとに以下を計算して、これでたたみ込みを行ったものとなる。
※$DP[u][0]$ などは1次元配列を表していて、配列同士の $+,-$ の演算は要素毎の和、差を表すとする
②$f=1$ の更新
$v$ に監視員は置かれないが、少なくともどれか1つの子に監視員が置かれている。
これは、「どの子にも監視員が置かれていない」という①の余事象なので、
でのたたみ込みを計算すると、全ての子を統合した後で「(B)の結果 - (A)の結果 を計算し、最後に1つ右シフト」したものが $DP[v][1]$ となる。
右シフトは、たたみ込みの結果に $v$ 自身が考慮されていないため、それを考慮するための操作となる。
③$f=2$ の更新
$v$ に監視員を置くことによって、
子 $u$ のうち、$u$ 自身が監視されていない状態のもの($f=0$)があれば、新たに監視されるようになる。
つまり、$DP[u][0][k]$ を $DP[u][0][k+1]$ と見做して扱えばよい。
これでたたみ込みを行い、最後に1つ右シフトしたものが、$DP[v][2]$ となる。
計算量
子を1つ統合するたびに3パターンのたたみ込み計算が必要となる。
統合する2つのDPテーブルのサイズを $L,R$ とすると統合に $O(LR)$ かかり、
それを $N$ 個の頂点で行うので、、、なんとなく $O(N^3)$ になりそうで間に合わない!
これは、2乗の木DPと呼ばれる計算量見積もりに関する知識で、以下の場合に
要素数が小さい内は統合の計算量も小さいので、全体で $O(N^2)$ で済むよ、という証明が出来る。
この方法が使用できる。
Python3
import os
import sys
import numpy as np
def solve(inp):
def simple_convolution(aaa, bbb, MOD):
n = len(aaa)
m = len(bbb)
result = [0] * (n + m - 1)
for i in range(n):
for j in range(m):
result[i + j] = (result[i + j] + aaa[i] * bbb[j]) % MOD
return result
n = inp[0]
int_list = [n]
int_list.pop()
links = [int_list.copy() for _ in range(n)]
for i in range(n - 1):
u = inp[2 * i + 1] - 1
v = inp[2 * i + 2] - 1
links[u].append(v)
links[v].append(u)
dp0 = [int_list] * n
dp1 = [int_list] * n
dp2 = [int_list] * n
MOD = 10 ** 9 + 7
status = np.zeros(n, np.int8)
q = [0]
while q:
v = q[-1]
if status[v] == 0:
status[v] = 1
for u in links[v]:
if status[u] == 0:
q.append(u)
else:
q.pop()
status[v] = 2
cdp01 = [1] # 子のDPの0,1をあわせてたたみ込んだもの
cdp012 = [1] # 子のDPの0,1,2をあわせてたたみ込んだもの
cdp0_12 = [1] # 子のDPの0をシフトした上で1,2とあわせてたたみこんだもの
for u in links[v]:
if status[u] != 2:
continue
tdp01 = [0] * max(len(dp0[u]), len(dp1[u]))
tdp012 = [0] * max(len(dp0[u]), len(dp1[u]), len(dp2[u]))
tdp0_12 = [0] * max(len(dp0[u]) + 1, len(dp1[u]), len(dp2[u]))
for i, t in enumerate(dp0[u]):
tdp01[i] += t
tdp012[i] += t
tdp0_12[i + 1] += t
for i, t in enumerate(dp1[u]):
tdp01[i] += t
tdp012[i] += t
tdp0_12[i] += t
for i, t in enumerate(dp2[u]):
tdp012[i] += t
tdp0_12[i] += t
for i in range(len(tdp01)):
tdp01[i] %= MOD
for i in range(len(tdp012)):
tdp012[i] %= MOD
for i in range(len(tdp0_12)):
tdp0_12[i] %= MOD
cdp01 = simple_convolution(cdp01, tdp01, MOD)
cdp012 = simple_convolution(cdp012, tdp012, MOD)
cdp0_12 = simple_convolution(cdp0_12, tdp0_12, MOD)
for i in range(len(cdp01)):
cdp012[i] = (cdp012[i] - cdp01[i]) % MOD
cdp012.insert(0, 0)
cdp0_12.insert(0, 0)
while cdp012 and cdp012[-1] == 0:
cdp012.pop()
dp0[v] = cdp01
dp1[v] = cdp012
dp2[v] = cdp0_12
ans = np.zeros(n + 1, np.int64)
for i, t in enumerate(dp0[0]):
ans[i] += t
for i, t in enumerate(dp1[0]):
ans[i] += t
for i, t in enumerate(dp2[0]):
ans[i] += t
return ans % MOD
SIGNATURE = '(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)
inp = np.fromstring(sys.stdin.read(), dtype=np.int64, sep=' ')
ans = solve(inp)
print('\n'.join(map(str, ans)))