Two Teams
問題はこちら
自分が気づいたところ
愚直解は,毎回使っていない最大値を検索→幅 を探索し,使っていないものをk個チームに属させるというもの. 計算量としては, なのでそのまま実装すると になるので間に合わない.
そこで,一回使ったものは取り除いて考えることができるようなデータ構造を考えれば良いと気づいた.
ここで,すでに使用したindexを扱う問題としてこれを解いたなーと思いながらも,帰着させることはできず.
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の復元が容易であるということ.