AOJ 1373 Placing Medals on a Binary Tree

問題文

深さ 1e9 の完全二分木と N 枚 (N <= 5 * 1e5) のメダルが与えられ, メダルを順番に二分木のノード上に置いていく.
各メダルには正整数 x が書かれており, 深さ x を持つノードの上にしか置くことができない.
また, そのノードを根とする部分木に既にメダルが置かれているようなノードにも置いてはいけない. (すなわち, 根から各メダルへのパス上に他のメダルが存在してはいけない)
メダルを順番に置けるなら置いていく. この時, 各メダルが置けるなら YES, そうでないなら NO を出力せよ.

Placing Medals on a Binary Tree | Aizu Online Judge

解法

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