読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

CodeChef SnackDown Online elimination round

CodeChef 永続セグメント木 Wavelet Matrix O(√n) 動的計画法

https://www.codechef.com/SNCKEL16

VCake

場合分け。

gist.github.com

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 で収まる。

gist.github.com

Coloring A Tree

  • dp[iの部分木][j個の連結成分をもつ]:=パターン数

として木 DP。x個の連結成分をもつ森とy個の連結成分がある森を繋げるとx+y-1個の連結成分がある森になって、繋げないとx+y個の連結成分をもつ森になる、ということを使って数え上げていく。

k-1 本の辺を切れば k 個の連結成分ができるので、m 本の辺から k-1 本を選ぶ場合の数を計算するだけで良かったらしい。

gist.github.com

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] みたいに全部同じ方向に移動されると困るのだが、これが絶対値の最小値になることはないので問題ない。

gist.github.com

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。

gist.github.com

Yet Another SubSegment Sum Problem

https://www.codechef.com/problems/SEGSUMQ

A[i]C[j]-B[i]D[j] は有理数外積っぽいので全順序である。そのため (C[j],D[j]) 未満の要素だけを使った区間総和セグメント木を作っておけばいい。

愚直に N 個セグメント木を作るのは難しい。こういうときは永続化してノードの大半を使い回せばいい。

gist.github.com

wavelet matrix を使えば永続は不要。提出してないので AC するか分からないけど、手元のランダムケースでは異常がなかったので大丈夫かな。

(追記:2016/06/22) 通った。案の定(0,0)の処理を間違えていた。

gist.github.com

6完したが上手くない解き方ばかりしていた気がする。