SRM517 Div1 Medium(600) AdjacentSwaps
それぞれのカードの移動前の後の位置から、ウサギが呼ばれる順番の満たす制約が得られる。例えば4番目の例の
1, 3, 0, 5, 2, 7, 4, 8, 10, 6, 12, 9, 14, 11, 16, 13, 18, 15, 19, 17
だと、3が3番目から1番目に移動していることで、数字をウサギの番号として、2→1と0→1と2→3という制約が、6が6番目から9番目に移動していることで、6→7→8と6→5と9→8という制約がかかる。移動の間のウサギは移動方向と同じ順番に呼ばれ、両端のウサギは逆順に呼ばれる。3→4と4→3というような矛盾する制約があったら答えは0。例の制約を図にすると以下のようになる。
1, 3, 0, 5, 2, 7, 4, 8, 10, 6, 12, 9, 14, 11, 16, 13, 18, 15, 19, 17 0→ 1← 2→ 3← 4→ 5← 6→ 7→ 8← 9→10←11→12←13→14←15→16←17→18
この制約を満たすウサギの並び順の総数が答え。動的計画法で求める。i番目までのウサギを並べた時にi番目のウサギがj番目に呼ばれる場合の数を覚えておく。
#include <vector> #include <numeric> using namespace std; class AdjacentSwaps{public: int theCount( vector <int> p ) { int M = 1000000007; int n = (int)p.size(); vector<int> D(n); for ( int i=0; i<n; i++ ) { if ( i==p[i] ) return 0; int d = p[i]<i ? 1 : -1; vector<int> t(n); t[p[i]] = -d; for ( int j=p[i]+d; j!=i; j+=d ) t[j] = d; t[i] = -d; for ( int j=1; j<n-1; j++ ) if ( t[j]!=0 ) { if ( D[j]!=0 && D[j]!=t[j] ) return 0; D[j] = t[j]; } } // T[i][j]: q[0], q[1], ……, q[i]を並べてq[i]がj番目にある場合の数 vector<vector<long long> > T( n-1, vector<long long>( n-1 ) ); T[0][0] = 1; for ( int i=1; i<n-1; i++ ) for ( int j=0; j<=i; j++ ) { if ( D[i] > 0 ) for ( int k=0; k<j; k++ ) T[i][j] += T[i-1][k]; else for ( int k=j; k<i; k++ ) T[i][j] += T[i-1][k]; T[i][j] %= M; } return (int)(accumulate(T[n-2].begin(),T[n-2].end(),0ll)%M); }};