Topcoder SRM 517 Div1(Medium) AdjacentSwaps

\(2\leq{N}\leq{50}\)

\(0\leq{A[i]}\leq{N-1}\)

N개의 원소로 이루어진 벡터 A가 주어진다. 벡터의 값들은 0과 N-1 사이값이며 중복되지않는다.

\(0\leq{K}\leq{N-2}\)

인 N-1가지의 K에 대해 각각 한번씩 swap(A[K], A[K+1]) 을 해야만 한다.

그렇다면 이 swap을 하는 순서에 따라서 주어진 벡터의 결과값이 달라질 것이다.

그렇다면 주어진 벡터가 0,1, ..., N-2, N-1 과 같은 형태로 오름차순 정렬되도록 하는 swap 순서는 총 몇가지가 있는지를

구하는 문제이다.

이 문제는 DP로 풀 수가 있다. 

\(dp[i][j]\,:\,[i,\,j]\) 의 구간을 오름 차순 정렬하는 방법의 수

오름 차순 정렬이라는 것은 [i, j] 구간에 어떤 수들이 들어있던지 상관없이 오름 차순 정렬만 되면 된다.

그 이유는 뒤 쪽의 설명을 통해 자연스레 알게 될 것이다.

(미리 좀 설명을 하자면, 어차피 나중에 안되는 경우는 0이 되기 때문에 지금은 중간 중간 값이 비어도 상관없이

오름차순으로만 정렬하면 됨)

dp[i][j] 는 [i, j] 구간을 정렬하는 방법의 수 이다. [i, j] 구간을 정렬하기 위해서 일단

i~j-1 의 위치에서 한번씩 swap을 해야하는데 분명 마지막으로 swap이 되는 부분이 있을 것이다.

그 마지막으로 swap이 되는 부분 k를 정하면, 결국 그 마지막 swap을 하기 전 상태를 생각해보면

그 부분을 기준으로 두 sub vector 로 나누어 질 텐데

그 두부분도 각각 오름 차순 정렬이 될 것이다. 왜냐하면 [i, j] 가 정렬 되고 난 sub vector를 Q라고 할 때

Q[i] < Q[i+1] < ... < Q[k] < Q[k+1] < ... < Q[j] 일 텐데, Q[k] 와 Q[k+1] 을 swap 시켜도 부등식

Q[i] < Q[i+1] < ... < Q[k+1] 과 Q[k] < ... < Q[j] 가 각각 만족되기 때문이다.

그렇기 때문에 이 각각은 또 부분문제 dp[i][k] 와 dp[k+1][j] 로 나누어진다. 왜냐하면 두개를 각각

오름차순 정렬하고 k위치에서만 swap 해주면 두 부분을 합친 부분이 오름차순 정렬되는 효과가 나타나기 때문이다. 결국,

\(lastK[i][j][k]\,:\,[i,\,j]\) 의 구간을 마지막 swap을 k 인덱스에서 하여 오름 차순 정렬하는 방법의 수

일 때 lastK[i][j][k] 는 dp[i][k] 와 dp[k+1][j] 를 통해 계산이 되며 가능한 모든 k, 즉 [i, j) 의 k에 대해 각각

lastK[i][j][k] 를 구하여 다 더하면 dp[i][j] 가 나올 것이다. 식으로 표현해보면

\(dp[i][j] = \sum_{k=i}^{j-1} {lastK[i][j][k]}\)

왜냐하면 마지막으로 swap을 하는 곳은 결국

[i, j) 의 한 위치중 하나일 것이 분명하기 때문이다. 케이스를 나누어 마지막에 다 더해주는거라고 생각하면 된다.

그런데 물론 특정 구간이 오름차순 정렬이 가능하지 않을 때도 있기 때문에 이것을 따져서 안되는 경우는 0으로 계산하며

i==j 일 때, 즉 한칸일 땐 1가지밖에없는 셈이므로 1이다.

그럼 이 마지막으로 swap을 하는 위치가 [i, j) 에서 모두 가능하므로 각 경우의 방법의 수를 더해주면

[i, j]를 오름차순 정렬하는 방법의 수가 되는 것이다.

그렇다면 이제 애초에 구간이 정렬이 가능한지 판별하는 방법과

부분문제 dp[i][k] 와 dp[k+1][j] 로 dp[i][j] 를 구하는 식,

그리고 시간복잡도 분석을 하면 되겠다.

우선 구간이 정렬이 가능한지 판별을 하려면 어떻게 할까?

마지막 swap 지점으로 나누어진 왼쪽 부분구간과 오른쪽 부분구간을 각각 오름차순 정렬하고

두개를 이어붙인뒤 swap(k, k+1) 만 하면 전체가 오름 차순 정렬 되는지를 보면 될 것이다.

난 [i, k] 를 따로 떼내어 정렬한 부분과 [i, j] 을 정렬한뒤 swap(k, k+1) 을 한뒤 [i, k]를 떼낸 것과

같은지를 비교하는 방법으로 하였다. 

어쨋든 이것은 그냥 구현의 문제이다. 직관적으로 구현하면 O(N) 이 걸릴 것이다. 

그 다음으로 dp[i][k] 와 dp[k+1][j] 로 dp[i][j] 를 구하려면 어떻게 할까?

