【4日目】尺取り法の続き

今日は時間がなくてあまりできていないのだが、尺取り法の復習だけ少し。

尺取り法 (two pointers technique)

個人的にはtwo pointersというネーミングの方が分かりやすい感。条件を満たすような最長の区間[l, r)を求めるにあたり、lとrのうち片方を固定、片方を動かすということを交互に繰り返すことで、実直にやればO(n²)のところを計算量O(n)でできるアルゴリズム。たとえば

数列Sの部分列で、和がK以下になる最長のもの

を求める場合、以下のように書ける。

    ll r = 0;
    ll val = 0;
    ll ans = 0;

    for (ll l = 0; l < n; ++l) {
        for (; r < n + 1; ++r) {

            if (val + s[r] > k) {
                ans = max(ans, (ll)(r - l));
                break;
            } else val += s[r];

        }
        if (r == l) ++r;
        else val -= s[l];
    }

昨日書いた境界条件で場合分けしないための工夫の一環として、sの長さをn+1として、s[n]=INFとした。r==lとなったときの場合分けは減らす方法は今の所分からなかったのでそのまま。

AtCoderにEducational DP Contestたるものが存在するので、DPの練習に隙間時間に1問ずつやってみようと思う。あとグラフ問題も重点的に攻略したい。明日は時間がありそうならABC180、なさそうならグラフの問題を。