kmjp's blog

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

TopCoder SRM 574 Div2 Medium TheNumberGameDiv2

さてDiv2 Medium。先のDiv1 Easyのアレンジ問題。
http://community.topcoder.com/stat?c=problem_statement&pm=12479

問題

2つの数値A,Bが与えられる。
Div1 Easyと異なり、今回は数値Aに対し、「10で割る」「数値を反転する」の作業を繰り返し、Bに一致させる。
必要な作業の最小量を答える。

解法

AをBにできるかどうかは、Div1同様AまたはAを反転した文字列にBが含まれるかで決まる。
AまたはAを反転した文字列にBが含まれる場合、含まれるBの両側にある文字列を切り落とす回数をカウントすればよい。

とはいえ、切り落とす回数は(Aの文字列長)-(Bの文字列長)固定で、後は反転の回数を数えるだけだね。

class TheNumberGameDiv2 {
	public:
	int minimumMoves(int A, int B) {
		char As[100],Bs[100],Br[100];;
		int AL,BL;
		sprintf(As,"%d",A);
		sprintf(Bs,"%d",B);
		AL=strlen(As);
		BL=strlen(Bs);
		
		int loop,x,y,mm=999;
		FOR(x,AL-BL+1) {
			if(strncmp(As+x,Bs,BL)!=0) continue;
			
			y=AL-BL;
			if(x>0) y+=2;
			mm=min(mm,y);
		}
		
		ZERO(Br);
		FOR(x,BL) Br[x]=Bs[BL-1-x];
		FOR(x,AL-BL+1) {
			if(strncmp(As+x,Br,BL)!=0) continue;
			mm=min(mm,1+AL-BL);
		}
		
		return (mm>=999)?-1:mm;
	}
};

まとめ

先こちらやってればDiv1 Easy落とさなかったのに…。
まぁ今言ってもしょうがないんだけど。

広告を非表示にする