Maximum-Cup 2018:D - Many Go Round

問題

https://atcoder.jp/contests/maximum-cup-2018/tasks/maximum_cup_2018_d

考え方

部分和問題に帰着する。a_i のうちいくつか選んだときにその和の modL に等しくなれば良い。mod 上で考えればよいので DP を回す最大値は M 未満まででよい。

そのとき以下のように DP を定義する。

dp[i][j] :=\ i 番目まで見たときの j にいるときの最小回数

DPの初期値は j=0 の場合に 1 で、DP遷移は \displaystyle dp[i+1][j+a[i]] = min(dp[i+1][j+a[i]],\ dp[i][j] + \frac{j+a[i]}{M}) となる。

Submission #3910219 - Maximum-Cup 2018

どこに着目して考察するべきだったか

mod\ M で考えて良いので、DPを回す最大値は M 未満でよかった。

何がバグっていたか

ビット上で考えうる部分和を列挙したのち、i (mod\ M) = L なる i ビット目がたっている場合には YES そうでない場合は NO と考えたが、その場合は (たぶんビット演算が重くて) TLE した。

Submission #3909990 - Maximum-Cup 2018

得た知見

mod M 上の最大値は M-1

類題