TopCoder SRM 606 Div1 Easy EllysNumberGuessing
問題
A, Bが数当てゲームをする。
Aは1以上10億以下の数を思い浮かべ、Bがそれに対して質問する。
Bの質問は一つの数字の形式で、それに対して、Aは(自分の思い浮かべた数) - (Bの言った数)の絶対値を答える。
Bの質問とそれに対するそれぞれのAの答えが与えられるとき、
Aの思い浮かべた数が一意に定まるならその数を、
候補が複数あるなら-1を、Aが嘘をついてるなら-2を出力せよ。
制約条件
guess[i]≦10億
answer[i]≦10億
方針
最初の質問で候補は2通りに絞れる。
すなわちguess[0] + answer[0]またはguess[0] - answer[0]か。
(1以上10億以下の条件を満たさないなら捨てる)
それぞれの候補に対して、実際にAの返答を計算してみて矛盾がないかを見る。
というのが楽な気がする。
自分はなんか、2通りの候補から矛盾するやつを消していくところで変なことやった。
ソースコード
bool ok(int n){ return 1 <= n && n <= (int)1e9; } class EllysNumberGuessing { public: int getNumber(vector <int> guesses, vector <int> answers) { int n = guesses.size(); set<int> cand; if(ok(guesses[0] + answers[0])) cand.insert(guesses[0] + answers[0]); if(ok(guesses[0] - answers[0])) cand.insert(guesses[0] - answers[0]); for(int i = 1; i < n; i++){ set<int> cand2; vi del; if(ok(guesses[i] + answers[i])) cand2.insert(guesses[i] + answers[i]); if(ok(guesses[i] - answers[i])) cand2.insert(guesses[i] - answers[i]); each(j, cand) if(!cand2.count(*j)) del.pb(*j); rep(j, del.size()) cand.erase(del[j]); } if(cand.size() == 0) return -2; if(cand.size() > 1) return -1; return *cand.begin(); } };