SRM606 Div1 Easy & Div2 Medium "EllysNumberGuessing"
問題
TopCoder Statistics - Problem Statement
訳
エリーとクリスは次のようなゲームで遊んでいる。まずクリスが1から10^9までの数を思い浮かべる。そうしたら、エリーはその数を当てることに挑戦する。エリーがクリスに数を伝えると、クリスは正解の数と、エリーの言った数がどれだけ離れているかを絶対値としてエリーに伝える。これが1ラウンドとなる。今、エリーはこれまでの結果から、正解の数が1つに特定できるかどうか気になっている。
あなたはint[] guesses、answersが与えられる。guesses[i]はエリーがiラウンド目にクリスに伝えた数を表し、answers[i]は、iラウンド目のエリーの数に対して返した数を表す。もし、正解の数が1つに特定できるのであれば、その数を返せ。正解の数の候補がいまだに2つ以上あれば、-1を返せ。もしクリスがウソを言っているのであれば、-2を返せ。
制約
1 <= ラウンド数 <= 50
考えたこと
- 1ラウンド目
正解となる数が多くとも2つまでに絞られる。
- 2ラウンド目以降
正解となる数に合わない→ウソ
ソースコード
using namespace std; class EllysNumberGuessing { public: int getNumber(vector <int> guesses, vector <int> answers) { int N = guesses.size(); int ans[2]; int count = 0; for (int i = 0; i < N; i++) { // 候補の数字 int a = guesses[i] + answers[i]; int b = guesses[i] - answers[i]; // 初回 if (i == 0){ if (1 <= a && a <= 1000000000) { ans[count++] = a; } if (1 <= b && b <= 1000000000) { ans[count++] = b; } // 候補がない?ウソだ! if (count == 0) return -2; continue; } // 正解の数が1つに絞られているとき if (count == 1){ // 正解の数と合わない?ウソだ! if (ans[0] != a && ans[0] != b) return -2; continue; } // 正解の数が、まだ2つ可能性があるとき bool b0 = ans[0] == a || ans[0] == b; bool b1 = ans[1] == a || ans[1] == b; if (b0){ if (b1){ } else{ // 正解の数1に絞られた count--; } } else{ if (b1){ // 正解の数2に絞られた ans[0] = ans[1]; count--; } else{ // どっちにも合わない?ウソだ! return -2; } } } return count == 2 ? -1 : ans[0]; } };