しりとり (AOJ 2273)

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2273

問題

略

解法

解説参照。

#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <cassert>
#include <algorithm>
#include <string>
#include <set>
#include <iostream>
using namespace std;


set<string> used;

string gen(char start, char end) {
  string str;
  while (true) {
    str = "";
    str += start;
    for (int i = 0; i < 5; i++) {
      str += random() % 26 + 'a';
    }
    str += end;
    if (!used.count(str)) { break; }
  }
  return str;
}

string ask(const string out) {
  printf("?%s\n", out.c_str());
  fflush(stdout);

  string ret;
  cin >> ret;
  return ret;
}

void output(string str) {
  fprintf(stderr,"%s\n", str.c_str());    
}


int main() {
  srandom(time(NULL));
  char prev = 'a';
  for (int i = 0; i < 51; i++) {
    string send, receive;
    send = gen(prev, 'a');
    used.insert(send);
    receive = ask(send);
    if (receive[0] != *send.rbegin()) { break; }
    if (used.count(receive)) { break; }
    used.insert(receive);
    prev = *receive.rbegin();
  }
  puts("!OUT");
  fflush(stdout);
}