일단 순서가 어찌됐던간에 왼쪽 부분구간 [i, k] 에서는 swap을 (k - i) 번 할 것이고

오른쪽 부분구간 [k+1, j] 에서는 (j - k - 1)번 할 것이다. 그럼 어차피 이 둘은 독립적이고 서로에게 영향을 끼치지

않기 때문에 이 둘의 swap을 어떤 순서로 할 것인지의 문제이다.

그러면 순서가 정해져 있는 X색의 구슬 A개와 Y색의 구슬 B개를

각자 자신의 그룹에서의 순서에 맞게 섞는 방법은 A+B 개의 자리중에 X색 구슬의 자리 A개를 선택하는 방법의 수와

같으므로 \(_{A+B}C_{A}\) 와 같으므로 이 문제에서는 왼쪽, 오른쪽 구간에서 오름 차순 정렬을 하기 위한

순서가 정해져 있다면 그 각각의 순서를 유지하며 왼쪽, 오른쪽의 swap을 섞는 가짓수이므로

\(_{j-i-1}C_{k-i}\) 가지의 순서로 swap을 할 수가 있으며 왼쪽, 오른쪽 구간을 오름 차순 정렬하기 위한

swap 순서를 정하는 방법의 수는 각각 dp[i][k] 와 dp[k+1][j] 이므로 세개를 곱해주면된다. 즉,

\(lastK[i][j][k] = dp[i][k]\cdot{dp[k+1][j]}\cdot{_{j-i-1}C_{k-i}}\)

라는 식이 나온다. 그리고 [i, j) 인 모든 k 에 대해 lastK[i][j][k] 를 모두 더하면 dp[i][j] 가 나오는 것이다. 즉,

\(dp[i][j] = \sum_{k=i}^{j-1} {dp[i][k]\cdot{dp[k+1][j]}\cdot{_{j-i-1}C_{k-i}}}\)

라는 식이 나오게 되는 것이다.

마지막으로 시간복잡도를 계산해 보자.

우선 부분문제가 \(O(N^2)\) 개, 각 부분문제를 구할 때 \([i,\,j)\) 에 대해 마지막으로 swap 하는 지점 k를 

정해주기 때문에 \(O(N)\) 개의 k 후보가 있으며, k가 정해졌을 때 왼쪽부분과 오른쪽부분 각각을 오름차순정렬하여

마지막으로 k위치에서 swap만 한번 했을 때 결과적으로 두부분을 합친 구간이 오름차순 정렬되는지를

판별하기위해 \(O(N)\) 이 걸리기 때문에 전체 복잡도는 \(O(N^4)\) 가 된다.

#include <bits/stdc++.h>
#define REP(i,a,b) for(int i=a;i<=b;++i)
#define FOR(i,n) for(int i=0;i<n;++i)
#define pb push_back
#define all(v) (v).begin(),(v).end()
#define sz(v) ((int)(v).size())
#define inp1(a) scanf("%d",&a)
#define inp2(a,b) scanf("%d%d",&a,&b)
#define inp3(a,b,c) scanf("%d%d%d",&a,&b,&c)
#define inp4(a,b,c,d) scanf("%d%d%d%d",&a,&b,&c,&d)
#define inp5(a,b,c,d,e) scanf("%d%d%d%d%d",&a,&b,&c,&d,&e)
#define fastio() ios_base::sync_with_stdio(false),cin.tie(NULL)
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pll;
typedef vector<int> vi;    
typedef vector<ll> vl;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<pll> vll;
typedef vector<vector<int> > vvi;
typedef pair<int,pair<int,int> > piii;
typedef vector<piii> viii;
const double EPSILON = 1e-9;
const double PI = acos(-1);
const int MOD = 1e9+7;
const int INF = 0x3c3c3c3c;
const long long INFL = 0x3c3c3c3c3c3c3c3c;
const int MAX_N = 102;
 
class AdjacentSwaps {
public:
    ll nCr[53][53];
    ll dp[53][53];
    int N;
    vi P;
    ll go(int s, int e) {
        if (s == e) return 1;
        ll& cache = dp[s][e];
        if (cache != -1) return cache;
        cache = 0;
 
        vi se;
        REP(i, s, e) se.pb(P[i]);
        sort(all(se));
 
        REP(k, s, e - 1) {
            vi sorted;
            sorted.assign(P.begin() + s, P.begin()+ s + k - s + 1);
            sort(all(sorted));
            vi seSorted = se;
            swap(seSorted[k-s], seSorted[k-s + 1]);
            
            vi leftSorted;
            leftSorted.assign(seSorted.begin(), seSorted.begin() + k - s + 1);
            
            if (sorted != leftSorted) continue;
 
            cache = (cache + go(s, k) * go(k + 1, e) % MOD * nCr[e - s - 1][k - s]) % MOD;
        }
 
        return cache;
    }
    int theCount(vector<int> p) {
        N = sz(p);
        memset(dp, -1, sizeof(dp));
        memset(nCr, 0, sizeof(nCr));
        P = p;
        FOR(i, 53) nCr[i][0] = 1;
        REP(i, 1, 52) REP(j, 1, 52) nCr[i][j] = (nCr[i - 1][j] + nCr[i - 1][j - 1]) % MOD;
 
        int ret = (int)go(0, N - 1);
        return ret;
    }
};