読者です 読者をやめる 読者になる 読者になる

ARC070 F「HonestOrUnkind」別解

HonestOrUnkind解いた。
面白かった、と思ってたけど想定解と違ったのでメモ。
想定解の方がシンプルで頭良い。

正直者を1人特定するところが違った。

まず人の組をN/2組作る。Nが奇数なら1人余る。
各組(x,y)について? x yを質問する。
'N'なら正嘘、嘘正、嘘嘘のどれか。(消費される人数は正≦嘘)
'Y'なら正正、嘘正、嘘嘘のどれか。(yを嘘にするためには嘘を2人消費する)
'Y'だった組のyを全部取り出した集合をTとする。
元々のN人では正>嘘である点に注意すると、

  • Nが偶数:Tの中でも正>嘘になる
  • Nが奇数:Tの中では正≧嘘になる

奇数のときも正>嘘にできれば、再帰的にやることにより高々2(N/2)=N回の質問で正直者を1人見つけられる。
奇数のときは「Tのサイズが偶数なら余っていた1人をTに追加する」とすることにより、正>嘘にできる。
いちおう証明↓
Tのサイズが奇数の場合:偶奇の性質上、正=嘘は成り立たないので正>嘘
余りが正だった場合:元が正≧嘘なんだから正を足せば正>嘘になる
余りが嘘だった場合:Nが偶数だった場合を思い出すと、正>嘘になっていてつまり正が嘘より2人以上多いので、嘘を1人足しても正>嘘
どのケースでも正>嘘になっていることが分かる。