AOJ 2940 場所当てゲーム (RUPC 2019 day1-D)

発想はすごくシンプルで、実装頑張る

問題へのリンク

問題概要

整数 が与えられる。 ラウンドのインタラクティブゲームを行う。

• まずあなたは 頂点の無向単純グラフを 1 つ作成して出力する。
• 相手はそのグラフを受け取り、各ラウンドのはじめに、いずれか 1 つの頂点を思い浮かべる (どの頂点が思い浮かべられたかはあなたにはわからない)
• その頂点を当てるために最大 10 回まで、以下の質問を行える
  • 頂点 u を出力して、
    • u と v が一致したら Yes と答えが返ってきてそのラウンドを終了
    • u と v が隣接していたら Near と返って来てラウンド続行
    • u と v が隣接していなかったら No と返って来てラウンド続行

ラウンドすべてについて、10 回以内に Yes が返って来たら正解となる。

制約

• 

考えたこと

二分探索ができるグラフ構造にすればよい。すなわち、ゲームの各ラウンドが

• left = 0, right = N でラウンドスタート
• 毎ステップ、mid = (left + right) / 2 として、mid を出力
  • Yes なら終了
  • Near なら当てたい頂点が mid 以上であることが確定する (ようにグラフを作っておく)
  • No なら当てたい頂点が mid 未満であることが確定する (ようにグラフを作っておく)

という感じになる。グラフを作るのが大変だったが、再帰関数を用いることで上手く作ることができた。

#include <iostream>
#include <vector>
#include <string>
using namespace std;

void rec(vector<vector<int> > &G, int left, int right) {
    if (right - left <= 1) return;
    int mid = (left + right) / 2;
    for (int i = mid + 1; i < right; ++i) G[mid].push_back(i);
    rec(G, left, mid);
    rec(G, mid, right);
}

vector<vector<int> > make_graph(int N) {
    vector<vector<int> > G(N);
    rec(G, 0, N);
    return G;
}

int main() {
    int N, K; cin >> N >> K;
    auto G = make_graph(N);
    int M = 0;
    for (int i = 0; i < N; ++i) M += G[i].size();
    cout << M << endl;
    for (int i = 0; i < N; ++i) for (auto e : G[i]) cout << i+1 << " " << e+1 << endl;
    
    for (int _ = 0; _ < K; ++_) {
        int left = 0, right = N;
        string res;
        while (true) {
            int mid = (left + right) / 2;
            cout << mid + 1 << endl;
            cin >> res;
            if (res == "Yes") break;
            else if (res == "Near") left = mid;
            else right = mid;
        }
    }
}