POJ-2085: Inversion

PKU

こんなに面倒なはずがない、という問題だったのでいつもより丁寧に書く

keyword

反転数　Greedy　BIT　二分探索　C++

問題概要

[1..N](N<5*10^4)のpermutationのうち、反転数がMになる辞書順最小のものを出力する問題。

素朴な解法

辞書順最小という問題が出たら解法は大体2つ。

  • 条件を満たすものは全部作り出すことができる。つまり辞書順最小は本質ではない。
  • 前からGreedyに詰めていく。

(追記：解の候補を辞書順に小さい方から生成してアタリが出るまで試す、という解法も考えられる。広い意味ではこれは前者に含まれるかもしれないが)
今回の場合は明らかに後者だろう(少し丁寧に考えると、N!をMで割った値が大きすぎて前者が無理だと分かる)。
まず反転数の上限について考えてみよう。長さnの数列の反転数の上限はn*(n-1)/2である([N..1]のとき)。
となると、次のように解けば良いことが分かる。

  • (N-1)*(N-2)/2>=Mなら先頭にはまだ使ってない数のうち最小のものを置いて良い。
  • (N-1)*(N-2)/2
  • あとは残りのリストについて再帰的に解く。

これを素直に実装したのがこれ。

int64 N, M;

void solve(){
    vector<int> ans;
    set<int> unused;
    for(int i=1;i<=N;i++) unused.insert(i);
    for(int i=0; i<N; i++){
        int64 res = N - i - 1, most = res*(res-1)/2;
        set<int>::iterator itr = unused.begin();
        if(most < M){
            int pos = M - most;
            M -= pos;
            advance(itr,pos);
        }
        ans.push_back(*itr);
        unused.erase(itr);
    }
    for(int i=0; i<N; i++)
        printf("%d%c",ans[i], i==N-1?'\n':' ');
}

int main(){
    while(scanf("%lld%lld",&N,&M),N+1) solve();
    return 0;
}

実はこれだと計算量がO(N^2)になっていてTLEする。何故かというとadvance(itr, pos)に最悪O(N)かかってしまうから。

改善案

advanceに時間が掛かっていたのがTLEの原因なだけで、部分問題を残して元の問題は殆ど解けている。
上の解法の過程で、「i番目(0-origin)にはまだ使ってない数のうちa[i]番目の数を使う」という情報はO(N)で得られることが分かる。この情報を使って答えとなる配列を構成しないといけない。この新しい部分問題について考えよう。
この問題は、「1,2,...,K-1のうち既に使ったものがi個以上となる最小のK」を求めれば良い。これはBITを使った二分探索で求められる。
この解法だと計算量はO(N * (log N)^2)。一応ACだった。

int64 N, M;
int bit[MAX_N];
vector<int> adds, ans;

void initBIT(){ memset(bit,0,sizeof(bit)); }
int sum(int n){ int ret=0;for(;n;n-=n&-n)ret+=bit[n];return ret; }
int add(int n, int x){ for(;n<=N;n+=n&-n)bit[n]+=x; }

void solve(){
    adds.clear(); ans.clear();
    for(int i=0; i<N; i++){
        int64 res = N - i - 1, most = res*(res-1)/2;
        if(most < M){
            int pos = M - most;
            M -= pos;
            adds.push_back(pos);
        }
        else{
            adds.push_back(0);
        }
    }

    subsolve();

    for(int i=0; i<N; i++)
        printf("%d%c",ans[i], i==N-1?'\n':' ');
}

bool check(int mid, int val){
    return sum(mid)>val;
}

void subsolve(){
    initBIT();
    for(int i=1; i<=N; i++) add(i,1);
    for(int i=0; i<N; i++){
        int high=N, low=0;
        while(high-low>1){
            int mid = (high + low)>>1;
            if(check(mid, adds[i])) high = mid;
            else low = mid;
        }
        ans.push_back(high);
        add(high,-1);
    }
}

int main(){
    while(scanf("%lld%lld",&N,&M),N+1) solve();
    return 0;
}

感想

どう考えてもこんな面倒くさい問題なはずがない。嘘解法臭がきつすぎる。
どうしても分からなかったときは実験してみるに限る…だけど眺めてみても綺麗な法則があるようには見えない。どう解くのがスマートなんだろう。