アルゴリズムパズル－プログラマのための数学パズル入門

2019年2月7日

オライリー・ジャパン

著者：Anany Levitin、Maria Levitin
訳者：黒川洋、松崎公紀

質問形式の序文
謝辞
パズル一覧
　チュートリアルのパズル
　本編のパズル
　墓碑銘パズル
目次

第1章チュートリアル
一般的なアルゴリズム設計戦略
　魔方陣(Magic Square)
　nクイーン問題(The n-Queens Problem)
　有名人の問題(Celebrity Problem)
　数当てゲーム(Number Guessing)(別名20の扉(Twenty Questions))
　トロミノ・パズル(Tromino Puzzle)
　アナグラム発見(Anagram Detection)
　封筒に入った現金(Cash Envelopes)
　2人の嫉妬深い夫(Two Jealous Husbands)
　グァリーニのパズル(Guarini’s Puzzle)
　最適なパイの切り分け(Optimal Pie Cutting)
　互いに攻撃しないキング(Non-Attacking Kings)
　真夜中の橋渡り(Bridge Crossing at Night)
　レモネード売り場の設置場所(Lemonade Stand Placement)
　正への変化(Positive Changes)
　最短経路の数え上げ(Shortest Path Counting)
分析テクニック
　チェスの発明(Chess Invention)
　正方形の増大(Square Build-Up)
　ハノイの塔(Tower of Hanoi)
　不完全なチェス盤のドミノ敷き詰め(Domino Tiling of Deficient Chessboards)
　ケーニヒスベルクの橋の問題(The Königsberg Bridges Problem)
　板チョコレートの分割(Breaking a Chocolate Bar)
　トウモロコシ畑の鶏(Chickens in the Corn)

