インタラクティブな問題がたまに出題される. 特別扱いする必要があるか,ということだが, 何も考えずに書いてしまうとデバッグが難しい,ということがあるので, やはり形式を整えておきたい感じである.

先日の Codeforces R.812 (Div 2) Tournament Countdown で,TLE というめにあった. virtual base class を持つオブジェクトのメソッド呼び出しがあったりしたのが 良くなかったのではないかと思う.

ということで,軽く実行できるようにしたい.

ポイントとしては,ask() 関数と answer() 関数を用意する. これらで,問と答の入出力部分をラップする. 実装するときには,ask_i() と answer_i() という名前で書く. 通常はこちらを ask(), answer() として使い, 自動テストのと期には ask_judge(), answer_judge() に切り替える.

典型的な実装はこんな感じ.二分探索数当てゲームを想定.

bool judge = false;

ll ask(ll x) { return judge ? ask_judge(x) : ask_i(x); }
ll answer(ll x) { if (judge) answer_judge(x); else answer_i(x); }

ll ask_i(ll x) {
  cout << "? " << x << endl;
  string s; cin >> s;
  if (s == "SMALL") return -1;
  else if (s == "LARGE") return 1;
  else if (s == "EQUAL") return 0;
  else assert(0);
}

void answer_i(ll x) {
  cout << "! " << x << endl;
}
#endif

solve() 関数では,初期入力を受け取ったのち,ask() と answer() を 使って解を組み立てる.

ll L, R;
void solve() {
  cin >> L >> R;
  if (judge) read_judge();

  ll lo = L, hi = R;
  while (true) {
    ll mid = (lo + hi) / 2;
    ll resp = ask(mid);
    if (resp == 0) { answer(mid); return; }
    else if (resp < 0) { lo = mid; }
    else { hi = mid; }
  }
}

自動テストに関して.本来の入力の後に問題情報を, 渡すようにするので,それを読む関数 read_judge() を,適切な位置に 置いておく(上の solve() 関数参照).

void read_judge() {
  cin >> expected;
}

自動テストでは,ask() 関数と answer() 関数を差し替えて, 自動テストに適した形にする.つまり,ask() は,追加情報を参照して, 適切な答を作成して返す.また,answer() は,不正解の場合には 異常終了するようにする.

ll ask_judge(ll x) {
  if (x < expected) return -1;
  else if (x == expected) return 0;
  else return 1;  
}

void answer_judge(ll x) {
  if (x == expected) return;
  else               exit(1);
}

自動テストのときには,./cans の引数に judge を与えるようにする. int main(int argc, char *argv[]) { // … if (stcmp(argv[1], “judge”) == 0) { judge = true; }

solve(); // multiple-question のときには,ここでループ. }

cmpNaive を使用するときには,コマンドとして cmpNaive -i -e -p './cans judge' のように使う.ソースコードは これ以上書き直す必要は無い (naive関数は不要).

たとえば Codeforces R.#449 Ithea Plays with Chtholly のように,先に相手側から質問が来て,こちらはそれに答える,というタイプの ものもある.最後のこちらの答を入力したら, 直ちにプログラムを終了せよ,とか指示される. この場合は,

  • 最初の質問までを初期入力と考える.
  • こちらの n 番目の答を ask() で渡して,その戻り値として,相手の n + 1 番目の 質問を得る.
  • こちらの最後の答は answer() で渡す.

というふうにすれば良いであろう.