AtCoder ARC #070 : F - HonestOrUnkind

本番この方針は思い浮かばなかったな…。
http://arc070.contest.atcoder.jp/tasks/arc070_d

問題

N人の人がおり、うちA人は正直者で、B人は不親切である。
N人はそれぞれ誰が正直者か知っている。

N人中a番の人に「b番の人は正直者か？」と尋ねることを考える。
a番が正直者なら、正しい回答を返す。a番が不親切な場合、どんな回答を返すかわからない。

最大2N回の質問で、正直者を全員特定できるか。できるなら判定せよ。

解法

正直者が過半数いない場合、不親切な人が協力し合うと不親切な人を正直者に見せかける回答ができてしまうので、特定できない。

以下、正直者が過半数とする。
正直者を1名特定できれば、その人にN回質問することで全員正直者かどうかわかるので、1名特定することを考えよう。

x→yをx番の人がy番を正直者と答えたとする。
ここで正直者のチェインCを考える。すなわちC[m]→C[m-1]→C[m-2]→...→C[0]となる人の並びを考える。
この並びの長さが(B+1)以上の場合、間に1人以上正直者C[i]がいるので、C[i],C[i-1],...,C[0]は正直者となる。
よってC[0]は必ず正直者である。

人を順番にこのチェインの末尾に追加できるかどうかを判定していこう。
チェインが空ならその人を無条件で追加し、空でなければ末尾の人から正直者判定されるか質問を投げる。
質問の結果正直者と判定されればチェインの末尾に追加できる。

問題は正直者でないと判断された場合である。
この時、チェイン末尾の人と、今追加するか判定中の人の少なくとも1名は不親切である。
よって、両者を取り除いてしまおう。取り除く人は少なくとも不親切な人を1名含むので、正直者が過半数という状態は維持できる。
最終的にどこかで条件(長さ(B+1)以上)を満たすチェインができるので、それで正直者を特定できた。

なお、Editorialではチェインを逆向き(先頭側)に伸ばしているが、どちらでもACがとれる。

int N,A,B;
int ret[4020];

int ask(int a,int b) {
	string s;
	cout<<"? "<<a<<" "<<b<<endl;
	cin>>s;
	return s[0]=='Y';
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>A>>B;
	if(A<=B) {
		cout<<"Impossible"<<endl;
		return;
	}
	
	N=A+B;
	vector<int> path;
	y = B;
	FOR(i,N) {
		if(path.empty() || ask(path.back(),i)) {
			path.push_back(i);
		}
		else {
			path.pop_back();
			y--;
		}
		if(path.size()>y) break;
	}
	
	x = path.back();
	FOR(i,N) ret[i]=ask(x,i);
	cout<<"!";
	FOR(i,N) cout<<ret[i];
	cout<<endl;
	
}

まとめ

この解法は思い浮かばなかったな。
質問にNoと帰ってきたとき、「少なくとも1名は不親切」という情報が取得できる点に気付かなかった。