読者です 読者をやめる 読者になる 読者になる

kmjp's blog

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

Google Code Jam 2015 Qualification Round : C. Dijkstra

GCJ

よくまぁDijkstraという単語からこんな問題を思いつくな。
https://code.google.com/codejam/contest/6224486/dashboard#s=p2

問題

"ijk"で構成されるL文字の文字列SとXが与えられる。
SをX回繰り返した文字列をTとする。

Tを3つの部分文字列に分割した場合、各文字を四元数と考えて各部分文字列の積を取った場合、各部分文字列が"i","j","k"になるか求めよ。

解法

同じ文字列を2回繰り返すと1か-1になり、4回繰り返すと1になる。
よってXが大きい時は、Xを4引いたときと同じ結果になると考えてよい。
下記コードでは、Xが大きいときは X=8+(X-8)%4でXを12未満にするよう前処理している。

あとはTを1文字ずつ処理していく。
四元数の乗算表に用いて先頭から掛け合わせて行き、iが出来たら1つ目の部分文字列終了。
その後また掛け合わせてjができたら2つ目の部分文字列終了。
最後残りがkになるか判定する。

初回の部分文字列について、iになるタイミングが複数あるかもしれないが最初にiになった時点で終了してよい。
なぜなら、T[0..x]もT[0..y]も掛け合わせてiになるということはT[(x+1)..y]=1ということであり、1つ目の部分文字列に入れても2つ目の部分文字列に入れても掛け合わせる過程で消えるので問題ない。

int mult(int cur,char c) {
	int minu=(cur<0);
	cur=abs(cur);
	
	if(cur==1) {
		if(c=='i') cur=2;
		if(c=='j') cur=3;
		if(c=='k') cur=4;
	}
	else if(cur==2) {
		if(c=='i') cur=1, minu^=1;
		if(c=='j') cur=4;
		if(c=='k') cur=3, minu^=1;
	}
	else if(cur==3) {
		if(c=='i') cur=4, minu^=1;
		if(c=='j') cur=1, minu^=1;
		if(c=='k') cur=2;
	}
	else if(cur==4) {
		if(c=='i') cur=3;
		if(c=='j') cur=2, minu^=1;
		if(c=='k') cur=1, minu^=1;
	}
	
	if(minu) cur=-cur;
	return cur;
}

void solve(int _loop) {
	int f,i,j,k,l,x,y; string s;
	ll L,X;
	string S;
	
	cin>>L>>X;
	cin>>s;
	
	if(X>8) X=8+(X-8)%4;
	S="";
	FOR(i,X) S+=s;
	
	int state=0, cv=1;
	FOR(i,S.size()) {
		cv=mult(cv,S[i]);
		if(state==0 && cv==2) state=1, cv=1;
		if(state==1 && cv==3) state=2, cv=1;
	}
	
	_P("Case #%d: %s\n",_loop,(state==2&&cv==4)?"YES":"NO");
}

まとめ

大ざっぱにXを切り落としたけど、正解できてよかった。

広告を非表示にする