13中学受験の問題をプログラミングを使って解いてみるC++アルゴリズム数学算数中学受験はじめにこんにちは。Mikatus株式会社でフロントエンドエンジニアをやっている青山です。今回はアドベントカレンダーということで、せっかくなので普段の業プロ1とはちょっと異なるものを題材に記事を書いてみようと思います。皆さんは中学受験の問題を解いたことがありますか?私は今まで解いたことがありませんでしたが、たまたまなんとなく中学受験の問題を眺めていたら2プログラミングの題材としてとても良さそうな問題があったのでプログラミングを使って解いてみたいと思います。簡単な言語機能のみを使うようにしたいと思うのと、コードよりも考え方に重点を置いて進めて行きたいと思うので専門的なプログラミングの知識がなくてもある程度は読めると思います。プログラマーではない読者の方は、記事の内容はすっ飛ばして頭の体操としてふつうに問題を解いてみても面白いかもしれません。まで移動するとき、考えられる移動経路は何通りありますか。とある中学3の算数問題をベースに記事用に用意した問題です。図は自分で作成したものです。考えて考察していきます。して(それにあわせて格子も拡大して)考えてみてください。解法1まず、もっとも原始的かつ愚直な解法を考えて見ます。経路をひたすら全部書いてみる!」という方法はどうでしょうか?確かに根気さえあればなんとかなるかもしれませんが、ちょっと試してみれば「漏れなくダブりなく4」考えられる全パターンの経路を書き出すのはなかなかに難しいことがわかると思います。遠くなっただけで経路数が爆発して手で全列挙するのはほぼ無理になりますそこでより小さな問題を考えてみます。1)$の1通りしかありませんね。した場合はどうでしょうか。1)$の2通りだとわかります。経路を考えて見ましょう。二つのみとわかります。経路は1通りであることを確認しました。経路も1通りであるとわかります。経路は2通りであることを確認しています。1通りを足した3通りであるとわかります。上か右にしか移動できないことから、ある点への経路数は、左隣の点への経路数と一個下の点への経路数の和であると一般化できます。経路数の和であるとわかります。順番に図などに各点の経路数をメモしつつ計算していけば答えを導出できそうですね!ただ、図に数値を順番に書き込んでいって答えを求めても良いですが、ちょっと面倒です。ここでやっとプログラミングを使ってみましょう!ところで、アルゴリズムをそれなりに勉強している・したことがある人であれば問題を見た瞬間に「これ完全にDP(動的計画法)の問題やんけ!」となったかもしれません。Programming)と呼びます。今回くらいの問題だとあまりありがたみがわからないかもしれませんが、部分問題の計算結果を使い回すことで時間計算量を効率化できるところが動的計画法の一つの大きな利点です。ここまででプログラミングのコードは一切書いてないですが、この解法の考え方は完全に動的計画法ですね。・・・こんな問題を日常的に解いている小学生、強すぎませんか?考察力、考える力がめっちゃつきそうだと思いました。ちなみに記事のタイトルを「中学受験の問題で動的計画法に入門する」とかにしようか悩みましたがそうするとネタバレになってしまうのでやめましたそれでは実際にここまでの考察をコードに落とし込んで行きましょう。今回はC++を使って書いて見たいと思います。(なるべく基本的な言語機能のみで簡単に書いて行きます)コードを書く前にもう一度ポイントをおさらいするとある大きな問題を、同じ形をしたより小さな問題に帰着させ、その小さな問題の解を使って大きな問題を解く分割したより小さな部分問題の解を記録し、再利用することで時間計算量を効率化する以上が動的計画法のポイントでした。部分問題の計算結果を記録していくことについてですが、これを実現するには俗にいうDPテーブルというもの用意します。二つあるため、DPテーブルを二次元配列を使って実現します。次に小さな問題の解を使って大きな問題を解くについてですが、まずはコードを書く前に式を考えて見たいと思います。ことがわかっています。この関係性を使って式を立ててみましょう。y)$という式が立てられそうです。考えるとこの式は完璧ではありません。いう点は存在しないのでおかしなことになってしまいます。ときもおかしくなってしまいます。いうわけでしっかりと場合分けを考慮してもう一度ちゃんと式を立ててみましょう。\end{cases}\end{eqnarray}こんな感じでしょうか。してしまっても良いことがわかります。\end{cases}\end{eqnarray}あとはこの式で表現される関係をそのままコード化すれば部分問題を使ってより大きな問題を解くといったことが実現できそうです。ちなみに、このような式を漸化式と呼んだりします。ところでDPを実現する方法として代表的なものに、配るDP5、貰うDP5、メモ化再帰(どれも本質的にはほとんど同じです)の3つがあります。配るDPは小さい方から大きい方へ、現在みている部分問題の結果を部分問題の関係性を利用してより大きいほうへ配りながら解いていくやり方です。今回の場合だと、漸化式をそのまま再帰関数で書いてメモ機能を入れつつ実装すればメモ化再帰、ボトムアップなループで下からやっていくような実装をすれば貰うDPになります。実は今回の問題では配るDPのほうが簡単にコードが書けるのでそっちでやってみたいと思います。配るDPのほうが簡単にコードが書けるのかはいったん置いておいて、実現方法を見ていきましょう。ある点の経路数をより遠い点に配っていきます。y)$に配ってやれば実現できます。実現方法がわかったところで、なぜ今回の問題で配るDPのほうがコードを書くのが簡単なのか考えてみましょう。0以下の場合を考慮する必要があります(再帰の場合はベースケースとして、貰うDPの場合は配列外参照やセグフォを防ぐため)。してもそれより小さい方を考慮する必要がないことがわかります。(ただし、どんどん大きい方へ配ろうとすることを考えるとテーブルをちょっと大きく持っておく必要がありますが、逆に言うとそれだけで済みます)では実際にコードを書いて見ましょう。0;}最初のdpテーブルの初期化時に余分にサイズを大きくとっていますが、それだけです。if文すら登場しません。いう結果が出力されます。解法2ではもう一つの解法を見て行きましょう。(こちらの解法は義務教育の範囲をちょっと飛び出して、高校数学の知識を使います。)数学が得意な人はちょっと考えると図からパスカルの三角形6が見えると思います。すると問題を見た瞬間に「パスカルの三角形やんけ!」となったかもしれません。そもそもパスカルの三角形って何?な方向けにWikipediaへのリンクを貼っておきます。各点から矢印を書いてみるとよりわかりやすいかもしれません。首が柔らかく135度回転させられる人は、首の付け根を中心として頭を左下側に135度倒して図形をみてみるとよいかもしれません。首が折れてしまうかもしれないので、図のほうを回転してみるとこんな感じです。?パスカルの三角形が見えたのではないでしょうか?パスカルの三角形が見えなかった方は解法1の考え方を使って、図の各点に経路数を書き込んでみるとわかると思います。・としてコンビネーションを使って各点の経路数を表現することができます。