CodeChef SnackDown Online elimination round
https://www.codechef.com/SNCKEL16
VCake
場合分け。
Chocolates for Everyone
$na+dn(n-1)/2=c$となる$a,d\ge1$が存在するかを判定したい。一次不定方程式$ax+by=c$の一般解は、特殊解を$x_0,y_0$としたとき$x=x_0+bk,y=y_0-ak$。特殊解は extgcd で得られる。
一般解が求まれば不等式をたてて判定可能。
extgcd で得られる$ax+by=c$の解は$|x|\le bc,|y|\le ac$ なので、このままだと解がオーバーフローしかねない。そこで $2a+(n-1)d=2c/n$に変形する。これなら $|x|\le 2c(n-1)/n \le 2c,|y|\le 4c/n$ となり long long で収まる。
Coloring A Tree
- dp[iの部分木][j個の連結成分をもつ]:=パターン数
として木 DP。x個の連結成分をもつ森とy個の連結成分がある森を繋げるとx+y-1個の連結成分がある森になって、繋げないとx+y個の連結成分をもつ森になる、ということを使って数え上げていく。
k-1 本の辺を切れば k 個の連結成分ができるので、m 本の辺から k-1 本を選ぶ場合の数を計算するだけで良かったらしい。
Robot Walk
入力の L,R はどうでも良くて、a[i] だけ見ればいい。移動後に左右どちらかにかならず回転するため、偶数番目の a[i] は x 方向に、奇数番目の a[i] は y 方向にしか関与しない。また各 a[i] を + に作用させるか - に作用させるかも自由に選べる。
適当に回転をさせた結果、最終的な x 座標が +p になったとする。回転方法が確定しているため、少なくとも p 回移動量を変更しなければ原点に戻せない。-方向の移動を p 増やせば原点に戻せる。つまり最終的な位置の絶対値が p なら最小コストは p である。
以上の考察から、a[0]+a[2]-a[4]とかa[0]-a[2]-a[4]みたいに符号を工夫して絶対値を最小化する問題を解けばいいことが分かる。これは「dp[i][j]:=i番目まで使って和を j にできるか」という DP を bitset で高速化すれば解ける。
a[0]+a[2]+a[4] みたいに全部同じ方向に移動されると困るのだが、これが絶対値の最小値になることはないので問題ない。
Jealous Numbers
√1000 以下の素数は 11 個しかないことを使う。
まず a[i] を
- S=√1000 以下の素因数のみで構成される
- L(p)=√1000 より大きい素因数 p をもつ
というグループに分類する。√1000 より大きい素因数を 2 つ以上含むことはないため、S と各 L(p) は共通部分を持たない。こうすることで次のような DP ができるようになる。
- dp[ √1000 以下の素数のビットマスク ] := 最大個数
S はそのまま DP。L(p) は L(p) の要素を同時に 2 個以上使わないように DP。
Yet Another SubSegment Sum Problem
https://www.codechef.com/problems/SEGSUMQ
A[i]C[j]-B[i]D[j] は有理数や外積っぽいので全順序である。そのため (C[j],D[j]) 未満の要素だけを使った区間総和セグメント木を作っておけばいい。
愚直に N 個セグメント木を作るのは難しい。こういうときは永続化してノードの大半を使い回せばいい。
wavelet matrix を使えば永続は不要。提出してないので AC するか分からないけど、手元のランダムケースでは異常がなかったので大丈夫かな。
（追記：2016/06/22) 通った。案の定(0,0)の処理を間違えていた。
6完したが上手くない解き方ばかりしていた気がする。
