Help us understand the problem. What is going on with this article?

中学受験の問題をプログラミングを使って解いてみる

はじめに

こんにちは。
Mikatus株式会社でフロントエンドエンジニアをやっている青山です。

今回はアドベントカレンダーということで、せっかくなので普段の業プロ1とはちょっと異なるものを題材に記事を書いてみようと思います。

突然ですが皆さんは中学受験の問題を解いたことがありますか?

私は今まで解いたことがありませんでしたが、たまたまなんとなく中学受験の問題を眺めていたら2プログラミングの題材としてとても良さそうな問題があったのでプログラミングを使って解いてみたいと思います。

なるべく簡単な言語機能のみを使うようにしたいと思うのと、コードよりも考え方に重点を置いて進めて行きたいと思うので専門的なプログラミングの知識がなくてもある程度は読めると思います。

またプログラマーではない読者の方は、記事の内容はすっ飛ばして頭の体操としてふつうに問題を解いてみても面白いかもしれません。(中学受験なのでただ解くだけであれば義務教育レベルの知識で十分なハズです)

問題

図の格子状に引かれた線を道とし、右または上方向に道を進むことで点 $A$ から点 $B$ まで移動するとき、考えられる移動経路は何通りありますか。

Frame 1.png


とある中学3の算数問題をベースに記事用に用意した問題です。図は自分で作成したものです。(どこかから勝手に持ってきた画像ではありません)

下に考察・解法を書いていきたいと思いますが、先に進む前にまずは読者の方も問題を解いてみましょう!

考察

2パターンのアプローチで解いてみたいと思いますが、説明・考察する際の便宜上どちらの場合もまず格子状の線を座標平面に見立てて、黒い丸がついてる箇所を点、そして点$A$ を $(0, 0)$ 、点$B$ を $(3, 3)$ と考えて考察していきます。

点$B$ が $(3, 3)$ だと簡単すぎるかもなので、余裕のある人は点$B$ を $(6, 6)$ として(それにあわせて格子も拡大して)考えてみてください。

解法1

まず、もっとも原始的かつ愚直な解法を考えて見ます。

例えば「 $A$ から $B$ までの経路をひたすら全部書いてみる!」という方法はどうでしょうか?

確かに根気さえあればなんとかなるかもしれませんが、ちょっと試してみれば「漏れなくダブりなく4」考えられる全パターンの経路を書き出すのはなかなかに難しいことがわかると思います。

点$B$ が $(3, 3)$ くらいであればまだなんとかなるかもしれませんが、これが $(6, 6)$ とかちょっと遠くなっただけで経路数が爆発して手で全列挙するのはほぼ無理になります

そこでより小さな問題を考えてみます。

点$B$ を $(0, 1)$ としたときの経路は何通りでしょうか?

以下では矢印 $\rightarrow$ で点から点への移動を表現しています

  • $(0, 0) → (0, 1)$

の1通りしかありませんね。

点$B$ を $(1, 0)$ としたときも同じく1通りしかないことがわかります

では、点$B$ を $(1, 1)$ とした場合はどうでしょうか。

  • $(0, 0) → (1, 0) → (1, 1)$
  • $(0, 0) → (0, 1) → (1, 1)$

の2通りだとわかります。

次に $(1, 2)$ までの経路を考えて見ましょう。

上か右にしか移動できないということから $(1, 2)$ の一つ前の点としてあり得るのは $(1, 1)$ と $(0, 2)$ の二つのみとわかります。

$(0, 2)$ の一つ前の点としてあり得るのは $(0, 1)$ のみです。

先ほど $(0, 1)$ までの経路は1通りであることを確認しました。ということは $(0, 2)$ までの経路も1通りであるとわかります。

そしてすでに $(1, 1)$ までの経路は2通りであることを確認しています。

これらの事実から $(1, 2)$ までの経路は $(1, 1)$ までの2通りと $(0, 2)$ までの1通りを足した3通りであるとわかります。

ここまでの考察結果を一般化してみると・・・

上か右にしか移動できないことから、ある点への経路数は、左隣の点への経路数と一個下の点への経路数の和であると一般化できます。

よって点$B$ $(3, 3)$までの経路は $(3, 2)$ までの経路数と $(2, 3)$ までの経路数の和であるとわかります。

ここまで来れば、あとは $(0, 0)$ の経路数を1として $(3, 3)$ までを順番に図などに各点の経路数をメモしつつ計算していけば答えを導出できそうですね!

ただ、図に数値を順番に書き込んでいって答えを求めても良いですが、ちょっと面倒です。ここでやっとプログラミングを使ってみましょう!

ところで、アルゴリズムをそれなりに勉強している・したことがある人であれば問題を見た瞬間に「これ完全にDP(動的計画法)の問題やんけ!」となったかもしれません。

