ACPC 2020 Day3
コンテストサイト
Aizu Online Judge Arena
解説
kaisetu - Google ドライブ
A
東西方向と南北方向は独立に計算していい。斜め移動の必要はない。Day2 に比べると問Aの難易度が上がっている
B
a(l+1) + ... + a(r) を累積和で求めることができる
C
dp[i][j] := a(i) までをチェックして和がdp[i][j] * K + j 存在するならば、その時のdp[i][j]の最大値 dp[i+1][(j+a(i)) % K] < dp[i][j] + (j + a(i)) / K ならば update
D
例えばM = 6 のとき、一度2になれば3にはなれないし、3になれば2にはなれない。
考察
- d を M の約数とする。一度dの倍数を書けるとその後ずっとdの倍数
- M の異なる二つの素因数p, qがあると、同時に達成できない
- M が素数pの冪 p^k の時 (k>=1)
- pの倍数でない数にすべて到達する必要がある
- k = 1 のとき、数列aは少なくとも1つ、pの倍数を含む必要がある
- k > 1 のとき、「pの倍数でない数」「pの倍数だがp^2の倍数でない数」「p^2の倍数だがp^3の倍数でない数」…の順に到達する必要がある。結局は少なくとも1つ p の倍数だがp^2の倍数でない数を含む必要がある
よって、素因数分解し、BFS等で到達判定する。到達できるならば一筆書きもできる
E
またMODだ
a(i) で剰余を取ると a(i) 未満になる。よって a(i) から狭義単調減少になる要素だけ取り出しておく。
各 b(j) について独立に求める。現在のb(j) 以下の a(i) で最大の物で剰余を取る、この操作を繰り返す。aを単調にしているので二分探索で求めることができる。
また、剰余を取るとb(j) の値は b(j) / 2 未満になるので、この繰り返しの回数は大きくならない
F
高さ i の木に長さ 2i のリボンを置くと、
- その置き方は2つの葉の選び方 : pow(2, i-1)*pow(2, i-1) == pow(4, i-1)
- 高さが 0, 1, 2, ..., i-2 の木が 2 つずつ残る
長いリボンから置く。残りの木の数が変化を配列に足す。
G
bit DPを高速化する問題。
隣り合うa(i), a(i+1) をグループ化して数えると O(m^2) 通りに減る。
cost(mask, v) := 「maskに含まれる花、v、それ以外の花」の順に花を並べたときに v に水をやる回数
O(M^3) で cost(mask, v) の適切な位置に足し引きして、高速ゼータ変換で総計する。
cost を用いて、bit DP
