Atcoder Beginner contest 130 E - Common Subsequence
問題概要
N個の整数列を与えられて、その部分列のうち、Kを超える部分列を数え上げる。
解法
しゃくとり法。
しゃくとり法解説記事 しゃくとり法 (尺取り法) の解説と、それを用いる問題のまとめ - Qiita
しゃくとり法のテンプレ書き方の参考
尺取りは書き方を体系化してしまえばよくて、
— Cinnamoroll(シナモロール)🌞 (@Cinnamon_VR) June 17, 2019
int r = 0, cur = hoge;
rep(i,n){
while(r < n && check() ) cur+=a[r],r++;
ans += n+1-r;
cur -= a[i];
}
みたいにすればバグらない気がするけど
昨日のDをこのまま書くと壊れて、正確にはr進めたあとにcur>=kの判定がいります
— Cinnamoroll(シナモロール)🌞 (@Cinnamon_VR) June 17, 2019
提出
今回のcur >= kのチェックは、rを進めた後、countを追加する前に実施。
