Google Code Jam 2015 Qualification Round : C. Dijkstra

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

問題

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

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

解法

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

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

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

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を切り落としたけど、正解できてよかった。