実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 795
問題概要
正整数 に対して
とする。長さ
の正整数列
が与えられるとき、
の値を求めよ。
制約
- 入力はすべて整数。
考察
の最大値が
と大きいので、愚直に2重ループを回していては間に合わない。何か工夫が必要である。
そこで、 であることから
を
で割った商は常に
のいずれかになることに注意して、
を次のように言い換えてみる。
こうすることで、求める式の値は となる組
の個数を
として、
に等しいことがわかる。
第1項については、各 が
回ずつ加算されることを考えると、
として求められる。
問題は第2項だ。なんとかして を
未満で求めたい。そこで、こんなことを考えよう。
「昇順ソートされた について、各
に対して
となる
を数えていけばいいのでは?」
は二分探索 ( C++ では
lower_bound
) で求めることができるので、計算量は 程度まで抑えられる。
あとはこれを実装するだけ...と言いたいところだが、 は
の組みあわせの個数なので、二重にカウントしないように二分探索の探索範囲を
に応じて変える必要があることに注意しよう。また、
int
型だとオーバーフローする (1敗) 。
コード
#include <bits/stdc++.h> using namespace std; using ll = long long; #define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++) #define all(x) (x).begin(), (x).end() // ======================================== // ll MOD = 100000000; int main() { ll N; cin >> N; vector<ll> A(N); ll sum = 0; rep(i, 0, N) { cin >> A[i]; sum += A[i]; } sum *= (N - 1); sort(all(A)); ll k = 0; rep(i, 0, N) { auto j0 = lower_bound(A.begin() + i + 1, A.end(), MOD - A[i]); k += A.end() - j0; } cout << sum - MOD * k << endl; }
実装時間: 60分
が絡む問題は個人的に苦手意識があるんだよなぁ...てかこれ茶Diffってマジ?