abc149_e Handshake

原因

コーディングで派手に事故った

問題

https://atcoder.jp/contests/abc149/tasks/abc149_e

$N$ 要素の数列 $A=\{ A_i \}$ から2要素 (同じでも良い) を選んでできるペアの和からなる $N^{2}$ 要素の数列のうち上位 $M$ 個の和を求めよ。

$1 \le N \le 10^{5}$, $1 \le M \le N^{2}$, $1 \le A_i \le 10^{5}$

解法

$A$ は昇順にソートしておく。

(1) 上位 $M$ ペア目に相当する値 $x$ を、$x$ 以上になるペアの数によって二分探索する。

(2) $x$ 以上になるかどうかは各 $A_i$ について、$A$ に対して $x-A_i$ をキーとして二分探索すればよい。

(3) $M$ 個で区切れないときは $M$ を上回らない範囲で $x$ を求めておいて、$x$ の直下ペアの値を答えへ必要なだけ足す。

あとは上からの累積和で当てはまる部分を全部足してOK。計算量 $O(N \log \max A_i)$

事故

(1) x の上限を $2 A_n$ にした

2 2 
1 1

など、全要素が同じ時にもれなくバグる　2WA

対策： 要素アクセスで死なないときのOK側は大袈裟に取る

(2) vector に対するにぶたんを手書きした

なんで？

個数を求めるので初期値を-1とnにして……などと無駄な思考リソースを使った。　0WA

対策： STLに慣れる

(3) 直下ペアを求める時に配列範囲外アクセスした

$x$ の直下ペアを各 $A_i$ についてそれぞれ求める際、$A_i + A_1 \ge x$ のときに存在しない $A_0$ を叩いていた。　1WA

なんかREにならなかったので気づくのが遅れた

対策： continue判定をケチらない。そもそもなんかコンパイラオプションあったはずなので調べる

提出コード

初AC https://atcoder.jp/contests/abc149/submissions/9879339

リファイン版 https://atcoder.jp/contests/abc149/submissions/9879559

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

ll n,m;
vector<ll> a;
ll f_ind(ll i, ll x){ 
    auto it = lower_bound(a.begin(), a.end(), x - a[i]); // (2)
    return a.end() - it;
}
ll fint(ll x){ // x 以下となるペアの数
    ll ans = 0;
    REP(i,n) ans += f_ind(i,x);
    return ans;
}
bool f(ll x){
    return fint(x) <= m;
}

signed main(){
    cin >> n >> m;
    a.resize(n);
    REP(i,n) cin >> a[i];
    sort(a.begin(), a.end());

    ll ng = 0;
    ll ok = 2 * a[n-1] + 1; // (1)
    while(abs(ok-ng) > 1){
        ll mid = (ok + ng)/2;
        (f(mid) ? ok : ng) = mid;
    }
    ll rem = m - fint(ok);
    ll border = 0;

    REP(i,n) {
        if (f_ind(i,ok) == n) continue; // (3)
        border = max(border, a[i] + a[n-1-f_ind(i,ok)]);
    }
    ll ans = border * rem;

    vector<ll> acum = a;
    acum.push_back(0);
    REP(i,n) acum[n-1-i] += acum[n-i];

    REP(i,n) {
        ans += f_ind(i,ok) * a[i] + acum[n-f_ind(i,ok)];
    }
    cout << ans << endl;
}

感想

コーディングで死ぬの本当に険しい。頭がついていない。

mathjax でのエスケープはバックスラッシュ2個

ところで 「M$」 がリンクになって、対処しないと mathjax が死ぬのがあまりにも💩