http://projecteuler.net/index.php?section=problems&id=352
帰ってきたらすでに20人が正答。いや、もう7時間以上が経っているのでまだと言うべきか。問題を見たら、長い。問題を見たら買い物に出かけて考えようと思っていたのでいらつく。とりあえず読んでみたが意味がわからない。買い物に行って考える。
25頭の羊について感染しているかどうか特定したい。そのときの検査の平均回数を最小化したい。
何頭かの羊をまとめて検査することができる。その検査でネガティブなら全頭ネガティブ、ポジティブならさらに5つの検査が個々の羊に対して必要。
だいたいわかってきた。最後の方に最初の4頭が云々というのがよくわからなかったが、5頭のうち1頭以上が感染しているとわかっているなら4頭が検査でネガティブなら残りの1頭は検査するまでもなくポジティブってことか。と納得しかけて思った。どうして1頭以上感染しているとわかるんだ？最初のまとめたテストでポジティブなら1頭以上がポジティブとすると、そのテストを1頭ずつでやればいいから、5つの検査要らないじゃん。
まだ問題がちゃんとわかっていない。
最後のところ考慮せずにさらっと書いたら6.88になった。値だけ求めたのでどういう分配になっているかは知らない。
