AOJ 1373 Placing Medals on a Binary Tree
問題文
深さ 1e9 の完全二分木と N 枚 (N <= 5 * 1e5) のメダルが与えられ, メダルを順番に二分木のノード上に置いていく.
各メダルには正整数 x が書かれており, 深さ x を持つノードの上にしか置くことができない.
また, そのノードを根とする部分木に既にメダルが置かれているようなノードにも置いてはいけない. (すなわち, 根から各メダルへのパス上に他のメダルが存在してはいけない)
メダルを順番に置けるなら置いていく. この時, 各メダルが置けるなら YES, そうでないなら NO を出力せよ.
解法
x が書かれたメダルを2つ置く場合, (x-1) の書かれたメダルを1つ置くものと見做してもよい.
よって, 各深さ k (0<=k<=N) に対してメダルが置かれているかどうかだけを覚えておき, 新しくメダルを置く際にこれを更新していく.
既に 0 が埋まっているか, 新しいメダルを置いた時に 0 のメダルができ, かつ他のメダルが残る場合に NO を出力する.
この判定を O(1) or O(logN) で行うのがこの問題の要所. 自分は Fenwick Tree を使って sum[1, x[i]] ?= x[i] で判定した.
YES の場合は愚直に (x-1) のメダルに置き換えていけばよい. この置き換えは高々 O(N) 回しか行われないので間に合う.
N < x[i] となるような x[i] は 0 のメダル生成に関与しないので, 存在するかどうかだけ覚えておけば良い.
ソースコード
template <typename T> class FenwickTree { const int n; vector<T> data; public: FenwickTree(int _n) : n(_n), data(_n, 0) {} void add(int pos, const T &value) { for (int i = pos; i < n; i |= i + 1) data[i] += value; } T sum(int pos) const { T res = 0; for (int i = pos - 1; i >= 0; i = (i & (i + 1)) - 1) res += data[i]; return res; } T sum(int l, int r) const { return sum(r) + (-sum(l)); } }; int main() { cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; FenwickTree<int> ft(N + 1); int cnt = 0; bool zero = false; vector<int> x(N); for (int i = 0; i < N; i++) { cin >> x[i]; bool f; if (zero) { f = false; } else if (N < x[i]) { cnt++; f = true; } else if (!ft.sum(x[i], x[i] + 1)) { f = true; ft.add(x[i], 1); } else { if (ft.sum(1, x[i] + 1) == x[i] && (cnt || ft.sum(x[i] + 1, N + 1))) { f = false; } else { f = true; while (ft.sum(x[i], x[i] + 1)) { ft.add(x[i], -1); x[i]--; } ft.add(x[i], 1); if (x[i] == 0) zero = true; } } cout << (f ? "Yes" : "No") << endl; } return 0; }
感想
値を set で管理したら余裕で TLE したので Fenwick Tree に書き換えたら通って虚無.
http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=3329722
ICPC審判団講評では多倍長2進小数に変換する解法が示されていた.
http://icpc.iisf.or.jp/past-icpc/comments/2016.pdf