アルゴリズムパズル 8-28 僕の解答・感想

1. 概要

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

2. 各問題の解答・感想

2.1. 8 ジグソーパズルの組み立て

1ピースの場合，2ピースの場合，3ピースの場合……と考えていけばあぁそういうことねみたいな感じになるので解けた．

2.2. 9 暗算

ガウスっぽい求め方もやったけれど，先に思いついたのは行列を分割する方法．

A = [ [1 2 3 ... 10] [1 2 3 ... 10] ... [1 2 3 ... 10] ]

B = [ [0 0 0 ...  0] [1 1 1 ... 1] ... [9 9 9 ... 9] ]

という行列を考えると問題の行列はA+BになるのでAの合計とBの合計を求めた．

こういう問題は僕は好きで，昔小学生のころの実験的な授業で，「九九の百ます計算の表の中から，性質をたくさん見つけましょう」というのがあって，あの授業は良かったなぁと今でも思い出す．

2.3. 10 8枚の硬貨に含まれる1枚の偽造硬貨

引っかかりました．8だから2^3やし3!!! と思って答えを見たら2と書いてあって，2手だよと書いてあるのをみてすぐに手法はわかったので先入観がネックだなぁと強く感じた問題．

2.4. 11 偽造硬貨の山

思いついたのですごく気分が良かった．やり方は本の解答と同じだった．

2.5. 12 注文付きのタイルの敷き詰め

本の解答同様に理詰めでやったところ，解答にある形とはちょっと違うけど条件を満たせない形に至った．

2.6. 13 通行止めの経路

大学受験でやった．

なにげにこういうテクニックって授業ではあまりやらなくて，どちらかといえば塾とかでしか教えてもらえないイメージ(友人から聞いた気がする)．

2.7. 14 チェス盤の再構成

同じ色が隣り合わせになってはダメなので，そうならないように切断する必要がある．

その場所を全部切れば答えに行き着く．

2.8. 15 トロミノによる敷き詰め

n=1について考えればチョロい．

2.9. 16 パンケーキの作り方

問題文読んで「よくわからない，普通に2枚ずつ焼いていって奇数だったら最後の1枚を2分かけて焼けばよいのでは？」みたいに思ったが当たり前に違っていて悲しい．

ヒントをちゃんと読んで考えるべきだった．

2.10. 17 キングの到達範囲

紙にかけばわかる．

2.11. 18 角から角への旅

小学生の頃「レイトン教授と悪魔の箱」をやっていて，ナイトツアーがめちゃくちゃ好きだったのだけれど問題見た瞬間「おっ！8x8のナイトツアーやな！久々だけれどできるかな～？」とやってたら問題を読み間違えていることに解答を見て気づいた．

2.12. 19 ページの番号付け

計算するだけ，高校数学感がすごい．

2.13. 20 山下りの最大和

本では上からだが僕は下から計算した(一番下に0があるものとして，下から順番にその数字の下のある数字で最も大きいものをその数字に加える，という処理を上までやると最大和が出て，その経路を見れば下り方もわかる)．

プロジェクトオイラーっぽい問題だなぁと思ってたらプロジェクトオイラーの問題だった．

なんとなく既視感があるしどこかで解いたのかもしれない．

2.14. 21 正方形の分割

答えはあってるし，構成法も解答と同様だったがn=5の場合にできない理由にあまり自信がなかった．

なお答えを見たらその理由が簡単に説明されていて少し考えたらなるほどとなった．

(n=5の場合に仮に分割できたとすると，分割されてできた小正方形の四隅は，大正方形の四隅にくっついていないといけないが，そうすると真ん中に「十」みたいな空間ができてしまい，その空有間を埋めるとn=4になるしどう頑張っても構成できない)

2.15. 22 チームの並べ方

結構苦戦した．問題文もすこし読み取りづらかった．でも面白い問題だった．

「推移律はないが大小比較ができる集合」って意識的に考えたことがなかったので普通におもしろいし，そういった集合でもソートみたいなことはできるのは面白いし，普通のソートのアルゴリズムが使えなさそうなのでどうやるんだろうとか妄想が捗る．

2.16. 23 ポーランド国旗の問題

問題文だけだとよくわからないので図と例が欲しいところではあった．

(正直一番左から～とか一番右から～というような情報を得ることはOKなのか？と若干不安になりながら答えを見た)

2.17. 24 チェス盤の塗り分け

問題文だけだとよくわからない問題だった．多分こういうことだろうと考えて答えを作った．

(a) 2なのは明らか(チェス盤でナイトが行ける場所は今いる場所とは色が異なる場所なので9

(b) とりあえず角においてみて，効きのある場所の色をすべて異なるようにしてゴニョゴニョしたら[[1 2 3 ... n] ... [1 2 3 ... n]]とすれば条件を満たすことがわかったのでn.

(c) ビショップ同様とりあえず置いて……とやって本の答えと同じになった．

2.18. 25 最高の時代

競プロかな？？？みたいになった．

計算のオーダーが指定されてないし頭も良くはないので以下のようにやればいけそうだなぁと思って答えを見た．

1. 没年で昇順にソートして，i番目の科学者の生年と没年を(a_1 b_1) ... (a_n b_n)とする．

2. 各iについて，j番目(j<i)の科学者は死亡しているので，i番目～n番目の科学者でb_i-1年に生まれている科学者の集合をA_iとする(A_i = {a_k | a_k < b_i, k ∈ {i...n}})

3. A_iの要素の数をn_i，A_iの要素で最も大きい数字をc_iとする

4. iをn_iが最大となるiとすると，c_i年～b_i-1年が最高の時代

という方針でO(n^2)やなと思って見たらO(n log n)の方法が紹介されていてしょぼりーぬであった．

2.19. 26 何番目か求めよ

高校数学だった．

2.20. 27 世界周遊ゲーム

適当にやったら見つけられた．解はたくさんありそうではある．

2.21. 28. 一筆書き

ちょろい．

小学生の頃一筆書きをしよう！みたいな算数の授業があったのだけれどそれが全然できなくて軽く泣いた思い出がある．その時書けなかった図形は今でも覚えている．

まぁそういう経験があったので奇数のnodeがあったらそこから出発し，奇数のnodeで終わる必要があるのも熟知している．

3. 感想

今回得られた反省としては，

1: 問題文をよく読むこと

問題文をよく読んで，よくわからなかったらヒントを読むこと．

2: 先入観にとらわれるな

簡単すぎる場合はもう少し考えて本当にその解であってるか考えたほうが良い．

また最適だろうと思ってももう少し考えて改良できないか考えたほうが良い．

といったところだろうか．後加えるなら

3: オライリー本がプログラム書くための本だとは限らない

ですね．正直読むスタンスを間違えていた．

プログラムが書ける人向けのパズル集なので，数独の問題をとくのと同じように紙とペンで解いてるのが適切だった．とても楽しい．