■A - Seismic magnitude scales
rep(i, a - b)ans *= 32;
■B - typo
全部試す
■C - Select Mul
bit全探索
■D - Online games
imos法を必要なとこだけ持つ感じ。
■E - LEQ
区間和と区間を２倍にする遅延セグ木があれば一瞬でできるんだろうけど
やり方がわからないので、ただのセグ木で少し工夫をする
■F - Diameter set
木の中心を知っていますか
AtCoder Grand Contest 001 C - Shorten Diameter
■G - Jumping sequence
・前半パート
ABC111D - Robot Armsを思い出せばいい。
45度回転すると考えやすくなり、x+yとx-yのそれぞれに対して{-d,d}で作れるかというナップサックをすればいい
これはx+y+Σdとx-y+Σdを{0,2d}で作れるかというナップサックと同じなので
適当に２で割ってナップサックをしてやらばいい。
・後半パート
しかし、O(n*Σd)かかるので無理。
なのでbitsetで高速化をしてやればいい。
メモリ制限: 1024 MBはbitset<3600001> bit[2001];ぐらいなら耐えるらしい
これはlong long[360000/64][2001]ぐらいなので900MBぐらいらしいです。
※僕の手元環境で実行できないので(？)サンプル通すときは小さくする必要がある
■H - Count Multiset
noshi91さんのユーザー解説の方法がすごい。
dp[i][j]:=i個で和がjな条件を満たす集合の通り数
最小値が２以上
全て１減らすとdp[i][j-i]と同じに通り数になる
最小値が１以上
１を無視するとdp[i-1][j-1]から１をM個使っているものを除いたものになる
除くものを考える
和がj-1-(1 * m)かつ個数がi-1-mかつ全要素が2以上。
これはdp[i-1-m][(j-1-m)-(i-1-m)]な集合に1を足したものだと思えばいい
つまりdp[i-1-m][j-i]
でも確かに最小値を消して、全部減らして再帰的に考えるのはARCで見たことある気がするな。
