kmjp's blog

競技プログラミング参加記です

AtCoder ARC #053 : D - 2 つの山札

ARC

TopCoderで似た問題見たけど、解法は全然違った。
http://arc053.contest.atcoder.jp/tasks/arc053_d

問題

1～Nのpermutationである数列２つA,Bが与えられる。
これらの数列に対し以下の処理を計(2N-2)回行い、別の数列を作る。

  • A,Bのどちらかを選択する。ただし長さが1の方は選択できない。
  • 選択した方の先頭要素を作成中数列の末尾に加え、しなかった方の先頭要素はA,Bから取り除く。

作れる数列は何通りあるか。

解法

Editoralの解法はいまいち理解しきれなかったので、sigma425氏のコードを参考に別解で解いた。
ただ途中過程はEditorialと同じ。
http://arc053.contest.atcoder.jp/data/arc/053/editorial.pdf

以下行・列・配列添え字は0-originで書く。
Editorialのように、縦横N本の線分からなるグリッドを考える。
左上の点から右下の点に隣接点を辿り移動することを考える。
各線分では、上からa行目の線分にはA[a]、左からb列目の線分にはB[b]に相当する数値がラベル付されているとする。
こう考えると、線分を通るたびにそのラベルの内容を末尾に加えていったものが作成した数列となる。

…ここまではEditorialと同じだが、ここから変わる。
以下左上からa行b列の交点を(a,b)と表現する。
dp[a][b] := (a,b)の交点に到達するとき、そこまでの過程で作れるユニークな数列数
を考える。dp[N-1][N-1]が求めたい値である。
まず同じ数列を重複してカウントして良いなら、dp[a][b]は単純な組み合わせ計算でdp[a][b]=dp[a-1][b]+dp[a][b-1]となる。
ここから同じ数列が来るパターンを取り除こう。

移動経路が異なるのに、作成中の数列の末尾何要素が重複するケースはそもそも何通りあるか。
(a-k,b-k)→(a,b)と移動するとき、行と列が対角線に対象となっている数をpとする。
例えばテストケース3は、(0,0)→(4,4)に移動する際0行・0列、2行・2列、4行・4列が一致するのでp=3である。
これらの列・行だけを通って移動する場合、対角線に対称な経路を通っても同じ数列ができる。
よって、そのような経路の組み合わせは半分だけしかカウントしてはならない。

そこで、dp[4][4]から以下の値を引く。

  • (2,2)から一致する2行・2列目・4行・4列目だけを通り、かつ対角線の右上側だけを通って(4,4)に至る経路の組み合わせをSとするとS*dp[2][2]を引く。
  • (0,0)から一致する0行・0列・2行・2列目・4行・4列目だけを通り、かつ対角線の右上側だけを通って(4,4)に至る経路の組み合わせをTとするとT*dp[0][0]を引く。

まとめると、A[a-k]==B[b-k]となるkがあったとき、そのようなkが小さい順にp個目だったとするとf(p)*dp[a-k][b-k]を引いていけば良い。
f(p)はp行p列のグリッドを対角線の右上側だけ通っていく経路の数であり、これはO(p^2)で求められる。

int N;
int A[2010],B[2010];
ll mo=1000000007;
ll dp[2010][2010];
ll lesspat[2010][2010];

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N;
	FOR(i,N) cin>>A[i];
	FOR(i,N) cin>>B[i];
	
	FOR(y,N+1) {
		lesspat[0][y]=1;
		FOR(x,N+1) {
			if(x+1<y) (lesspat[x+1][y] += lesspat[x][y])%=mo;
			(lesspat[x][y+1] += lesspat[x][y])%=mo;
		}
	}
	
	dp[0][0]=1;
	FOR(y,N) FOR(x,N) {
		ll& ret=dp[x][y];
		if(x||y) ret = (((x)?dp[x-1][y]:0)+((y)?dp[x][y-1]:0))%mo;
		
		if(A[x]==B[y]) {
			int same=0;
			i=x-1,j=y-1;
			while(i>=0 && j>=0) {
				if(A[i]==B[j]) same++, ret += mo-dp[i][j]*lesspat[same-1][same]%mo;
				i--, j--;
			}
		}
		ret %= mo;
	}
	
	cout<<dp[N-1][N-1]<<endl;
}

まとめ

SRMで見た類似問題と問題設定がちょっとだけしか変わってない気がするけど、解法が全く異なるのは面白い。
…今後kyuridenamida系の名前には触れないようにします。