yukicoder : No.438 Cwwプログラミング入門

遅れて参加したけど、ギリギリ全完出来て良かった。
http://yukicoder.me/problems/no/438

問題

整数X,Y,Zが与えられる。
以下の４種類の命令からなるスタックマシンにおいて、10000回以下の命令でスタックの最上位をZに出来るか判定せよ。

• スタック最上位にXを積む
• スタック最上位にYを積む
• スタック最上位の２つの値を抜き出し、その和をまた最上位に積む
• スタック最上位の２つの値を抜き出し、最上位から1つ目のものから2つ目のものを引いた値をまた最上位に積む

解法

まずコーナーケースを片付けておく。

• Z==0の場合、Xを２回積んで差を取ればよい。
• X,Yのうち片方だけ使えばいい場合、すなわちZがXやYの倍数の場合、その数だけXやYを積んで和を取る。命令数が10000を超えないかは要チェック。

X*a+Y*b=Zを満たす整数a,bを求めよう。
命令長の上限が10000なので、|a|や|b|の上限は10000である。(正確には加減算も必要なので|a|+|b|は5000以下)
そのためaを-10000～10000総当たりし、対応するbが存在するか求めてみる。

存在する場合、2*(|a|+|b|)-1個の命令でZを作れるので、それが10000以下なら解が存在する。

• aもbも正なら、Xをa個、Yをb個積んで(a+b-1)回和を取ればよい。
• aが正でbが負なら、Yをb個積んで(b-1)回和を取り、Xをa個積んで(a-1)回和を取り、最後のその差を取る。
• aが負でbが正なら、Xをa個積んで(a-1)回和を取り、Yをb個積んで(b-1)回和を取り、最後のその差を取る。

ll X,Y,Z;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>X>>Y>>Z;
	if(Z==0) return _P("ccW\n");
	if(X==0 && Y==0) return _P("mourennaihasimasenn\n");
	
	if(Y && Z%Y==0 && 2*(Z/Y)-1<=10000) {
		x = Z/Y;
		cout<<string(x,'w')<<string(x-1,'C')<<endl;
		return;
	}
	if(X && Z%X==0 && 2*(Z/X)-1<=10000) {
		x = Z/X;
		cout<<string(x,'c')<<string(x-1,'C')<<endl;
		return;
	}
	if(X==0 || Y==0) return _P("mourennaihasimasenn\n");
	
	for(i=-10000;i<=10000;i++) {
		ll B=Z-X*i;
		if(B%Y) continue;
		ll C=B/Y;
		if((abs(i)+abs(C))*2-1>10000) continue;
		if(i>0 && C>0) {
			cout<<string(i,'c')<<string(C,'w')<<string(i+C-1,'C')<<endl;
			return;
		}
		else if(i<0) {
			cout<<string(abs(i),'c')<<string(abs(i)-1,'C')<<string(C,'w')<<string(abs(C)-1,'C')<<"W"<<endl;
			return;
		}
		else if(C<0) {
			cout<<string(abs(C),'w')<<string(abs(C)-1,'C')<<string(abs(i),'c')<<string(abs(i)-1,'C')<<"W"<<endl;
			return;
		}
	}
	
	_P("mourennaihasimasenn\n");
	
	
}

まとめ

最初互除法のコードを書いてしまった。