■A - Century
(n+100-1)/100
■B - 200th ABC-200
long longに収まることを確認して
問題に書かれているとおりにやる
■C - Ringo's Favorite Numbers 2
mod200で分類しておき
Σx(x-1)/2
■D - Happy Birthday! 2
実装重たくない？と思って答えを見たら鳩の巣原理。。天才！
Cと同様にmod200で分類しておく
同じmodの物があればそれが答えなので別処理しておく。
すると、
{1,2,5,7,11}みたいな集合から適当に２グループ作ってmod200で和の等しいグループが作れるか？
という問題になる
前から
dp[i][j] := i番目まで見た、mod200でjな数が作れるかどうか
を言う感じでdpをする。
しかし、これだと復元パートが面倒なので
vector
■E - Patisserie ABC 2
i + j + kで順番に見ていく
i + j + kを固定したときの場合の数は
更にiを固定をすればj + kが固定されるため
必要なのはj + kの区間和で、前のi + j + kの結果に足し引きすれば尺取法と同じ容量なので合計でO(3*N)で求まる
これで答えを満たすときのi+j+kが特定できたので
同じ要領でiを特定し、jとkも特定すれば良い。
■F - Minflip Summation
解説放送のやり方が天才。
01011110のような文字列をフリップして全て同じにするためにかかる回数は
円環にして01と10の回数を足し２で割った物になる。
K個連結しているがabcabcみたいなものは円環にして考えるのなら
abcを考え倍にすればいいので行列で頑張る必要がない。
