サプリメント解説(ABC17-D)
DPの尺取りをやったことがなかったため、難しく感じました。forDPじゃないと解けないDP多すぎませんか。
あと高橋君、サプリメント10^5個飲むのは飲みすぎ。
問題
解説
部分点解法
部分点解法は明らかにDPです。ここでは満点解法につなげるためにもらうDPを書きます
dp[i]=a(i=何個目の薬か、a=i個目の薬を選ぶとき、その前の薬から考えて何通りの選び方があるか）
dp[i]=(dp[i-1]+~dp[i-k])（i-kは同じ味の薬がでない最大の範囲）
こんな感じでもらうDPが書けます。
しかし、遷移の計算量含めるとO(N^2)となり、間に合いません。
満点解法
この画像の通り、同じ区間を何度も計算するのは無駄となります。
このようなときに使えるアルゴリズムには「尺取り法」と「累積和（いもす法）」というのがあります。
尺取り法→
第21回アルゴリズム勉強会 from Yuuki Ono
www.slideshare.net累積和→
累積和手法 - sataniC++
今回は尺取法を使います。
尺取法はその時その時で前にある値を削り、新たに新しい値を追加することで成り立ちます。
iを更新していくごとに、そのiの前でどれだけの範囲をかぶることなく選べるかというのを考えると、尺取法のような形になるのがわかります。
なので、
for(n個目までの薬){
while(かぶっている間は){
i個目の時に適応できない薬は合計から減らす
}
配列にi個目の時の選び方の通りを保存
i+1個目の合計にはi個目の合計が含まれるので、合計を二倍する
}
というようになります。
