KUPC2016 : D - 長い黒板 / Long Blackboard

ようやく全完。
http://kupc2016.contest.atcoder.jp/tasks/kupc2016_d

問題

2*Wのグリッドがあり、各セルは白黒に塗られている。

この問題はリアクティブであり、2*W以下の白黒に塗ったグリッドを与えると、元のグリッドがそのようなグリッドを含むかどうかを答えてくれる。
これを用いて元のグリッドを求めよ。

解法

1列ずつ求めていく。
空のグリッドから初めて、1列ずつ右の列を4通り連結させつつ、そのようなグリッドが存在する範囲で連結していく。
そのうち4通りどれも右に連結できなくなるので、そうするとグリッドの右端が確定する。
後は同様に左を1列ずつ確定させていく。

int N;

int ask(string a,string b) {
	cout<<a<<endl;
	cout<<b<<endl;
	string s;
	cin>>s;
	if(s=="end") exit(0);
	return s=="T";
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	cin>>N;
	
	string a="";
	string b="";
	while(1) {
		FOR(i,4) {
			a+=".#"[i/2];
			b+=".#"[i%2];
			if(ask(a,b)) break;
			a.pop_back();
			b.pop_back();
		}
		if(i==4) break;
	}
	while(1) {
		FOR(i,4) {
			a=".#"[i/2] + a;
			b=".#"[i%2] + b;
			if(ask(a,b)) break;
			a.erase(a.begin());
			b.erase(b.begin());
		}
	}
	
}

まとめ

まぁまぁすんなり回答できた。