Codeforces Round #215 (Div. 1) C. Sereja and the Arrangement of Numbers

問題

codeforces.com

解法

p 個の数字を使えるとすると, その p 個の数字は w の大きい方から順に選ぶのが明らかに最適です(w は関係ないですね)。

ということで, 問題は N 個からなる数列が与えられた時, 最大いくつまで数字を使えるか, の p を求めることです。

これは, p 個の頂点を持つ完全グラフのすべての辺を通る最小回数がいくらか, という問題を考えることで解決します。p 個の数字を問題の条件に合うように並べるには, 辺を通る最小回数 + 1 の頂点が必要だからです。
p が奇数の場合は, 完全グラフのすべての頂点の次数が偶数になるので, 一筆書きが出来て, すべての辺を通る最小回数は p*(p-1)/2 回
p が偶数の場合は, 実験すると p*p/2-1 になる気がしました。証明になってない気がしますが, とりあえず p*p/2-1 では出来ることは説明します。まず, 各頂点であと通っていない辺が 1 本になるようにするには, p*(p-2)/2 回辺を通る必要があります(これは奇数の場合と同じで一筆書きっぽく出来る)。で, その後は p-1 回辺を通ることで, 残りの辺を通ることができるので, p*p/2-1 には出来ます。

const int MAXM = 100100;
int w[MAXM], q[MAXM];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    cin >> N >> M;
    for (int i = 0; i < M; i++) cin >> q[i] >> w[i];
    sort(w, w+M);
    reverse(w, w+M);
    int p = 1;
    for (; ; p++) {
        int need = 0;
        if (p%2==0) need = p*p/2;
        else need = p*(p-1)/2+1;
        if (need > N) break;
    }
    p--;
    int ans = 0;
    for (int i = 0; i < min(p, M); i++) ans += w[i];
    cout << ans << endl;
    return 0;
}