N 人の人間のうち何人かが正直者で残りは嘘つきである。 次の 2 種類の質問を繰り返して正直者をすべて特定する問題である。
小課題 4 つあり、そのうち最も難しい小課題 4 では N ≦ 100 000 であり、質問の回数も 100 500 回までに制限されている。
この小課題では N ≦ 10 であり、質問の回数は無制限であるから、N 人それぞれが正直者か嘘つきかを全探索しても十分に間に合う。
まず、質問は全部で N + N^2 種類しかないので質問をすべて行う。次に 2^N 通りのすべての可能性それぞれについて、質問の結果と矛盾がないかどうかを調べる。矛盾のない組み合わせが 2 つ以上あれば特定不可能、 1 つしかなければそれを答えれば良い。
この解法は O(N^2 2^N) 時間で動き、 N + N^2 回の質問を行う。これで 16 点が得られる。
小課題 1 では可能性を 2^N 通りすべて試したが、実際は 2^N 通りも試す必要はない。なぜなら、人 0 に対して質問 1 を N 回行った結果があれば、人 0 が正直者か嘘つきかがわかると全員が正直者であるかがわかるからである。すなわち、人 0 が正直者かどうかの 2 通り試すだけでよい。
これに気づけば後は小課題 1 と同じように、N + N^2 回の質問を行い、人 0 が正直者と仮定した場合と嘘つきと仮定した場合について、質問の結果と矛盾がないかどうかを調べればよい。
この解法は O(N^2) 時間で動き、N + N^2 回の質問を行う。これで 45 点が得られる。
この小課題では N ≦ 100 000 となり、質問の回数が 200 500 回までに制限されている。
この小課題を解くためには、小課題 2 で行った「質問の結果と矛盾がないかを調べる」部分の最適化を行う。質問 1 において、人 i と人 j が正直者かどうかについて 4 通りの可能性を考えると、それぞれの場合で質問の返答は次のようになることがわかる。
これはつまり、質問 1 の返答は i と j が正直者かどうかが両方反転しても変わらないことを示している。小課題 2 で考慮した 2 通りの可能性は、片方はもう一方をすべて反転させたものであったことに注意すると、どちらの場合でも質問 1 で予期される返答は変わらない。すなわち、「矛盾があるか調べる」際に質問 1 の結果については考慮する必要がない。よって 2 通りの可能性について、質問 2 の結果だけに矛盾があるかを調べるだけで十分である。
この解法は O(N) 時間で動き、 2N 回の質問(人 0 に対して質問 1 を N 回、全員に対して質問 2 を 1 回ずつ)を行う。これで 62 点が得られる。
この小課題では小課題 3 に比べて質問回数の制限が 100 500 回となっている。この小課題を解くためにはこれまでとは異なった発想が必要である。
まず、全員の質問 2 を行い、人 i からは返答 A[i] を得たとしよう。このとき A[i] = A[j] ならば人 i と人 j はともに正直かともに嘘つきである。さらに考えると、質問 2 に対して m と答えた人の人数が m でなければ、m と答えた人はすべて嘘つきであることがわかる。これによって N 人の人間をいくつかのグループに分けることができる。
ある m に対し、質問 2 に m と答えた人の人数が m であった場合、その m 人はすべて正直者かすべて嘘つきのどちらかである。この m 人をひとつのグループとして考える。するとグループは全部で O(√N) 個にしかならないことに注意せよ。できるだけグループが小さくなるように 1 人のグループ、2 人のグループ、3 人のグループ、と順に作っていっても O(√N) 個のグループしか作ることができない。
さらにもうひとつのグループを考慮する必要がある。これは質問 2 の結果によって嘘つきであることが確定した(質問 2 への返答と、その返答をした人数が一致しなかった)人々からなるグループである。このグループはもはや結果が確定しているので不必要に思えるが、このグループを使わなければならない局面が存在する。
さて、各グループに属する人間たちはすべて正直かすべて嘘つきなので、N 人全員を考慮する必要はない。すなわち各グループから代表を 1 人とってきて O(√N) 人について考えれば良い。また、あるグループが正直グループであることが分かればその他のグループはすべて嘘つきになる。すなわち正直グループは高々 1 個しか存在しない。
まず先に確実に嘘つきであるような人間からなるグループが存在する場合を考えよう。この場合、確実に嘘つきであるような人間のうちひとりを f として、次のように質問をすることで正直者の特定が可能である。各グループの代表者 x に対して「f は正直者か？」と質問をすれば、この質問に No と答えた x のグループが正直であることが確定する。あるいは、この質問に No と答えたグループがいなければ、全員嘘つきであることがわかる。
次に嘘つきと確定している人間がいない場合を考える。正直グループは高々 1 個しか存在しないので、ほとんどが嘘つきである。嘘つきと嘘つきに対して質問 1 を行えば Yes が帰ってくるが、正直者と嘘つきに対して質問 1 を行えば No が帰ってくる。
あるグループの代表者 x をもってきて、その他のグループの代表者全員に対して質問 1 を行う。このとき No が帰ってくるようなグループの代表者 y がいれば、 x か y のどちらかが正直である。このような y がいなければ全員嘘つきである。さて、 x か y が正直であるので、このとき x と y どちらとも同じグループに属さない人間 z がいれば、z は必ず嘘つきである。よって、 z に対して質問を行うことで x と y どちらが正直かを判定できる。
問題は z が存在しない場合、すなわち最初からグループが 2 つしか無かった場合である。この場合、どのように質問をしても正直者を特定することは不可能であるから、グループが 2 つしか無かった場合は impossible を呼び出して終了せねばならない。
この解法は O(N) 時間で動き、N + O(√N) 回の質問を行う。これで 100 点が得られる。