解いた問題のソースコードと解説など。


SRM 574 Div1 Easy TheNumberGame

問題

プレーヤーが二人いて各々が数字をひとつ持っている。この数字は10進数表記で0を含んでいない。1ターンごとに交互の順番で以下の2つの操作のうち好きな方を選んで行う。

  1. 数字を逆順にする
  2. 数字を10で割る

先方のプレーヤーが1000ターン以内に後方の持つ数字と同じにできれば先方の勝ちになる。両者が最適に勝負をした時、先方は勝つことができるか。

やりかた

2つの数字は文字列として持っておくとわかりやすい。
後方の文字列が先方の文字列に含まれていない場合、後方が毎回逆順にする操作を行えば、数字が一致することは絶対にない。しかし含まれている場合、先方のプレーヤは逆順にしたり、最下位桁の文字を削ったりして後方のプレーヤの数字になるようにすることが必ずできる。

以下ソース。

string itos(int a){
  stringstream ss;
  ss << a;
  return ss.str();
}

class TheNumberGame {
public:
  string determineOutcome(int A, int B) {
    string result;
    string a = itos(A); string b = itos(B);
    
    bool good = false;
    if(a.find(b, 0) != string::npos) good |= true;
    reverse(ALL(b));
    if(a.find(b, 0) != string::npos) good |= true;
    return good ? "Manao wins" : "Manao loses";
  }
};
Get up! 明日のSUPER ST@R!