今回の考察でやったような、「ある大きな問題を、同じ形をしたより小さな部分問題に帰着させ、部分問題の計算結果を記録して使い回しながら解いていく」といった手法を動的計画法(Dynamic Programming)と呼びます。

今回くらいの問題だとあまりありがたみがわからないかもしれませんが、部分問題の計算結果を使い回すことで時間計算量を効率化できるところが動的計画法の一つの大きな利点です。

ここまででプログラミングのコードは一切書いてないですが、この解法の考え方は完全に動的計画法ですね。

・・・こんな問題を日常的に解いている小学生、強すぎませんか?考察力、考える力がめっちゃつきそうだと思いました。

ちなみに記事のタイトルを「中学受験の問題で動的計画法に入門する」とかにしようか悩みましたがそうするとネタバレになってしまうのでやめました

それでは実際にここまでの考察をコードに落とし込んで行きましょう。

今回はC++を使って書いて見たいと思います。(なるべく基本的な言語機能のみで簡単に書いて行きます)

コードを書く前にもう一度ポイントをおさらいすると

  • ある大きな問題を、同じ形をしたより小さな問題に帰着させ、その小さな問題の解を使って大きな問題を解く
  • 分割したより小さな部分問題の解を記録し、再利用することで時間計算量を効率化する

以上が動的計画法のポイントでした。

まず部分問題の計算結果を記録していくことについてですが、これを実現するには俗にいうDPテーブルというもの用意します。今回は考慮すべきパラメーターが $x$ と $y$ の二つあるため、DPテーブルを二次元配列を使って実現します。

そして次に小さな問題の解を使って大きな問題を解くについてですが、まずはコードを書く前に式を考えて見たいと思います。

ここまでで既に、ある点への経路数は、左隣の点への経路数と一個下の点への経路数の和である ことがわかっています。この関係性を使って式を立ててみましょう。

$F(x, y) :=$ 点 $(x, y)$ の経路数 

とすると・・・

$F(x, y) = F(x, y - 1) + F(x - 1, y)$

という式が立てられそうです。

ですが、よくよく考えるとこの式は完璧ではありません。

例えば $x = 0, y = 3$ のときに $F(0, 3) = F(0, 2) + F(-1, 3)$ となりますが、$(-1, 3)$ という点は存在しないのでおかしなことになってしまいます。

同じように $y = 0$ のときもおかしくなってしまいます。

というわけでしっかりと場合分けを考慮してもう一度ちゃんと式を立ててみましょう。

\begin{eqnarray}
F(x,y)
 =
  \begin{cases}
    1 & ( x = 0 \text{ and } y = 0 ) \\
    F(x, y - 1) & ( x = 0 \text{ and } y > 0 ) \\
    F(x - 1, y) & ( x > 0 \text{ and } y = 0 ) \\
    F(x, y - 1) + F(x - 1, y) & ( otherwise )
  \end{cases}
\end{eqnarray}

こんな感じでしょうか。ちょっと場合分けが多いですね・・・
もうちょっと考えると、$x$ または $y$ が $0$ ならそれより左側または下側どちらか片方にしか点がない、つまり経路が複数になる可能性がないため、 $1$ としてしまっても良いことがわかります。

そうすると下記のように、よりシンプルな式にすることができますね!

\begin{eqnarray}
F(x,y)
 =
  \begin{cases}
    1 & ( x = 0 \text{ or } y = 0 ) \\
    F(x, y - 1) + F(x - 1, y) & ( otherwise )
  \end{cases}
\end{eqnarray}

あとはこの式で表現される関係をそのままコード化すれば部分問題を使ってより大きな問題を解くといったことが実現できそうです。

ちなみに、このような式を漸化式と呼んだりします。

ところでDPを実現する方法として代表的なものに、配るDP5貰うDP5メモ化再帰(どれも本質的にはほとんど同じです)の3つがあります。

ざっくり説明すると、

  • メモ化再帰はトップダウンで文字通り再帰的にDPテーブルにメモしながら解いていくやり方(すでにDPテーブルに結果がメモされていればその値を使い回す)
  • 貰うDPは小さい方から大きい方へ、現在みている部分問題をそれより小さい部分問題の結果を使って解いていくやり方
  • 配るDPは小さい方から大きい方へ、現在みている部分問題の結果を部分問題の関係性を利用してより大きいほうへ配りながら解いていくやり方

です。

今回の場合だと、漸化式をそのまま再帰関数で書いてメモ機能を入れつつ実装すればメモ化再帰、ボトムアップなループで下からやっていくような実装をすれば貰うDPになります。

ですが、実は今回の問題では配るDPのほうが簡単にコードが書けるのでそっちでやってみたいと思います。

なぜ配るDPのほうが簡単にコードが書けるのかはいったん置いておいて、実現方法を見ていきましょう。

