【よくわかる解説!】ABC353 C問題〜尺取法〜

ABC

解説動画

動画内の説明で利用していたファイル


# title
    尺取!!
# point
1. シグマの理解
    i = 1
        j = 2, 3, 4, 5, 6
    i = 2
        j = 3, 4, 5, 6
    i = 3
        j = 4, 5, 6
    i = 4
        j = 5, 6
    i = 5
        j = 6
2. aはソートする(尺取法をするため)
3. あまりとかを無視すると下記で計算可能!
    (n - 1) * a[i]
4. Mを超えるのが何個か数える(尺取法)

(注意!)M = 1e8だが, 理解のためM = 20とする.

n = 6
# 入力例
6
2 4 8 13 15 19

 2: 2+4, 2+8, 2+13,  2+15,   2+19
 4:      4+8, 4+13,  4+15,   4+19
 8:           8+13,  8+15,   8+19
13:                 13+15,  13+19
15:                         15+19
19:

余込みで愚直に計算すると,145

Mを超えるのが8個! <= これを数えるのがむずい!尺取法! 工夫した計算で, 2*5 + 4*5 + 8*5 + 13*5 + 15*5 + 19*5 - 8*20 # 配列情報 0 1 2 3 4 5 2 4 8 13 15 19 a[i] + a[r] >= Mの時はrをデクリメント!

r:
    スタート地点はn-1
    その場に留まるか, 左に移動するかのいずれか

動きを追う
i = 0
    r = 5
        a[i] + a[r] = 21
    r = 4
        a[i] + a[r] = 17 => i = 0の時, r = 4 => ((n - 1) - r)個
i = 1
    r = 4
        a[i] + a[r] = 19 => i = 1の時, r = 4 => ((n - 1) - r)個
i = 2
    r = 4
        a[i] + a[r] = 23
    r = 3
        a[i] + a[r] = 21
    r = 2
        a[i] + a[r] = 16 => i = 2の時, r = 2 => ((n - 1) - r)個
i = 3
    r = 2
        a[i] + a[r] = 21
    r = 1
        a[i] + a[r] = 17 => i = 3の時, r = 1 => ((n - 1) - max(r, i))個
i = 4
    r = 1
        a[i] + a[r] = 19 => i = 4の時, r = 1 => ((n - 1) - max(r, i))個
i = 5
    r = 1
        a[i] + a[r] = 23
    r = 0
        a[i] + a[r] = 21
    r = -1 => ((n - 1) - max(r, i))個

コード

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (n); ++i)

int main() {
    // const ll M = 20;
    const ll M = 1e8;
    ll n;
    cin >> n;
    vector a(n);
    rep(i, n) cin >> a[i];
    sort(a.begin(), a.end());

    ll ans = 0;
    rep(i, n) ans += a[i] * (n - 1);

    int r = n - 1;
    ll cnt = 0;
    rep(i, n) {
        while(r >= 0 && a[i] + a[r] >= M) {
            r--;
        }
        // cout << i << " " << r << endl;
        ll nowCnt = (n - 1) - max(r, i);
        cnt += nowCnt;
    }
    ans -= ll(cnt) * M;
    cout << ans << endl;

    return 0;
}

コメント