これもコードは短いのよね。
http://arc068.contest.atcoder.jp/tasks/arc068_d
問題
1～Nの数字が書かれたカードが順に並んでいる。
このカードをdequeを使い以下の手順で並び替える。
- カードを数字の小さい順にdequeの前後どちらかに追加していく。
- 全部追加し終わったら、dequeの前後どちらかからカードを抜きだし、抜き出した順に並べていく。
こうして得られるカード列のうち、1のカードがK枚目に来るものは何通りあるか。
解法
下記サイトの解説がわかりやすい。
ARC #068-F : Solitaire - 問題解決の宝石箱
…ので、これ以上書く必要もないが一応書いておく。
dequeにカードをすべて追加すると、deque内のカードの数字は外側から1のカードに向けて単調減少列を成す。
ここから順にカードを取り除いていくので、1のカードが出るまでのカード列は、最大で２つの単調減少列に分解できる。
1のカードを抜き出す直前を考える。
1のカードがK枚目に来るということは、その直前、残り(N-K+1)毎のカードがdequeにある。
また、残されたカードは前後の端どちらかに1があり、反対側に向けて単調増加列を成す。
以下、1のカードを抜き出す前と抜き出した後をそれぞれ考えよう。
1のカードを抜きだすまでのカードは2つの単調減少列を成すと書いたが、カードを追加する場合は可能なら1つめに追加する、とすることにしよう。
たとえば9,6,8,5,7,4という数列は[9,8,7][6,5,4]の２つの単調減少列に分解できる。
ここに3を追加して9,6,8,5,7,4,3という数列を考えた場合、２の減少列のどちらに追加しても単調減少列を成すが、その場合は1つめの方を優先して追加するとする。
こうすると同じ数列を分解の仕方の際で多重にカウントすることを回避できる。
上記のとおり、1のカードを抜きだすまでに(N-K+1)枚のカードが残るので、2～Nのカードのうち２つの単調減少列に取り込まれないカードもある。
これらを余剰カードとよぼう。
ここで以下の状態を考える。
dp(n, k, b) := nより大きな数字のカードを処理した後、k枚余剰カードになっている。またbは直前のカードを余剰カードにしたかどうかを示す真偽値とする。その場合におけるカードの組み合わせ数。
初期状態ではdp(N,0,0)=1である。ここから、1以上のカードを処理し、余剰カードが(1を除くので)N-K毎となる状態dp(1,N-K,false)+dp(1,N-K,true)をDPで求めておこう。
この時、n枚目のカードの扱いにより以下のように遷移する。
- n枚目のカードを即座に1つめの単調減少列の末尾に加えるケース: dp(n-1,k,false) += (dp(n,k,false)+dp(n,k,true))
- n枚目のカードを余剰カードとするケース: dp(n-1,k+1,true) += (dp(n,k,false)+dp(n,k,true))
- 余剰カードのうち最大の値のカードを引っ張り出し2つめの単調減少列に追加する: dp(n,k-1,false) += (dp(n,k,false))
- このケースは、直前に余剰カードにしたばかりのカードを使うことはできない。その場合は最初から1つめの単調減少列に加える場合と同じであるためである。
これでdp(1,N-K,false)+dp(1,N-K,true)によりK枚目までの並び方が決まった。
残り(N-K)毎の順だが、あとは左右どちらかから取り除くのを最後の1枚以外2択で選んでいくだけなので2^(N-K-1)通り。
ll dp[2020][2020][2]; ll mo=1000000007; int N,K; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>K; dp[N][0][0]=1; for(i=N;i>=1;i--) { for(j=N;j>=0;j--) { (dp[i-1][j][0]+=dp[i][j][0]+dp[i][j][1])%=mo; (dp[i-1][j+1][1]+=dp[i][j][0]+dp[i][j][1])%=mo; if(j) (dp[i][j-1][0]+=dp[i][j][0])%=mo; } } ll ret=(dp[1][N-K][0]+dp[1][N-K][1])%mo; FOR(i,N-K-1) (ret*=2)%=mo; cout<<ret<<endl; }
まとめ
コード短いなぁ。