配るDPで実現する場合、小さい方から順番に、ある部分問題の解 $=$ つまりある点の経路数をより遠い点に配っていきます。

具体的には、点$(x, y)$ の結果を点$(x, y + 1)$ と点$(x + 1, y)$に配ってやれば実現できます。

では実現方法がわかったところで、なぜ今回の問題で配るDPのほうがコードを書くのが簡単なのか考えてみましょう。

メモ化再帰の場合も貰うDPの場合も $x$ または $y$ が0以下の場合を考慮する必要があります(再帰の場合はベースケースとして、貰うDPの場合は配列外参照やセグフォを防ぐため)。ですが配るDPの場合はそもそも大きい方しかみないので $x$ や $y$ が $0$ だったとしてもそれより小さい方を考慮する必要がないことがわかります。(ただし、どんどん大きい方へ配ろうとすることを考えるとテーブルをちょっと大きく持っておく必要がありますが、逆に言うとそれだけで済みます)

では実際にコードを書いて見ましょう。

#include <iostream>
#include <cstring>
using namespace std;

int main() {
  // dpテーブル
  int dp[10][10]; // [10][10]も必要ないですが、余分にとっています

  memset(dp, 0, sizeof(dp)); // 一旦dpテーブルを0で初期化します

  dp[0][0] = 1;

  for (int x = 0; x < 4; x++) {
    for (int y = 0; y < 4; y++) {
      // 「配るDP」
      dp[x + 1][y] += dp[x][y];
      dp[x][y + 1] += dp[x][y];
    }
  }

  cout << dp[3][3] << endl;

  return 0;
}

最初のdpテーブルの初期化時に余分にサイズを大きくとっていますが、それだけです。if文すら登場しません。

この問題の正解は $20$ ですが、このコードを実行すると正しく $20$ という結果が出力されます。:clap:

自力で解けた方はおめでとうございます!:thumbsup:

ちなみに点$B$ を $(6, 6)$ とした場合の答えは $924$ です。

解法2

ではもう一つの解法を見て行きましょう。(こちらの解法は義務教育の範囲をちょっと飛び出して、高校数学の知識を使います。)

数学が得意な人はちょっと考えると図からパスカルの三角形6が見えると思います。

もしかすると問題を見た瞬間に「パスカルの三角形やんけ!」となったかもしれません。

そもそもパスカルの三角形って何?な方向けにWikipediaへのリンクを貼っておきます。

各点から矢印を書いてみるとよりわかりやすいかもしれません。

Frame 2.png

首が柔らかく135度回転させられる人は、首の付け根を中心として頭を左下側に135度倒して図形をみてみるとよいかもしれません。

首が折れてしまうかもしれないので、図のほうを回転してみるとこんな感じです。

Frame 3.png

どうでしょう?パスカルの三角形が見えたのではないでしょうか?

パスカルの三角形が見えなかった方は解法1の考え方を使って、図の各点に経路数を書き込んでみるとわかると思います。(これをやると答えが求まっちゃいますが・・・)

ということは、

  • $(0,0)$ を ${}_0 \mathrm{ C }_0$
  • $(1,0)$ を ${}_1 \mathrm{ C }_0$
  • $(0,1)$ を ${}_1 \mathrm{ C }_1$
  • $(2,0)$ を ${}_2 \mathrm{ C }_0$
  • $(1,1)$ を ${}_2 \mathrm{ C }_1$
  • $(0,2)$ を ${}_2 \mathrm{ C }_2$




としてコンビネーションを使って各点の経路数を表現することができます。

そうすると点$B$ $(3,3)$ は ${}_6 \mathrm{ C }_3$ だとわかります。

あとはを $ {}_6 \mathrm{ C }_3 $ を計算するだけです。(プログラミングするまでもないですね:sweat_smile:

{}_6 \mathrm{ C }_3 = \frac{6 \times 5 \times 4}{3 \times 2 \times 1} = 20

以上で $20$ と正しい答えがでて問題を解けました!:clap:

おわりに

いかがでしたでしょうか?
中学受験と言えど、大人が解いてもなかなか面白いと思います!

ちなみに今回の問題は動的計画法としてみるとかなり簡単な問題です。
もっとしっかり勉強してみたいと言う方は こちらの記事 がとてもわかりやすいのでオススメです!

さて、明日は@ym1KBさんです。よろしくお願いします。


  1. 業務プログラミング 

  2. 専門知識というよりは考える力を求められる問題が多く、普通に大人が解いても難しく面白い問題が多いと思いました 

  3. 開成中学の2019年の算数入試問題・・・あたりがベース 

  4. MECE: Mutually Exclusive and Collectively Exhaustive とか呼ばれたりもしますね 

  5. 配るDP、貰うDPの呼称はこちらの記事より拝借しました。 

  6. この手の組み合わせが絡んでくる問題ではパスカルの三角形が潜んでいたりすることがよくあります 

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした