Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

IJPC # 3 C - Honest Fox and Dishonest Man

問題文 : しょうじききつね と うそつきにんげん

解法 :
はじめに"正直者の人数" をもととしたグループを作ると, それが正しい可能性のあるグループは高々O(√N) 個しかできない.
明らかに嘘を付いている人物がいれば, その人を使って正直者かどうかの判定を行える.
そのような人物がいなければ, 次のように場合分けを行う.
・全員が"正直者の人数"が N 人といっていれば, もうどうしようもないのでimpossible()を呼び出す.
・グループが2 つ以上あって, その中の1 人の人にそれぞれのグループの人1 人について質問をして "全員が正直者" と帰ってきた場合, 全員嘘つきなのでそう答える.
・上記2 つでなくグループが2 つしかない場合, もうどうしようもないのでimpossible() を返す.
・そうじゃなければ, 嘘つきである可能性があるグループが2 つ浮上するので, 第3 のグループを用いてどちらが正しいかを突き止める.

質問は高々N + O(√N) しか行われないため, これで満点が得られる.

ソース :

#include "grader.h"
#include "honest.h"
#include <vector>

using namespace std;

vector<int> gr[100001];

void identify(int N)
{
	int ret[100001];
	int belong[100001];
	
	for (int i = 0; i < N; i++){
		int x = question(2, i, 0xdeadbeef);
		gr[x].push_back(i);
		belong[i] = x;
	}
	
	int lier = -1;
	vector<pair<int, int> > cand;
	
	for (int i = 0; i <= N; i++){
		if (gr[i].size() && gr[i].size() != i) lier = gr[i][0];
		else if (gr[i].size()){
			cand.push_back(make_pair(i, gr[i][0]));
		}
	}
	
	if (~lier){
		int honest = 0x7fffffff;
		for (int i = 0; i < cand.size(); i++){
			if (question(1, lier, cand[i].second) == 0){
				honest = cand[i].first;
				break;
			}
		}
		for (int i = 0; i < N; i++){
			answer(i, belong[i] == honest);
		}
	}
	else {
		if (cand.size() == 1){
			impossible();
			return;
		}
		int oCount = 0;
		int suggest[100001];
		int prob[2];
		
		for (int i = 0; i < cand.size(); i++){
			bool f = question(1, cand[0].second, cand[i].second);
			oCount += f;
			suggest[cand[i].first] = f;
			if (!f){
				prob[0] = cand[0].first, prob[1] = cand[i].first;
			}
		}
		if (oCount == cand.size()){
			for (int i = 0; i < N; i++) answer(i, 0);
			return;
		}
		
		if (cand.size() == 2){
			impossible();
			return;
		}
		
		int honest = 0x7fffffff;
		for (int i = 0; i < cand.size(); i++){
			if (cand[i].first != prob[0] && cand[i].first != prob[1]){
				if (question(1, cand[i].second, gr[prob[0]][0]) == 0) honest = prob[0];
				else honest = prob[1];
				break;
			}
		}
		
		for (int i = 0; i < N; i++) answer(i, belong[i] == honest);
	}
	return;
}