Codeforces #402 (Div. 1) B: Bitwise Formula

解法

AND, OR, XORのいずれもビットごとに独立に計算されることに注目する。ボブの選ぶm桁の数値(仮にxとする)は、各桁独立に求められる。各桁は0か1の2通り。それぞれ試して各変数のm桁目を求めて和をとり、最小値、最大値に対してそれぞれ適切なほうを選ぶ。

時間: O(nm)

ミス

誤読。ボブの選んだ数値まで和に含めてしまっていた。入力例まで読めば間違えなかったはず。

SRM 709 DIV1 Medium: Softmatch

http://codeforces.com/blog/entry/49911?#comment-344869

↑の理解

|patterns|<=5なのでこれの最大ケース|patterns|=5の場合だけ考えてみよう。以下のような愚直なDPはすぐに思いつく。

dp[i][p[0]][p[1]][p[2]][p[3]][p[4]]

:= Sのi番目まで確定していて、pattenrs[j]についてはp[j]文字まで一致している。このときの単語の出現個数の最大値。

しかし、これでは間に合わないから、DPテーブルの次元を減らしたい。

p[0]>=p[1]の場合を考えてみよう。ただし、p[1]の値は具体的にはわかっていないとする。

p[0]の値によって、Sの確定部分のうち直前p[0]文字は求まる。このSの直前p[0]文字、S[i-p[0],i)によって、p[1]の値を具体的に求めることができる。つまり、pattenrs[1]のprefixとS[i-p[0],i)のsuffixが最大何文字一致しているかがわかる。同様に

p[0]>=p[j], (j!=0)ならば p[j]の値をすべて求めることができる。

p[0]が最大とは限らないが、あるp[x]が最大でありその値がわかっているならば他のp[j](j!=x)は求めることができる。よって、先のDPは以下のように変換できる。

dp[i][j][k]

:= Sのi番目まで確定していて、patterns[j]が一致文字数が最も多く、その文字数はkである。このときの単語の出現個数の最大値。

これを解けば良い。

思いつき方?

とりあえず愚直なDPを考えてみる。そのDPの次元のとり方に無駄がありそうなら、次元を減らそうと試みる。p[i]は何に畳み込めるか。逆に考えるとわかりやすい?p[i]をすべて求めるのに必要最小限の情報は何か。

SRM 709 DIV1 Easy: Xscoregame

|A|<=15で順列で最小とあり、ビットDPっぽい。しかし、

X+(X^Y) の後半xorパートが怪しい。

の値が大きければ良いというわけでもない。

そこでA[i]<=50に注目する。A[i]<=50<64=2^6である。つまりA[i]の下位6ビット以外はすべて0。それに対してXの値は当然1であったほうが良い。つまり、下位6ビット以外に関しては、大きければ大きい方がいい。よって普通にXの最大値がわかれば十分。他方、下位6ビットに関してはYとのxorで影響を受けるので、ありうるすべての値について最大値を計算する。したがって以下のようなDPを計算する。

dp[used][lower_bits]

:= Aのうち使用したものがused、下位6ビットがlower_bitsであるときのXの最大値

WA

dp[used]:=Xの最大値

をやらかした。

証明しようと試みなかったし、直感的に正しいわけでもないのに、あまり考えずに提出してしまった。

これがExamplesで落ちないのは厳しい。

思いつき方

ビットDPっぽい。

A[i]<=50

=> 下位6ビットを見る

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個、2個、1個、3個取り除いたことがある)
となり、このとき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

数列を辞書順最小にしたいということから、貪欲。ちゃんと説明する。

最初に取り除く石について考える。取り除く候補の石の山が2種類あるとし、それぞれ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で表し、最も大きい石の山を先の手順で削っていき、より小さい石の山のカウントを増やしていく。このとき、出力すべき解の変数に加算していく。

思いつき方

図を描く。手を動かす。

 

f:id:parukii:20170220014619j:plain

AtCoder ARC069 D: Menagerie

i(>=2)番目の動物はi-1番目、i-2番目の動物が決まっていればわかる。そこで、1番目と2番目の動物の種類をたかだか4通りを総当りで仮定し、そのそれぞれの仮定について、他のN-2種類の動物を決める。そうしたら、仮定が間違っていないかを条件に従ってチェックして解になるか調べる。