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

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は比較的素直に構築できる。

• $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)$ となる。

公式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

$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$ にも監視員を置くかの場合分けが入る。

$v$ に監視員は置かれず、監視されてもいけない。

子に監視員が置かれたパターン（$f=2$）は使えないが、$f=0,1$ であれば それぞれの子がどちらであってもよく、子同士も干渉しない。

つまり、子 $u$ ごとに以下を計算して、これでたたみ込みを行ったものとなる。

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

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

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

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

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

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

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

$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)$ で済むよ、という証明が出来る。

• 二乗の木 DP - (iwi) ｛ 反省します - TopCoder部
• 木と計算量 前編 〜O(N^2)とO(NK)の木DP〜 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ

この方法が使用できる。

Python3