■156F - Modularness
これも難しいね。
サンプルをベースに説明すると
3,6,7,11,14
でmodを取ると
1,0,1,1,0なりansは1
aに足されるdは最初からmodをとってから足しても変わらないので
3,4,5,5,6と同じ
こうするとn項目とn+1項目の差はd未満なので
anとan+1をmodで割ったときの商の差は0 or 1で
差が発生するときは余りが逆転することになる。
ここまでわかると、答えを直接求めるのではなく、
n-1から>か=になるケースを引けばいいとわかる。
=になるケースは足されたd(mod)が0の時
問題は>となるケースだが
それは上のサンプルでいうと
3 = 1*2+1
6 = 3*0+0であり、商の部分が増えたタイミングで発生するので
末項/m-初項/mになる。
■157F - Yakiniku Optimization Problem
幾何
二分探索なのは明らか。
基本的には151F - Enclose Allと似たような容量で考える。
熱源の中心の候補店は、２円の交点と円の中心。
■158F - Removing Robots
ロボットの倒す順番は関係がない
左から好きなのを倒していって、残ってるやつ選んで更に好きなのを選ぶを繰り返せば良い
dp[i];=i番目以降のロボットの通り数として
i番目のロボットを倒すとj番目のロボットまで倒れるとするなら
dp[i] = dp[i+1]+dp[j+1];//倒さない＋倒すとなる。
i番目を倒せばどこまで倒れるかはセグ木で管理。
■159F - Knapsack for All Segments
[2,2,4]で4を作るのは
(1+x^2)(1+x^2)(1+x^4)のx^4の係数
それぞれをf1f2f3として
no1 = f1
no2 = f1f2 + f1 + f2
no3 = f1f2f3 + f1f2 + f2f3 + f1 + f2 + f3
差分を考えると
F1 = f1
F2 = f1f2 + f2
F3 = f1f2f3 + f2f3 + f3
Fn = F(n-1) * fn + fn = (F(n-1) +1) * fn
となる。
■160F - Distributing Integers
全方位木DP。
dfsを２回する。
二回目のdfsは親から子の答えを出すために必要なものを渡す。
