Algoogle

Algorithm for Programming Contest

POI II The Coding of Permutations

Category: POI Tag: binary-indexed-tree, binary-search

The Coding of Permutations

問題概要


1からnまでの整数を並び替えた数列をaとする.
をj<iとなるjのうち>となる数とする数列bが与えられる.
数列aとして考えられるものを出力せよ. 存在しない場合はNIEと出せ.

解法


数列を後ろから特定していく.
値の候補の集合をSとし, i番目を見ているとき
候補のうち番目に大きい数をとすればよい.
その後候補からを削除する.

あとは値の候補のうちk番目を見つけ, 削除できるようなデータ構造を考えれば良い.

今回はBITを使ってやることにした.
簡単のため値は0からn-1で考える.
値vを使ったら位置vに1を足す.
すると位置jについてそれ以降に使われた値の個数というのがsum(j,n)でわかる.
つまりj以降でまだ使われていない数はn-j-sum(j,n)個となる.
あとは使われてない個数が個になるような位置の最右端を二分探索すればよい.
計算量はになる.

余談だが, 使ってないもののリストをvectorで持ち番目を持ってきて削除とかはvectorのeraseが要素数の線形程度かかるので厳しい.

コード


(kod.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
#include <bits/stdc++.h>
using namespace std;

template<class T> class bit
{
        vector<T> dat;
        int N;
public:
        bit(int N) : N(N){
                dat.assign(N,0);
        }
        // sum [0,i)
        T sum(int i){
                T ret = 0;
                for(--i; i>=0; i=(i&(i+1))-1) ret += dat[i];
                return ret;
        }
        // sum [i,j)
        T sum(int i, int j){ return sum(j) - sum(i);}
        // add x to i
        void add(int i, T x){ for(; i < N; i|=i+1) dat[i] += x;}
};

int n, a[1<<15], b[1<<15];

int get_val(int i, bit<int> &bs)
{
        int lb = 0, ub = n, mid;
        while(ub-lb>1) {
                mid = (lb+ub)/2;
                if(n-mid-bs.sum(mid,n) > b[i]) lb = mid;
                else ub = mid;
        }
        return lb;
}

void solve()
{
        bit<int> bs(n+1);
        for (int i = n-1; i >= 0; i--) {
                if(b[i] > i) {
                        puts("NIE");
                        return;
                }
                int v = get_val(i,bs);
                a[i] = v+1;
                bs.add(v,1);
        }
        for (int i = 0; i < n; i++) printf("%d\n", a[i]);
}

void input()
{
        scanf("%d", &n);
        for (int i = 0; i < n; i++) scanf("%d", b+i);
}

int main()
{
        input();
        solve();
        return 0;
}

Comments