AtCoder Beginner Contest 207 D,E,F問題メモ

AtCoder Beginner Contest 207

総合的になかなか高難易度の回だった。

D - Congruence Points

不必要な高速化をしてコーナーケースに引っかかる、あると思います。

問題

2次元平面上の点の集合 $S,T$ があり、ともに要素数は $N$
- $2N$ 個の各点の座標は与えられる
以下の2つの操作を好きなように繰り返して、$S$ を $T$ に一致させられるか判定せよ
- 全点一斉に $(dx,dy)$ だけ平行移動
- 全点一斉に原点を中心に角度 $r$ だけ回転
$1 \le N \le 100$
$-10 \le 各点の座標 \le 10$
入力は全て整数

解法

$S,T$ から1点ずつ取り出して「この2点が一致するように操作するとき、他の点も一致するか」を考えるだけだと、平行移動と回転角度の組合せが一意に決まらない。

$S,T$ から2点ずつ取り出すと（どっちをどっちに対応させるかで2通りあるが）一意に決まる。
しかしそれでは、他の点が正しいかのチェックも合わせると $O(N^4)$ とかになってしまい、間に合わない。

補足: 取り出した2点の距離が一致していないとその時点でアウトなので、実際にチェックが走る数が絞られることを考えると、間に合うみたい
- 解説 - AtCoder Beginner Contest 207

まず平行移動

平行移動と回転移動は、「回転移動の後に平行移動すると可能な配置だが、平行移動の後に回転移動では絶対になり得ない」みたいなのは存在しないので、どちらも高々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対応になっているか調べてもよい。

計算量

事前計算の重心計算と平行移動に $O(N)$
$S'_1$ をどれと対応づけるかで $O(N)$、その判定で $O(N^2)$

全体で $O(N^3)$ で、十分間に合う。

判定の高速化

平行移動後、$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$ が与えられる
以下の条件を全て満たすように、先頭から順に空でない連続する部分列に切り分ける
- $i$ 番目の部分列の総和は $i$ で割り切れる
切り分け方の総数を $\mod{10^9+7}$ で求めよ
$1 \le N \le 3000$

解法

3乗DPを、観察や発想で2乗DPに落とす。

3乗DP

まず3乗DPは比較的素直に構築できる。

$DP[i][k]=A_i$ までを $k$ 個の部分列に分けるパターン数

もらうDPで考えたとき、$A_{j+1}～A_i$ が $k$ の倍数になる場合のみ、以下のように遷移できる。

$DP[i][k] += DP[j][k-1]$

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氏のものかと思う。

解説 - AtCoder Beginner Contest 207

上の例で $DP[9][4]$ を求めたいとき、以下の情報を求めておけば、

$i=9$ より前で一番直近の、$i=9$ から遡った累積和が $k=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$ とする。

ある区間 $(l,r]$ の和が $k$ で割り切れる $\Longleftrightarrow$ $C_l$ と $C_r$ を $k$ で割ったあまりが等しい

というのはよく出てくる言い換えである。

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の結果を合計しておけば、必要な値がすぐに取り出せるようになる。

$SUB[k][m]=$ 今までの時点で、$C_i$ を $k$ で割ったあまりが $m$ であるような $i$ についての $DP[i][k]$ の総和

$DP[i][k]$ について求める際、

$DP[i][k]$ は、その時点の $SUB[k][C_i \% k]$ に入っている値
$SUB[k+1][C_i \% (k+1)]$ に $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で、適当に根を決めて子の情報を統合していけばよさそう。シンプルなのは以下が思いつく。

$DP[v][k]=$ 頂点 $v$ 以下の部分木で、監視されている頂点数が $k$ 個となるパターン数

だがこれだと情報が足りない。

$v$ に監視員を置いたとき、子が監視されてないなら新たに監視されることになるが、既に監視されていたなら増えない
$v$ に監視員を置かないとき、監視員の置かれた子が1つでもあれば、$v$ も監視される

このあたりを区別するには、以下の情報を追加する。

$DP[v][f=0/1/2][k]=$ 頂点 $v$ 以下の部分木で、状態が $f$ で、監視されている頂点数が $k$ 個となるパターン数
- $f=0$: $v$ に監視員が置かれておらず、監視されてもいない
- $f=1$: $v$ に監視員が置かれていないが、子に置かれた監視員より監視されている
- $f=2$: $v$ に監視員が置かれている（当然監視もされている）

ここまではわかっても、いざ子の情報を統合するのも結構難しい。
たたみ込みの要領で行うのだが、その前後でちょっと加工してやる必要がある。

統合の基本処理

$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個になるような場合の数は、

$u_1$ から1個、$u_2$ から2個持ってきた場合
- $DP[u_1][1] \times DP[u_2][2] = 3 \times 2 = 6$
$u_1$ から2個、$u_2$ から1個持ってきた場合
- $DP[u_1][2] \times DP[u_2][1] = 5 \times 0 = 0$

などとなり、これらを合計したものなので、

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$ ごとに以下を計算して、これでたたみ込みを行ったものとなる。

(A) $DP[u][0] + DP[u][1]$

※$DP[u][0]$ などは1次元配列を表していて、配列同士の $+,-$ の演算は要素毎の和、差を表すとする

②$f=1$ の更新

$v$ に監視員は置かれないが、少なくともどれか1つの子に監視員が置かれている。

これは、「どの子にも監視員が置かれていない」という①の余事象なので、

(B) $DP[u][0] + DP[u][1] + DP[u][2]$

でのたたみ込みを計算すると、全ての子を統合した後で「(B)の結果 - (A)の結果を計算し、最後に1つ右シフト」したものが $DP[v][1]$ となる。

右シフトは、たたみ込みの結果に $v$ 自身が考慮されていないため、それを考慮するための操作となる。

③$f=2$ の更新

$v$ に監視員を置くことによって、子 $u$ のうち、$u$ 自身が監視されていない状態のもの（$f=0$）があれば、新たに監視されるようになる。

つまり、$DP[u][0][k]$ を $DP[u][0][k+1]$ と見做して扱えばよい。

(C)「$DP[u][0]$ を1つ右シフトしたもの」$+DP[u][1]+DP[u][2]$

これでたたみ込みを行い、最後に1つ右シフトしたものが、$DP[v][2]$ となる。

計算量

子を1つ統合するたびに3パターンのたたみ込み計算が必要となる。

統合する2つのDPテーブルのサイズを $L,R$ とすると統合に $O(LR)$ かかり、それを $N$ 個の頂点で行うので、、、なんとなく $O(N^3)$ になりそうで間に合わない！

これは、2乗の木DPと呼ばれる計算量見積もりに関する知識で、以下の場合に

各頂点が持つDPテーブルのサイズは、その頂点の部分木のサイズに比例
子を統合する際にかかる計算量は、全ての子の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)))

目次

AtCoder Beginner Contest 207 D,E,F問題メモ

D - Congruence Points

問題

解法

まず平行移動

回転移動で判定

計算量

判定の高速化

E - Mod i

問題

解法

3乗DP

計算量改善

その1

その2

F - Tree Patrolling

問題

解法

統合の基本処理

①$f=0$ の更新

②$f=1$ の更新

③$f=2$ の更新

計算量