kmjp's blog

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

Good Bye 2013 : D. New Year Letter

少々めんどくさい問題。
http://codeforces.com/contest/379/problem/D

問題

N文字の文字列S[1]とM文字の文字列S[2]があるとする。
ここから、下記のとおりフィボナッチ数列の要領で文字列S[i]を生成する。
 S[i] = S[i-2] + S[i+1]
S[K]に"AC"という文字列がちょうどX回含まれるようにしたい。

K,X,N,Mが与えられたとき、条件を満たすS[1]とS[2]を作成せよ。

解法

まず、S[K]にもともとのS[1]とS[2]が何回含まれるかをカウントする。
S[1]とS[2]に最初から"AC"が含まれていれば、S[K]にはその分"AC"が含まれる。

また、S[1]・S[2]の末尾が"A"でS[1]・S[2]の先頭が"C"の場合、文字列の連結により"AC"が生成される可能性があるので、以下の4通りのケースがS[K]何個含まれるかもカウントする。

  • S[1]の末尾にS[1]の先頭が連結する。
  • S[1]の末尾にS[2]の先頭が連結する。
  • S[2]の末尾にS[1]の先頭が連結する。
  • S[2]の末尾にS[2]の先頭が連結する。

N,Mが高々100なので、後は

  • S[1]中の"AC"の数
  • S[2]中の"AC"の数
  • S[1]の先頭文字が"A","B","C"のいずれか
  • S[1]の末尾文字が"A","B","C"のいずれか
  • S[2]の先頭文字が"A","B","C"のいずれか
  • S[2]の末尾文字が"A","B","C"のいずれか

でループを回し、"AC"の数がXに一致するものを総当たりで探す。
総当たりで見つけたら、後は必要な数だけS[1]とS[2]の中を"AC"で埋め、残りを"B"にして出力する。

コーナーケースとして、NまたはMが1の時は先頭と末尾の文字が一致しないといけない点に注意。

int K,N,M;
ll X;
ll sl[110];
ll sln[110][2];
ll slhd[110][2];
ll slcn[110][4];

void solve() {
	int f,i,j,k,l,x,y;
	
	cin>>K>>X>>N>>M;
	sl[1]=N;
	sl[2]=M;
	sln[1][0]=1;
	sln[2][1]=1;
	slhd[1][0]=0;
	slhd[1][1]=0;
	slhd[2][0]=1;
	slhd[2][1]=1;
	
	
	for(i=3;i<=K;i++) {
		sl[i]=sl[i-2]+sl[i-1];
		slhd[i][0]=slhd[i-2][0]; //head
		slhd[i][1]=slhd[i-1][1]; //tail
		sln[i][0]=sln[i-2][0]+sln[i-1][0]; //nums1
		sln[i][1]=sln[i-2][1]+sln[i-1][1]; //nums2
		slcn[i][0]=slcn[i-2][0]+slcn[i-1][0]; // num s1-s1
		slcn[i][1]=slcn[i-2][1]+slcn[i-1][1]; // s1-s2
		slcn[i][2]=slcn[i-2][2]+slcn[i-1][2]; // s2-s1
		slcn[i][3]=slcn[i-2][3]+slcn[i-1][3]; // s2-s2
		slcn[i][slhd[i-2][1]*2+slhd[i-1][0]]++;
	}
	
	if(N==1 && M==1) {
		if(slcn[K][1]==X) _P("A\nC\n");
		else if(slcn[K][2]==X) _P("C\nA\n");
		else _P("Happy new year!\n");
		return;
	}
	
	string rr1,rr2;
	FOR(j,N) rr1+='B';
	FOR(j,M) rr2+='B';
	for(x=0;x<=N/2;x++) for(y=0;y<=M/2;y++) {
		ll tot=x*sln[K][0]+y*sln[K][1];
		
		string r1=rr1,r2=rr2;
		for(r1[0]='A';r1[0]<='C';r1[0]++) for(r2[0]='A';r2[0]<='C';r2[0]++) {
			FOR(i,3) FOR(j,3) {
				if(N==1 && r1[0]-'A' != i) continue;
				if(M==1 && r2[0]-'A' != j) continue;
				r1[N-1]='A'+i;
				r2[M-1]='A'+j;
				
				ll tot2=tot;
				if(r1[N-1]=='A' && r1[0]=='C') tot2+=slcn[K][0];
				if(r1[N-1]=='A' && r2[0]=='C') tot2+=slcn[K][1];
				if(r2[M-1]=='A' && r1[0]=='C') tot2+=slcn[K][2];
				if(r2[M-1]=='A' && r2[0]=='C') tot2+=slcn[K][3];
				
				if(tot2!=X) continue;
				
				l=N;
				if(r1[0]!='B') l--;
				if(N!=1 && r1[N-1]!='B') l--;
				if(2*x>l) continue;
				l=M;
				if(r2[0]!='B') l--;
				if(M!=1 && r2[M-1]!='B') l--;
				if(2*y>l) continue;
				l=(r1[0]!='B');
				FOR(k,x) {
					r1[l+k*2] ='A';
					r1[l+k*2+1] ='C';
				}
				l=(r2[0]!='B');
				FOR(k,y) {
					r2[l+k*2] ='A';
					r2[l+k*2+1] ='C';
				}
				cout << r1 << endl;
				cout << r2 << endl;
				return;
			}
		
		}
	}
	_P("Happy new year!\n");
}

まとめ

せっかくアプローチが良かったので、本番に正答したかったな。