ひらめの日常

プログラミングと読書と

Codeforces Round #552 (Div. 3) E. Two Teams

Two Teams

問題はこちら

codeforces.com

自分が気づいたところ

愚直解は,毎回使っていない最大値を検索→幅  kを探索し,使っていないものをk個チームに属させるというもの. 計算量としては,  n=O(10^{5}) なのでそのまま実装すると  O(n^{2})になるので間に合わない.

そこで,一回使ったものは取り除いて考えることができるようなデータ構造を考えれば良いと気づいた.

ここで,すでに使用したindexを扱う問題としてこれを解いたなーと思いながらも,帰着させることはできず.

B - Minimum Sum

AGC005-B 「Minimum Sum」 (400) - Mister雑記

解説を読んで

解説はこちらを参考にさせていただいた(いつもありがとうございます...!). cinnamo-coder.hatenablog.com

ある要素から右方向にあって、まだチームが決まっていない選手の最小のindexを持つことでこれは達成できる。左方向にも同じものを作っておく。

そこで,以下のように実装し,随時これをupdateする実装をした.

set<int> s : 使用してないスキルの集合
l[i] : i番目の人から,左方向でまだチームが決まっていない選手の最小のindex
r[i] : i番目の人から,右方向でまだチームが決まっていない選手の最小のindex
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

int main() {
    ll n, k;
    cin >> n >> k;
    vector<ll> a(n), idx(n);
    rep(i, n) {
        cin >> a[i];
        idx[--a[i]] = i;
    }
    set<ll> s; // 使ってないもの
    rep(i, n) s.insert(i);
    vector<ll> l(n), r(n);
    rep(i, n) {
        if (i == 0) l[i] = -1;
        else l[i] = i - 1;
    }
    rep(i, n) {
        if (i == n - 1) r[i] = -1;
        else r[i] = i + 1;
    }

    vector<ll> ans(n);
    ll turn = 1;
    while (!s.empty()) {
        ll maxval = *s.rbegin();
        s.erase(maxval);
        ll i = idx[maxval];
        ans[i] = turn;
        ll li = i, ri = i;
        for (int j = 0; j < k; ++j) {
            if (l[li] == -1) {
                break;
            }
            s.erase(a[l[li]]);
            li = l[li];
            ans[li] = turn;
        }
        for (int j = 0; j < k; ++j) {
            if (r[ri] == -1) {
                break;
            }
            s.erase(a[r[ri]]);
            ri = r[ri];
            ans[ri] = turn;
        }
        ll nli = l[li], nri = r[ri];
        if (nri != -1) l[nri] = nli;
        if (nli != -1) r[nli] = nri;
        turn = 3 - turn;
    }
    rep(i, n) cout << ans[i];
    return 0;
}

https://codeforces.com/contest/1154/submission/52917361

自分の詰まったところ

l[i], r[i]が端に到達した時の扱い方として,-1を立てるという方法にしたが,ここでバグを発生させていた.一回きちんと落ち着いて手で書いてからやった方が良い.

純粋にindex周りを扱うデータ構造の実装が遅い.

学んだこと

  • 最短の距離にあるものをそれぞれupdateしていくとうこと.
  • 値がdistinctな時には,array[それぞれの値] = index という構造を使うことでindexの復元が容易であるということ.