CodeChef May Challgenge 2016: 1-7問目

Laddu

問題文通りに実装する。

https://gist.github.com/pekempey/79737202a7f4a68bff7efe5ac7064133

Chef and Balls

両側に同じボールを乗せるのは意味が無いし、片側に 1 1 2 2 と置いてしまうと 1 と 2 の区別がつかなくなるので、左に 1 1 2、右に 3 3 4 かな。実際これで判別可能。

https://gist.github.com/pekempey/b2ed180c459b47010a26e77dd239528b

Forest Gathering

こまめに切るよりまとめて切った方がお得。x 日目に全部切って目的の量に達するかを二分探索すればいい。オーバーフローが面倒なので PyPy で通した。

https://gist.github.com/pekempey/1252051315a10e8d492cf8e674f5e43b

Chef and Big Soccer

  • dp[ 投げた回数 ][ ボールの位置 ] := パターン数

として動的計画法。

https://gist.github.com/pekempey/4288082c5a8600fc5df7ac65157319f4

Chef and math

mod 109+7 はハッタリで、多分パターン数は多くない。枝刈り全探索で十分。

https://gist.github.com/pekempey/0645c0d881be7376a45468e7db8ede31

Sereja and GCD 2

  • 重複する値があってはならない（1 を除く）
  • 50 以下の素数の個数は 15 個

ということを用いて次のような DP をする。

  • dp[ 整数 i まで使って良い ][ j 個使った ][ 使った素数のビットマスク ] := パターン数

ただしこの DP は重い。そこで sum[i][j] = dp[i][j][*] を埋め込んだ。

長さ n になるまで 1 を付け足して、並び替えも考慮してあげれば答えが求まる。

https://gist.github.com/pekempey/65d48ff0da9e78d9761c53b2fa4cfdac

Chef and Amazingness of Numbers

xor 値が x となるような部分列を持つ整数の数を数え上げるために次のような DP をする。

  • dp[ i 桁目まで割り当てた ][ more ][ less ][ 既に x が現れている ][ i 番目を末尾とする部分列の xor 値のビットマスク ] := パターン数

これを x=1..15 に対して計算すれば答えが得られる。ただしこの DP は重いので定数倍高速化が必要。

https://gist.github.com/pekempey/05caf88f7b742c4016118be30be3d7eb

多少雑な解法もあるけど、ここまでは順調。