アルゴリズムパズル 49-60 僕の解答・感想

1. 概要

『アルゴリズムパズル ―プログラマのための数学パズル入門』の29-48番目の問題の僕の解答・感想です．

2. 各問題の解答・感想

2.1. 49 宣教師と人食い人種

全幅探索だよなぁっておもって答え見て，状態空間グラフとか解答には書いてあるけど結局のところ禁止操作を除いた全幅探索では？と思ってる．

2.2. 50 最後の球

気づくのに時間がかかった．僕は(黒の球の数)x2+(白の球の数)がどちらの操作でも不変だということに気づいて回答したが，白の球の数のみに注目すれば良いことに答えを見てから気づいた．

2.3. 51 存在しない数字

まぁ100を法とした和が計算できれば行けるが……それはジルにできるのか？と半ば不安ながら答えを見た．できるらしい．
この手の問題は何言ってもヒントになってしまうので問題出題側に厳しいところがある．

2.4. 52 三角形の数え上げ

適当に数字を並べば法則性は見える，なんかややこしいだけな気がしたので証明は特にしなかった

2.5. 53 バネ秤を使った偽造硬貨の検出

にぶたん．\(W(n)=W(\lceil n/2 \rceil)+1\)の解が\(W(n)=\lceil \log_2 n \rceil \)になることはどうやって示されるんだろうか．
そのへんが気になりだしたら普通にアルゴリズム系の本を読んだ本がいい気もする．

2.6. 54 長方形の切断

No.30といたあとなら即答

2.7. 55 走行距離パズル

高校数学でみた気がする．

2.8. 56 新兵の整列

今の所暫定一番で問題文の意図が汲み取れなかった問題．
とりあえず昇順に並べれば良いのはわかるがヒントを見て何を言ってるんだ？となって答えを見て何を言ってるんだ？となった．
ここでいう差は二通りの読み方ができるよね？みたいなのは言葉の定義の話であってそこをどういう言うのは良い問題とは思えない．正直本質的でないところで悩むのは不毛すぎる．
答えを見たあとに問題文を見ると「なんで読み違えたんだろう」となってしまうので，レビューを頼まれたひとが指摘しないといけないのだと思う．
とりあえず僕の意見としては，この問題は「シュヴェイクは上司の命令を勘違いをしているが，どんな勘違いをしているだろうか」と一文入れたりするか，もしくは「～差の絶対値の平均が～の場合と，(ある兵士の身長)-(その兵士の前にいる兵士の身長)の平均が～の場合で解がことなる．どのように配置すればよいか」といういうふうに書き換えたほうが良いと思う．

2.9. 57 フィボナッチのウサギ問題

まぁ数列はすぐ出るでしょう．高校数学．

2.10. 58 ソートして、もう1回ソート

これは面白かった．トランプを実際に引っ張り出してきてあれこれやって「アレ？これひょっとして常に0なの？」と気づいたときは狐につままれたようだった．
証明は考えたがちゃんとまとまってないが納得できる状態まで持っていけた．

2.11. 59 2色の帽子

まぁよかった．少し考えたらわかると思う．
ただ「午後12:05から始めて午後12:55まで5分おきに囚人を整列させる」は12:05を含まないと思って「10回だからムリ！」と答えを見たら違ったので「合計11回整列させる」と書いてほしかった(中途半端な時間だから少し考えたらわかる気がするし若干ア.ス*ペ味がある)．

でも流石にこれは考えすぎかもしれないが，囚人の考え方しだいでうまくいかない場合があるのでは？と思った．というのも，解答では
・「自分の帽子の色がわからない，もしくは自分の帽子の色が白である」→「とどまる」
・「自分の帽子の色が黒である」→「前に出る」
という「黒だったときのみ前に出る」で行動をしていたが，
・「自分の帽子の色が白である」→「とどまる」
・「自分の帽子の色がわからない，もしくは自分の帽子の色が黒である」→「前に出る」
という「白だったときのみとどまる」で行動する可能性も否定出来ないなぁと思った．

2.12. 60 硬貨の三角形から正方形を作る

とりあえず「正方形」って何？となった．
外枠だけで良くて複数の正方形を作らせたいのか，中身が詰まってる1つの正方形を作らせたいのか，中身を詰めるとしたら詰め方はどんなものを許容するのか．
あと「何種類の」とは「向き・場所が異なる正方形」を区別するの話なのか，あるいは「大きさの異なる正方形」を区別する話なのかわからないなぁとなってた．
いちゃもんみたいに聞こえるかもしれないけれど変に深読みしてしまって混乱したので，とりあえず目標となる正方形の図を入れてほしかったのはある．
正直何言ってもヒントになるタイプの問題なので辛いところではあるので致し方なし．

3. 感想とか

問題文がよくわからなくて本質的じゃないところで悩むのが本当に不毛である．
訳者は悪くなくて(むしろ訳注を入れてくれたりして助かっている)，多分これは著者というかレビューしたひとがちゃんとレビューしてくれなかったのがいけないのではと思ってる．