yukicoder ☆5,6
何故か埋めています。解法メモなのでネタバレ注意。
☆5
42:
63:
93:
変なことをすると下から挿入できるが、普通に包除
114:
137:
特異問題です。これはむずい
1,x,x^2,..なら順番に倍数だから、modでピッタシになるようにdpするっていうのが出来たわけだが、今回はxを自由に使えるっていうのをx,2x,4x,..が1枚ずつあると言い換える。それでx_1,..,x_N,2x_1,..,2x_N,..っていう順番で使うかどうか決めていけば、各状態ではSum x_N 通りくらいしか持たなくて良い。
自由DPのときに分割するのは典型っぽいがその後こんなうまくいくのはびっくりしたなあ
214:
234:
243:
248:
263:
271:
283:
カス
284:
異なる二種類の和のmax みたいなのは 上位2種類持っておけば良い Bicycles(蝶々のやつ)とか
295:
まずこういうふうに並べるのが最適なのを示すのがアレだが、無駄に分割するのは意味がない(すべての文字でマージすれば絶対に積が大きくなる)のでOK.
あとはすごく小さいケースだけ場合分け
max制限がある数え上げでパラメーターtがあってn^tオーダーとかだとtが1,2,3とかのケースだけやればいいみたいなのあるよね
377:
Burnsideのいい練習問題だと思う.
不変な(x,y)の集合 みたいなのを考えたくなるが、ちゃんとBurnsideがわかってれば G = Z/HZ * Z/WZ の各元ごとにかんがえればいいことはわかる
382:
最大独立点集合, 乱択おもったより強いなあ(まあ乱数ガバいからまともに作ったケースだと落とされるのかな)
426:
苦行segtree
435:
無.なぜかmod 9 の世界でかけたり割ったりする時に 3^a * b (b = 1,2) の形で持っていたが,bは1,2,4,5,7,8なんだよなあ. 気をつけます
465:
474:
一時期ちょっと流行ったmod2系. Lucasの定理の拡張でmod素べきとかもあるので、困ったら使ってもいいかも(まあ愚直にやれるなら↑435みたいにやればよい).
540:
予想投稿サイトやめろ