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; }