解説動画
動画内の説明で利用していたファイル
# 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;
}
コメント