SRM 606 Div2 Medium EllysNumberGuessing

問題

SRM 606 - TopCoder Wiki

Aさんがある数を思い浮かべて,Bさんがその数を予想する.AはBが指摘した数と自分が思い浮かんだ数の差を答える. 複数回,この試行をした時,Aが思い浮かべた数がわかるならその数を分かるならその数を,複数あるなら-1を,Aの答えが嘘を付いているなら-2を返す.

解答

一回答えた時点で,答えの候補は2つしか無い. もしも試行を繰り返した時,この両者に食い違うなら嘘を付いている.

残りは単純な分岐なので略.

入力が重複する場合などもあるため,処理は少々面倒. 解説のように正解の数を全て考え検証する方法はとても楽. 無理矢理過ぎる感はあるが.

class EllysNumberGuessing
{
public:
  int getNumber(vector <int> guesses, vector <int> answers)
    {
      vector<int>g, a;
      int n = guesses.size();
      for(int i = 0; i < n; i++){
        bool foundSame = false;
        for(int j = i + 1; j < n; j++){
          if (guesses[i] == guesses[j] && answers[i] == answers[j]){
            foundSame = true;
          }
        }
        if (!foundSame){
          g.push_back(guesses[i]);
          a.push_back(answers[i]);
        }
      }
      guesses = g;
      answers = a;
      n = guesses.size();
      int uplimit = 1000000000;
      int lowlimit = 1;
      if (n == 1){
        if (guesses[0] + answers[0] > uplimit && guesses[0] - answers[0] >= lowlimit) return guesses[0] - answers[0];
        else if (guesses[0] + answers[0] <= uplimit && guesses[0] - answers[0] < lowlimit) return guesses[0] + answers[0];
        else if (guesses[0] + answers[0] > uplimit && guesses[0] - answers[0] < lowlimit) return -2;
        return -1;
      }
      int up = guesses[0] + answers[0];
      int low = guesses[0] - answers[0];
      bool allsame = true;
      for(int i = 0; i < n; i++)
        if (guesses[i] + answers[i] != up &&
            guesses[i] - answers[i] != up) allsame = false;
      if (up <= uplimit && allsame) return up;
      allsame = true;
      for(int i = 0; i < n; i++)
        if (guesses[i] - answers[i] != low &&
            guesses[i] + answers[i] != low) allsame = false;
      if (low >= 1 && allsame) return low;
      return -2;
    }
};