ロープ飛び移りゲームと動的計画法｜情報処理学会・学会誌「情報処理」

久野 靖（電気通信大学） おなじみ「教科『情報』の入試問題って?」，今回は，大学入学共通テストの2023年本試験「情報関係基礎」第3問を取り上げます（この問題を含むさまざまな問題のアーカイブは文献1）にあります）． なぜこの問題？ということですが，「情報 I」の試験が始まっていない現時点では，「情報関係基礎」の問題が参考にできる問題の最有力候補です．そして，毎回，第3問は「プログラミング」を題材としているので，取り上げてみよう，ということです． そして，特にこの問題は，難しい解法をどれくらい知っているべきか，という悩ましい議論とかかわりがありますので，それについても後半で取り上げます．では，始めましょう． ロープ飛び移りゲームって? この問題では，「ロープ飛び移りゲーム」というものを規定し，その得点を高くするためのアルゴリズムとプログラムを考えていきます．最後には表題にある「動的計画法」（