『パズルで鍛えるアルゴリズム力』の著者・大槻兼資さんより、挑戦状（クイズ）が届きました。頭の中でギリギリ解けるほどの難易度です。難なく解けた方は、コーディングスキルを用いてアドバンスト問題へ。いざ、挑戦！
本記事の感想をお送りいただいた方に抽選で書籍をプレゼント。詳細は記事のさいごに。
アルゴリズム的思考力を測る問題です。この問題の背景には、現実世界のさまざまな場面に応用できる技術が隠れています。ぜひ解いてみてください！
問題： ピラミッド上をギザギザに進む、コスト最小ルートは？
上の図のように、「丸」がピラミッドの形状にならんでいて、「丸」の中には数値がかかれています。下部には点が7個ならんでいて、それぞれ0,1,2,3,4,5,6と番号づけられています。左端の0番目の点がスタート（start）を表し、右端の7番目の点がゴール（goal）を表します。startからgoalまでは、下の図のように、点を経由してギザギザに移動します。
「丸」の中の数値は、点の移動に要するコストを表します。たとえば、0 番目の点 (start) から 3 番目の点への移動に要するコストは「8」です。
startからgoalへの移動方法の一例と、そのコストを下の図に示します。
- 0番目の点(start)から3番目の点へ移動するためのコストは、8です
- 3番目の点から4番目の点へ移動するためのコストは、950です
- 4番目の点から6番目の点(goal)へ移動するためのコストは、3です
よって、図のstartからgoalへの移動に要するコストは
8+950+3=961です。
startからgoalへ移動する経路のうち、コストが最も小さいものを求めてください。
アドバンスト問題
この問題が難なく解けたという方は、ピラミッドが1000段になっても、コンピュータを活用して解ける方法を考えてみてください。
問題の応用例
この「ピラミッド」問題は単なるパズルではなく、現実世界のさまざまな問題と結びついています。この問題の応用例を2つ挙げます。
大学入学共通テスト2022年度本試験「情報関係基礎」の問題
大学入学共通テスト2022年度本試験「情報関係基礎」では、次の文字列を作るために連結する最も少ない回文の数を求める問題が出題されました。
ガタイイイタイガーガイタ
正解は4個です。「ガ/タイイイタ/イガーガイ/タ」または「ガ/タ/イイイ/タイガーガイタ」のようにして、4個の回文を連結して作れます。
この回文の問題は、先ほどのピラミッドの問題として捉えることもできます。下の図のように、文章の両端と、文字と文字の間を、ピラミッドの点に対応させます。そして、点から点への移動を、その2点間にある文字を繋げてできる文字列に対応させます。そして、次のように設定します。
- 回文ではない文字列に対応するピラミッドの「丸」には「×」をかきます
- 回文に対応する移動のコストを1とします
このピラミッドで、「x」に対応する移動を禁止して、コストが最小の経路を求めると、最小個数の回文を連結してもとの文字列を作る方法が得られます。上の図の経路は「ガ/タイイイタ/イガーガイ/タ」という連結方法を表しています。
日本語のわかち書き
日本語の「わかち書き」とは、日本語の文章を語の区切りに空白を挟んで記述することです。たとえば、
この先生きのこる
という文章をわかち書きすると、次のようになります。
この 先 生きのこる
わかち書きにおいても、下の図のように「ピラミッド」を活用できます。先ほどの応用例(1)と同様に、文章の両端と、文字と文字の間を、ピラミッドの点に対応させます。
このピラミッドにおいて、妥当性の高い文字列に対応するピラミッドの「丸」には低いコストを表す数値を入れて、先ほどと同様にコストが最小の経路を求めると、妥当性の高いわかち書きの結果が得られます。
改めて、「ピラミッドパズル」の答えはわかりましたか？ 解答・解説は、こちらから。
書籍をプレゼント！
本記事の感想をお送りいただいた方の中から抽選で、ITスキルを磨ける書籍をプレゼント。ご応募お待ちしています！
1988 年生まれ。2014 年東京大学大学院情報理工学系研究科修士課程修了。修士（情報理工学）。現在、株式会社 NTT データ数理システム顧問、モノグサ株式会社コンテンツアーキテクト。数学や情報科学の諸分野の教材開発や啓蒙活動に従事。「けんちょん」の愛称で親しまれている。著書に『問題解決力を鍛える！アルゴリズムとデータ構造』（講談社）がある。数理最適化や機械学習を活用した数理コンサルティング業務の経験も多数。趣味は競技プログラミング、虫食算作り、国内旅行など。
※本記事に記載されている会社名、製品名はそれぞれ各社の商標および登録商標です。
