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

kmjp's blog

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

TopCoder SRM 574 Div1 Easy TheNumberGame

SRM

ああ、またやってしまった。Easyで凡ミスしたうえチャレンジミスしてスコアマイナス。
まさかの青コーダー戻り。最近このEasyミス+チャレンジミス多いぞ。

とはいえまずは復習。Div1 Easyから。
http://community.topcoder.com/stat?c=problem_statement&pm=12474

問題

両プレイヤーは、それぞれAとBの整数を持っている(途中の桁に0は含まない)。
Aを持つプレイヤーから開始し、交互に以下の処理のいずれかを行う。

  • 数値を10で割る(小数点以下切り捨て)
  • 数値をひっくり返す

プレイ中、両プレイヤーの数値が一致したら先手のプレイヤーが勝ち、一致しないなら後手が勝ちである。
両プレイヤーが最適手を取るときの勝者を答える。

解法

各プレイヤーの手順は2通りしかないので、相手がどちらを実行して自分が勝ちになるような最適手をDFSで求めようとしたが、ブール演算をミスしてACならず。

実はこれはすごく簡単で、Aを文字列にしたとき、Bまたはその逆の文字列を含むなら先手がかつ。
まず、Aは2つの手順を繰り返すことでA中にあるBまたはその逆の文字列を残し、両端の文字を消すことができる。
途中後手がBを10で割って1文字落としてもAがBまたはその逆の文字列を持つことは変わらない。
また、文字を落としすぎると最後0になって結局Aに追いつかれる。

char As[100],Bs[100];
int AL,BL;

class TheNumberGame {
	public:
	string determineOutcome(int A, int B) {
		char As[100];
		char Bs[100],Br[100];
		
		sprintf(As,"%d",A);
		sprintf(Bs,"%d",B);
		int L=strlen(Bs);
		int i;
		FOR(i,L) Br[L-1-i]=Bs[i];
		Br[L]=0;
		
		if(strstr(As,Bs) || strstr(As,Br))
			return "Manao wins";
		return "Manao loses";
		
	}
};

まとめ

終わってみれば非常に単純な問題。
275ptに騙された…。いやもしかしたら地道なDFSが想定解法なのかもしれんが。
ほんと自分はこういうミス多いな…。

広告を非表示にする