[IOI2014 Day2] Gondola 해법

이 문제는 여러 개의 부분 문제(서브태스크)가 하나의 문제를 이루어, 이 문제를 해결하기 위해서 3개의 코드를 짜야한다. 문제의 난이도는 매우 쉬운 편이며, 3개의 방법에 대해서 꼼꼼히 생각해야 되기 때문에 귀찮은 문제라고 생각한다.

1) 곤돌라 수열 확인

우선 곤돌라 수열에서 같은 수가 여러 개 있는 경우 이는 자명히 불가능한 곤돌라 수열이다.

그렇지 않은 경우, 주어진 곤돌라 수열에 있는 1 이상 $n$ 이하의 수에 신경써야한다. 곤돌라 수열에 1 이상 $n$ 이하의 수가 없다면, 이는 항상 가능한 곤돌라 수열이다.

만약 1 이상 $n$ 이하의 수가 하나라도 있다면, 초기 1의 위치를 짐작할 수 있으며, 다른 1 이상 $n$ 이하의 수가 그 1의 위치에 대해 상대적으로 올바른 위치에 있는지 확인하면 된다.

2) 교체 수열

가능한 교체 수열 중 한 가지만 구하면 되는 것이므로 매우 간단하게 풀리는 문제다. 문제의 조건에서 불가능한 곤돌라 수열은 주어지지 않으므로 따로 확인하지 않아도 된다.

1)에서 말했듯이 1이상 $n$ 이하의 수를 통하여 초기 1의 위치를 유추한다. 만약 그러한 수가 없다면, 1의 위치를 0 번지라고 가정하여도 상관 없다. 교체 수열을 구하기 위해 초기 1의 위치를 통해 초기 곤돌라 수열을 구하고 $n+1 \leq i \leq m$ (여기서 $m$은 주어진 곤돌라 수열에서 가장 큰 값)인 $i$를 곤돌라 수열의 어느 위치에 교체할 것인지 적절히 계산하면 된다. 자명하게도 교체 수열의 길이는 $m-n$ 이다.

3) 교체 수열의 개수 세기

우선, 1)의 함수를 통하여 가능한 곤돌라 수열인지 확인한다. 만약 불가능한 곤돌라 수열이라면 교체 수열의 개수는 0 이다. 이제 곤돌라 수열에서 $n$보다 큰 값을 모아 오름차순으로 정렬하고 이를 수열 $a$라고 하자. 처음 $x = n$이라고 하고, $a[0]$ 부터 순서대로 처리한다. $a[0] > x+1$ 인 경우 $x$와 $a[0]$ 사이에 교체되어야 하는 수가 있다는 것이고 그것의 개수가 $a[0]-x-1$ 이다. 그 교체되는 값이 들어갈 수 있는 자리의 수가 $y$개라고 하면, 가능한 경우의 수는 $y^{a[0]-x-1}$ 이다. 이는 repeated squaring 을 통해 빠르게 계산할 수 있다. $a[0]$에 대한 처리는 끝났으며, $x = a[0]$으로 대입하고 $a[1]$에 대한 처리로 넘어간다. 이를 반복하면 된다.

#include <map> #include <vector> #include <algorithm> using namespace std; #define MAXN 100000 #define pb push_back #define sz(v) ((int)(v).size()) #define all(v) (v).begin(),(v).end() typedef long long lld; static const int MOD = 1e9 + 9; static int tmp[MAXN]; int valid(int n,int inputSeq[]) { int i,j,p = -1; for (i=0;i<n;i++){ tmp[i] = inputSeq[i]; if (inputSeq[i] <= n){ j = (i-inputSeq[i]+1+n)%n; if (p < 0) p = j; else if (p != j) return 0; } } sort(tmp,tmp+n); for (i=1;i<n;i++) if (tmp[i-1] == tmp[i]) return 0; return 1; } int replacement(int n,int gondolaSeq[],int replacementSeq[]) { if (!valid(n,gondolaSeq)) return -1; int i,j,p = -1; for (i=0;i<n;i++){ if (gondolaSeq[i] <= n){ j = (i-gondolaSeq[i]+1+n)%n; if (p < 0) p = j; else if (p != j) return 0; } } int y=0; for (i=0;i<n;i++) if (gondolaSeq[i] > n){ if (y < gondolaSeq[i]) y = gondolaSeq[i]; } if (!y) return 0; map<int,int> pos; for (i=0;i<n;i++) pos[gondolaSeq[i]] = i; if (p == -1) p = 0; int c = 0, t = pos[y]; for (i=0;i<n;i++) tmp[i] = (i-p+n)%n+1; for (i=n+1;i<=y;i++){ int x = pos.count(i) ? pos[i] : t; replacementSeq[c++] = tmp[x]; tmp[x] = i; } return y-n; } int pow(int a,int b) { int ret = 1,t = a,i; for (i=0;i<31;i++,t=(lld)t*t%MOD) if (b&(1<<i)){ ret = (lld)ret*t%MOD; } return ret; } int countReplacement(int n,int inputSeq[]) { if (!valid(n,inputSeq)) return 0; int ret = n,last = n,i; vector <int> a; for (i=0;i<n;i++){ if (inputSeq[i] <= n) ret = 1; else a.pb(inputSeq[i]); } sort(all(a)); int left = sz(a); for (i=0;i<sz(a);i++){ int dummy = a[i] - last - 1; ret = ((lld)ret*pow(left,dummy))%MOD; last = a[i]; left--; } return ret; }