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の復元が容易であるということ．

ひらめの日常

日常のメモをつらつらと