yukicoder No.355 数当てゲーム(2)
解法
いろんな解き方があるような気がしますが, 以下のような解き方で解きました。
方針としては,
- 4 つの数字を確定する
- 4 つの数字の順列をすべて試す
とします。
4 つの数字は, 大きい数から順番に特定することにします。4 つすべての数が謎の時は,
0 1 2 num
というように数字を並べ, x+y が最大になる num の中で最も大きい数を選びます(最も大きい数を選ぶのは重要)。3 つの数が謎の時は,
know 0 1 num (know は知ってる数)
というように数字を並べ, x+y が最大になるものを選びます。以下同様です。
順列を試すのは next_permutation を使えば大丈夫です。
int ans[] = {-1, -1, -1, -1}; void readXY(int& x, int& y) { cin >> x >> y; if (x==4 && y==0) exit(0); } bool NG(const vi& ok, int num) { for (int el : ok) if (num==el) return true; return false; } int main() { vector<int> ok; for (int t = 0; t < 4; t++) { int atLeast = 3-ok.size(); vector<int> tmp(10); int maxi = 0; for (int num = atLeast; num < 10; num++) { if (NG(ok, num)) continue; // 確定してるやつ for (int el : ok) { cout << el << " "; } for (int i = 0; i < atLeast; i++) cout << i << " "; cout << num << endl; int x, y; readXY(x, y); tmp[num] = x+y; maxi = max(maxi, x+y); } for (int num = 9; num >= atLeast; num--) { if (tmp[num] == maxi) { ok.push_back(num); break; } } } sort(ok.begin(), ok.end()); do { for (int i = 0; i < 4; i++) { cout << ok[i]; if (i < 3) cout << " "; } cout << endl; int x, y; readXY(x, y); } while (next_permutation(ok.begin(), ok.end())); return 0; }