KUPC 2011 C: しりとり

その他のコンテスト

問題概要

しりとりで、相手がミスしたら指摘するリアクティブな問題。使える文字集合は小文字のアルファベット。こちらは先手で1~10文字の単語が使える。相手は1~2語の単語しか使えない。50ターン(先手 -> 後手で1ターン)以内に相手のミスを指摘しなければならない。

考えたこと

  • リアクティブ来た！
  • でも順位表見るに簡単っぽい。
  • 'a'で責めれば良さげ。
  • 初手'a'にすると27ターン後には詰むだろう。
  • とにかく愚直に書く。
  • コンパイルが通ってから、2分くらいかけて検証して送信。一発で通って嬉しい。

本番中で通ったコード

  • 二手目以降は"x??a"(xは相手のlast character)を返していたが、"xxa"とするのが一番楽だったように思う。今更だけど。
#include <cstdio>
#include <set>
#include <string>
using namespace std;

const int MAX_L = 12;

char buf[MAX_L+1];

int main(){

	set<string> used;

	puts("?a"); fflush(stdout);
	used.insert("a");

	for(;;){
		scanf("%[^\n]%*c", buf);
		string str = string(buf);

		if('a' != str[0] || !used.insert(str).second ){
			break;
		}

		char last_char = str[(int)str.length()-1];

		//(last, b, c, 'a')を出力する
		bool found = false;
		for(char b = 'a'; b <= 'z'; b++){
			for(char c = 'a'; c <= 'z'; c++)if(!found){
				str = string(1, last_char);
				str += b;
				str += c;
				str += 'a';
				if( used.insert(str).second ){
					found = true;
					printf("?%s\n", str.c_str());
					fflush(stdout);
				}
			}
		}

	}

	puts("!OUT");

	return 0;
}