Hatena::Grouptopcoder

kuuso1の日記

2015-02-03

SRM648 div2Hard ABC

| 23:34 | SRM648 div2Hard  ABC - kuuso1の日記 を含むブックマーク はてなブックマーク - SRM648 div2Hard  ABC - kuuso1の日記

http://community.topcoder.com/stat?c=problem_statement&pm=13645&rd=16312

  • 整数NとKが与えられる
  • 'A', 'B', 'C' からなるN文字の文字列のうち、i文字目とj文字目( i<j )が真に昇順になっているペアの数がK個となる文字列を答えよ</li>
  • そのような文字列がない場合は空文字列を返す

(制約)3 ≤ N ≤ 30, 0 ≤ K ≤ N*(N-1)/2

方針:(本番考えた方法)

文字を追加した際に、ペアの数がどう変化するかを考えると、下図のように

f:id:kuuso1:20150203231448p:image

・Aを追加する→ペアの数は不変

・Bを追加する→ペアの数は元の文字列のAの個数分だけ増加

・Cを追加する→ペアの数は元の文字列のAの個数とBの個数分だけ増加

となる。一方で、A、B、Cの個数だけではペアの個数が確定しないが、ペアの個数を覚えておけば上記の要領で計算できる。

まではよかったが、本番はそれを配列DPでやろうとして、

bool[][][][] dp;//dp[t][a][b][c]:Aをa個,Bをb個,Cをc個でt個の昇順ペアを持つ文字列を作ることが出来るか(false,true)
dp[0][0][0][0]=true;
for(int t=0;t<=N*(N-1)/2;t++){
	for(int i=0;i<N;i++){
		for(int j=0;j<N;j++){
			for(int k=0;k<N;k++){
				if(i+j+k>=N)continue;
				if(dp[t][i][j][k]==false)continue;
				dp[t][i+1][j][k]=true;
				dp[t+i][i][j+1][k]=true;
				dp[t+i+j][i][j][k+1]=true;
			}
		}
	}
}

でまず作れるかを判定して、作れるものは経路復元で解を作ろうとして撃沈。。。

(本番後考察)

そもそもdpテーブルがboolなので、経路復元で渡り歩くくらいなら最初からメモ化再帰でトレースできるんじゃ・・・

→できた。

public class ABC {
	public string createString(int N, int K) {
		NN=N;KK=K;
		memo=new bool[(N*(N-1)/2)+1,N+1,N+1,N+1];
		Ans="";
		found=false;
		dfs(0,0,0,0,"");
		return Ans;
	}
	int NN,KK;
	String Ans;
	bool[,,,] memo;
	bool found;
	
	void dfs(int t,int a,int b,int c,String s){
		if(found)return;
		memo[t,a,b,c]=true;
		if(a+b+c==NN){
			if(t==KK){found=true;Ans=s;}
			return;
		}
		if(a+b+c<NN){
			if(!memo[t,a+1,b,c])dfs(t,a+1,b,c,s+"A");
			if(!memo[t+a,a,b+1,c])dfs(t+a,a,b+1,c,s+"B");
			if(!memo[t+a+b,a,b,c+1])dfs(t+a+b,a,b,c+1,s+"C");
		}
	}
}

・この前yukicoderで教えてもらった、「配列DPは幅優先、メモ化再帰は深さ優先のイメージ」っていうの少しわかってきた気がする。

・(C#の話)配列をなめる必要がある時はジャグ配列でちゃんと個々に1次元配列を生成したほうが速度的に有利だけど、メモみたいに1回しかアクセスしない奴は多重配列使った方がいいな。

・ちなみにN=30で、配列DPだと12000000くらいの領域を確保して走査するけど、実際にメモ化で訪れ得るノード数は717464とかなり疎なグラフのようでした。

 メモ化再帰なかなか慣れないけど、初AC目指して精進します。