Codeforces #399 E: Game of Stones
ニムのルールを少し変えたゲームの勝敗を知りたい。石の山の状態の数とその状態の遷移の数が十分小く表せれば、Grundy数やるだけ。
山の状態を適切に表したい。愚直に考えれば
山の状態=(石の個数, 1~60のうち取り除いたことのある個数についてのフラグ)
たとえば
s[0] = 10としよう。
この山の状態は
(10, まだ石を取り除いていない)
であり、ここから石を4個取ると
(10-4, 石を4個取り除いたことがある)
この状態からもう一度石を4個取り除くことはできない。
更に石を2個取り除いてみると
(10-4-2, 石を4個、2個取り除いたことがある)
このとき石の山からは4個も2個も取り除くことはできない。
このあと石の山から1個、3個取り除けば状態は
(0, 石を4個、２個、１個、３個取り除いたことがある)
となり、このときGrundy数は0
s[i]<=60より、取り除いたことのある石の個数のフラグは、ビット数から2^60通り。だが、実際にあり得る状態の数は十分少ない。説明する。
取り除いたことのある石の数の集合をTとする。たとえば先の例では最終的に、T={1,2,3,4}となっていた。
山に含まれる石の個数をxとすると、あるj(1<=j<=n)によって
s[j] = x + ΣT
つまり
もとの石の山
= (残りの個数) + (取り除いた個数)
= (残りの個数) + (T[0]+T[1]+...+T[k])
が成り立っている。
これにより、状態はs[j]以下の整数の分割の1種と対応することがわかる。よって、整数m(0<=m<=60)の分割数をp(m)としたとき、状態数は
p(m)を使って抑えられる。
Σp(m)
= 1 + 1 + 2 + 3 + 5 + 7 + ... + 966467 (https://oeis.org/A000041)
= 6639349
< 6.7 * 10^6
この程度なのでおそらく間に合う。
思いつき方
ビットDPやGrundy数を知っている。愚直解について考える。sの要素60以下で小さい。愚直解は(状態がスカスカの)ビットDP。愚直解の計算量を調べてみる。状態数はもともとの石の数の分割数で抑えられる。間に合う。
Codeforces #399 D: Jon and Orbs
p[i]<=1000に注目する。
p[i]/2000 <= 1000/2000 = 1/2 (1)
i = 0,1,2,...,T
ターンたったときに全種類そろっている確率をf[i]とし、これをすべて求めて
l[i] = (p[i]-ε)/2000 の値で二分探索すればいい。
ただし、(1)よりf[T]>=1/2でなければならない。
そのようなTはk<=1000とkの値がそれほど大きくないので、じつはあまり大きくない。
つまり、1000種類のオーブが揃う確率を1/2以上にしたい場合、極端に多くのターンは必要なさそう。
ちなみに
T<=10000
これは十分に直感的だが、f[i]を実際に求めるだけで確かめられるし、そうすれば解も計算できる。
f[i]の求め方
g[i][j] := iターンたったとき、j種類揃っている確率
のDPを解けばいい。オーブを区別しなくていいことが重要。
実行時間
O(Tk + qlg(T))
思いつき方
入力の制約から気づく
AtCoder ARC069 E: Frequency
数列を辞書順最小にしたいということから、貪欲。ちゃんと説明する。
最初に取り除く石について考える。取り除く候補の石の山が２種類あるとし、それぞれp,qとする。pを取った場合に次のxは3、qを取った場合に次のxは7とする。このとき解は前者では
3,?,?,...
後者では
7,?,?,...
のようになり、未確定の部分がどのような値になっても辞書順最小は前者であることがわかる。
与えられた石の山aについてa[i]のとりうる値をA,B,C,D(A>=B>=C>=D)とする。下に図があり、それを見たほうがよくわかる。解の求め方は、まず石がA個ある石の山がk個あるとし、このうち一番左の山が次に追加する要素xになる。とりあえず最左でないk-1個の山からそれぞれA-B個ずつ取り除く。このときxは変わらない。次にただ1つになった最左のAの山からA-B+1個の石を取り除く。まだxは変わらない。最後にこの山から石を1個取り除く。このとき、最大の石の山の大きさはBであり、最左のBがもともとのAよりも左にあればxはその位置へ移動し、そうでない場合はxはもとの位置のままである。こうしてもとの問題よりもa[i]の値が小さくなった。あとは同じ手順をすべての石の山が空になるまで繰り返せばいい。
実装
最初のaの値について、各値が出現する最左のインデックスをmapで持っておく。また、各大きさの石の山がいくつあるかもmapで表し、最も大きい石の山を先の手順で削っていき、より小さい石の山のカウントを増やしていく。このとき、出力すべき解の変数に加算していく。
思いつき方
図を描く。手を動かす。
AtCoder ARC069 D: Menagerie
i(>=2)番目の動物はi-1番目、i-2番目の動物が決まっていればわかる。そこで、1番目と2番目の動物の種類をたかだか4通りを総当りで仮定し、そのそれぞれの仮定について、他のN-2種類の動物を決める。そうしたら、仮定が間違っていないかを条件に従ってチェックして解になるか調べる。
Codeforces #397 D: Artsem and Saunders
まず2式
g(h(x)) = x
h(g(x)) = f(x)
を別々に考えてみる。
g(h(x)) = x
を満たすg,hは
例えば
g(x)=x
h(x)=x
があり、必ず構成できる。
また
h(g(x)) = f(x)
については
g(x) = x, h(x) = f(x)
とすればよく、これもf(x)の値によらない。
ところが、2式を同時に条件とすると成り立たない場合がある。（入力例2)
なので2式を使って解が存在する条件を求める。(関数fだけで表す)
f(f(x)) = f(x)
これで解があるか調べられる。
解の構成を考える。
g(f(x))
= g(h(g(x))
= １(g(x))
= g(x)
g(f(x)) = g(x)
h(g(x)) = f(x)
の2式より解を作っていく。
g(f(x)) = g(x)
より
y = f(x)
とすると
g(y) = g(x)
これによりmを決める。(素集合を考えればいい)
z=g(x) として1<=z<=m
g(f(x)) = z
h(z) = f(x)
なのでf(x)の値ごとにzを追加していけばいい。
