Algoogle

Algorithm for Programming Contest

AOJ 2443 Reverse Sort

Category: AOJ Tag: bidirectional-search

Reverse Sort

問題概要


最大で長さ10の数列がある. 数列の連続する区間をreverseすることを繰り返すことで数列をソートしたい.
そのときの最小のステップ数を求めよ.

解法


まず, ステップ数は最大でもN-1になる. なぜなら位置が正しくない場所のうち, 一番左を揃えるように毎ステップやれば一番右はその左の数が正しくなったときに正しい位置になるから.

そのことを利用して両側探索(半分全列挙)を行う.
また最悪でもN-1ステップなので列挙は最大でも4ステップ分で良い. それらに共通する数列がなければ必ず最悪ステップが答えになる.
これで程度になる.
数列はunsigned long longを4ビットごとに区切ってhashにした.

コード


(2443.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;
typedef unsigned long long ull;
#define repi(i,a,b) for(int i = (a); i < (b); i++)
#define rep(i,a) repi(i,0,a)
typedef pair<ull,int> pli;
ull A;
const int M = 4;
map<ull,int> d[2];
int a[16], N;

void bfs(int f){
    queue<pli> que;
    d[f][A] = 0;
    que.push(pli(A,0));
    while(!que.empty()){
        ull u = que.front().first;
        int td = que.front().second;
        que.pop();
        if(td == min(4,N/2)) continue;
        for(int i = N-1; i >= 0; i--) {
            a[i] = u&((1<<M)-1);
            u >>= M;
        }
        rep(l,N) repi(r,l+1,N){
            reverse(a+l, a+r+1);
            ull v = 0;
            rep(i,N) v = (v<<M)+a[i];
            if(!d[f].count(v)){
                que.push(pli(v,td+1));
                d[f][v] = td+1;
            }
            reverse(a+l, a+r+1);
        }
    }
}

int solve(){
    bfs(0);
    A = 0;
    rep(i,N) A = (A<<M)+i;
    bfs(1);
    int ans = N-1;
    for(auto it = begin(d[0]); it != end(d[0]); it++){
        auto jt = d[1].find(it->first);
        if(jt != end(d[1])) ans = min(ans, it->second+jt->second);
    }
    return ans;
}
void input(){
    cin >> N;
    A = 0;
    rep(i,N) {
        int c;
        cin >> c;
        A = (A<<M)+(c-1);
    }
}
signed main(){
    input();
    cout << solve() << endl;
    return 0;
}

Comments