ああ、またやってしまった。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が想定解法なのかもしれんが。
ほんと自分はこういうミス多いな…。