第2章パズル
初級パズル
　1. 狼と山羊とキャベツ(A Wolf, a Goat, and a Cabbage)
　2. 手袋選び(Glove Selection)
　3. 長方形の分割(Rectangle Dissection)
　4. 兵士の輸送(Ferrying Soldiers)
　5. 行と列の入れ替え(Row and Column Exchanges)
　6. 指数え(Predicting a Finger Count)
　7. 真夜中の橋渡り(Bridge Crossing at Night)
　8. ジグソーパズルの組み立て(Jigsaw Puzzle Assembly)
　9. 暗算(Mental Arithmetic)
　10. 8枚の硬貨に含まれる1枚の偽造硬貨(A Fake Among Eight Coins)
　11. 偽造硬貨の山(A Stack of Fake Coins)
　12. 注文付きのタイルの敷き詰め(Questionable Tiling)
　13. 通行止めの経路(Blocked Paths)
　14. チェス盤の再構成(Chessboard Reassembly)
　15. トロミノによる敷き詰め(Tromino Tilings)
　16. パンケーキの作り方(Making Pancakes)
　17. キングの到達範囲(A King’s Reach)
　18. 角から角への旅(A Corner-to-Corner Journey)
　19. ページの番号付け(Page Numbering)
　20. 山下りの最大和(Maximum Sum Descent)
　21. 正方形の分割(Square Dissection)
　22. チームの並べ方(Team Ordering)
　23. ポーランド国旗の問題(Polish National Flag Problem)
　24. チェス盤の塗り分け(Chessboard Colorings)
　25. 最高の時代(The Best Time to Be Alive)
　26. 何番目かを求めよ(Find the Rank)
　27. 世界周遊ゲーム(The Icosian Game)
　28. 一筆書き(Figure Tracing)
　29. 魔方陣再び(Magic Square Revisited)
　30. 棒の切断(Cutting a Stick)
　31. 3つの山のトリック(The Three Pile Trick)
　32. シングル・エリミネーション方式のトーナメント(Single-Elimination Tournament)
　33. 魔方陣と疑似魔方陣(Magic and Pseudo-Magic)
　34. 星の上の硬貨(Coins on a Star)
　35. 3つの水入れ(Three Jugs)
　36. 限られた多様性(Limited Diversity)
　37. 2n枚の硬貨の問題(2n-Counters Problem)
　38. テトロミノによる敷き詰め(Tetromino Tiling)
　39. 盤面上の一筆書き(Board Walks)
　40. 交互に並ぶ4つのナイト(Four Alternating Knights)
　41. 電灯の輪(The Circle of Lights)
　42. もう1つの狼と山羊とキャベツのパズル(The Other Wolf-Goat-Cabbage Puzzle)
　43. 数の配置(Number Placement)
　44. より軽いか？より重いか？(Lighter or Heavier?)
　45. ナイトの最短経路(A Knight’s Shortest Path)
　46. 3色配置(Tricolor Arrangement)
　47. 展示計画(Exhibition Planning)
　48. マックナゲット数(McNugget Numbers)
　49. 宣教師と人食い人種(Missionaries and Cannibals)
　50. 最後の球(Last Ball)
中級パズル
　51. 存在しない数字(Missing Number)
　52. 三角形の数え上げ(Counting Triangles)
　53. バネ秤を使った偽造硬貨の検出(Fake-Coin Detection with a Spring Scale)
　54. 長方形の切断(Cutting a Rectangular Board)
　55. 走行距離計パズル(Odometer Puzzle)
　56. 新兵の整列(Lining Up Recruits)
　57. フィボナッチのウサギ問題(Fibonacci’s Rabbits Problem)
　58. ソートして、もう1回ソート(Sorting Once, Sorting Twice)
　59. 2色の帽子(Hats of Two Colors)
　60. 硬貨の三角形から正方形を作る(Squaring a Coin Triangle)
　61. 対角線上のチェッカー(Checkers on a Diagonal)
　62. 硬貨拾い(Picking Up Coins)
　63. プラスとマイナス(Pluses and Minuses)
　64. 八角形の作成(Creating Octagons)
　65. ビット列の推測(Code Guessing)
　66. 残る数字(Remaining Number)
　67. ならし平均(Averaging Down)
　68. 各桁の数字の和(Digit Sum)
　69. 扇の上のチップ(Chips on Sectors)
　70. ジャンプにより2枚組を作れI(Jumping into Pairs I)
　71. マスの印付けI(Marking Cells I)
　72. マスの印付けII(Marking Cells II)
　73. 農夫とニワトリ(Rooster Chase)
　74. 用地選定(Site Selection)
　75. ガソリンスタンドの調査(Gas Station Inspections)
　76. 効率良く動くルーク(Efficient Rook)
　77. パターンを探せ(Searching for a Pattern)
　78. 直線トロミノによる敷き詰め(Straight Tromino Tiling)
　79. ロッカーのドア(Locker Doors)
　80. プリンスの巡回(The Prince’s Tour)
　81. 有名人の問題再び(Celebrity Problem Revisited)
　82. 表向きにせよ(Heads Up)
　83. 制約付きハノイの塔(Restricted Tower of Hanoi)
　84. パンケーキのソート(Pancake Sorting)
　85. 噂の拡散I(Rumor Spreading I)
　86. 噂の拡散II(Rumor Spreading II)
　87. 伏せてあるコップ(Upside-Down Glasses)
　88. ヒキガエルとカエル(Toads and Frogs)
　89. 駒の交換(Counter Exchange)
　90. 座席の再配置(Seating Rearrangements)
　91. 水平および垂直なドミノ(Horizontal and Vertical Dominoes)
　92. 台形による敷き詰め(Trapezoid Tiling)
　93. 戦艦への命中(Hitting a Battleship)
　94. ソート済み表における探索(Searching a Sorted Table)
　95. 最大と最小の重さ(Max-Min Weights)
　96. 階段形領域の敷き詰め(Tiling a Staircase Region)
　97. 上部交換ゲーム(The Game of Topswops)
　98. 回文数え上げ(Palindrome Counting)
　99. ソートされた列の反転(Reversal of Sort)
　100. ナイトの到達範囲(A Knight’s Reach)
　101. 床のペンキ塗り(Room Painting)
　102. 猿とココナツ(The Monkey and the Coconuts)
　103. 向こう側への跳躍(Jumping to the Other Side)
　104. 山の分割(Pile Splitting)
　105. MU パズル(The MU Puzzle)
　106. 電球の点灯(Turning on a Light Bulb)
　107. キツネとウサギ(The Fox and the Hare)
　108. 最長経路(The Longest Route)
　109. ダブルnドミノ(Double-n Dominoes)
　110. カメレオン(The Chameleons)
上級パズル
　111. 硬貨の三角形の倒立(Inverting a Coin Triangle)
　112. ドミノの敷き詰め再び(Domino Tiling Revisited)
　113. 硬貨の除去(Coin Removal)
　114. 格子点の通過(Crossing Dots)
　115. バシェのおもり(Bachet’s Weights)
　116. 不戦勝の数え上げ(Bye Counting)
　117. 1次元ペグソリティア(One-Dimensional Solitaire)
　118. 6つのナイト(Six Knights)
　119. 着色トロミノによる敷き詰め(Colored Tromino Tiling)
　120. 硬貨の再分配機械(Penny Distribution Machine)
　121. 超強力卵の試験(Super-Egg Testing)
　122. 議会和平工作(Parliament Pacification)
　123. オランダ国旗の問題(Dutch National Flag Problem)
　124. 鎖の切断(Chain Cutting)
　125. 7回で5つの物体をソートする(Sorting 5 in 7)
　126. ケーキの公平な分割(Dividing a Cake Fairly)
　127. ナイトの巡回(The Knight’s Tour)
　128. セキュリティスイッチ(Security Switches)
　129. 家扶のパズル(Reve’s Puzzle)
　130. 毒入りのワイン(Poisoned Wine)
　131. テイトによる硬貨パズル(Tait’s Counter Puzzle)
　132. ペグソリティアの軍隊(The Solitaire Army)
　133. ライフゲーム(The Game of Life)
　134. 点の塗り分け(Point Coloring)
　135. 異なる組合せ(Different Pairings)
　136. スパイの捕獲(Catching a Spy)
　137. ジャンプにより2枚組を作れII(Jumping into Pairs II)
　138. キャンディの共有(Candy Sharing)
　139. アーサー王の円卓(King Arthur’s Round Table)
　140. nクイーン問題再び(The n-Queens Problem Revisited)
　141. ヨセフス問題(The Josephus Problem)
　142. 12枚の硬貨(Twelve Coins)
　143. 感染したチェス盤(Infected Chessboard)
　144. 正方形の破壊(Killing Squares)
　145. 15パズル(The Fifteen Puzzle)
　146. 動く獲物を撃て(Hitting a Moving Target)
　147. 数の書かれた帽子(Hats with Numbers)
　148. 自由への1硬貨(One Coin for Freedom)
　149. 広がる小石(Pebble Spreading)
　150. ブルガリアン・ソリティア(Bulgarian Solitaire)