東大の問題をプログラミングでボコボコにしたい！　～2017年理系第3問ほか～

皆さんこんにちは。東進衛星予備校　金沢南校の北川と申します。

大学入試の数学は難しいです。一見しただけではとても解けそうにない問題というのが、多数あります。それはそれはムカつくぐらい難しい問題も！

これらの問題が「一見しただけでは解けない」理由を考えてみると、「愚直にやると人間には処理不能な計算量となるから」というケースが多々あります。例えば以下の問題。

この問題は「原点を出発した点が上下左右に動くとき、6秒後に特定の位置にいる確率はどれくらいか？」というような話をしています。6秒間の上下左右の組み合わせは有限パターンしかないので、理論上は点の動きを全部書き出してみて、最後にどこにいるかを確かめればよいことになります。

しかし、それは人間の手ではかなり難しいでしょう。上下左右を6回組み合わせる、と考えれば、あり得る点の動きは\(4^6=4096\)通りです。さらにはその4096通りそれぞれについて、最後に点がどこにいるのか考える必要があります。要するにこういうことです。

「えーと、上上下下右右と動いたら、最後は(0,2)やな……」
「次は、上上下下左右やと……お、(0,0)や！」

これを4096回！ これでは計算というよりは拷問です。普通の人は拷問を受けたいとは思いませんから、別の方法を探すべきでしょう。拷問を受けてでも東大に入りたいという人は、この格闘ゲームのコマンドみたいな文字列を4096回検証するかもしれませんが（でもそんな時間と根性があったら東大の試験なんて受けずに、そのスキルで社会貢献するのが良いようにも思います。例えばその能力で雑誌の誤植を見つけて、手紙の一通でも出版社に送った方が、世の中は確実に良くなるような気がします）。

ともあれ、人間がやると拷問になってしまうこの「全部シミュレーションする」という手法。コンピュータなら上手く指示を与えることでやってくれそうな気がします。

そこで今日は大学入試の問題にプログラミングで殴り込み、普段辛酸を舐めさせられている憎き相手をボコボコにしてみたいと思います。力こそパワー、パワーこそ力。

上の問題も合わせて、全部で2問解きます。早速やっていきましょう。

目次

1.点の動き全部シミュレートする～再帰を使って楽しよう！～

2.直線と点とコンビネーション　～itertoolsで組み合わせの問題を破壊しよう！～

3.おわりに

1.点の動き全部シミュレートする～再帰を使って楽しよう！～

今回は、先ほど取り上げた東大理系2017年度の第2問を取り上げたいと思います。
問題を再掲しますね。

この問題を解くには、まず問題を分割するところから始めます。今回は全部点の動きをシミュレートする方針で解きますから、こんな感じでしょうか。

この各ステップを実装できればどうにかなりそうです。
今回は学校で習っている人も多く、かつ可読性も高いPythonで記述していきたいと思います。私がまともに書けるのがPythonだけとか、そんな理由ではないです。そんな理由ではないということにしといてください[1]。

さて、では点の動きをシミュレートするところから始めましょう。

ここも問題の細分化がカギを握ります。まず原点にある点が、最初の1秒で上下左右4か所のどこかに動きます。仮に上に動いたとしましょう。そしたら、上に動いた点も、次の1秒で上下左右のどこかに動きます。次も上に動いたとしましょう。そうすると同様にその点も次の1秒で……という「同じ動作の繰り返し」が発生します。

同じ操作を繰り返すなら、for文やwhile文、そして再帰が使えそうです。
今回は再帰を使って幅優先探索[2]のようなことをしてみます。動作としてはこんな感じ。

このような関数を用意し、初期値として[0,0,0]をキューに追加しておけば（つまり、「0秒後に点Pが点(0,0)にいる」という情報を与えておけば）、想定通りの動作をしそうです。

では、この関数を実装してみましょう。こちらのようになります。

def tansaku(points):
    head = points.popleft()
    if head[0] <= 5:
        t = head[0]
        x = head[1]
        y = head[2]
        for i in range(-1, 2, 2):
            points.append([t + 1, x + i, y])
            points.append([t + 1, x, y + i])
        tansaku(points)
    else:
        points.append(head)

tansaku関数の中にtansaku関数が入れ子になっています。これで再帰が実装できたはずです。

あとはこんな感じで初期化して動かしてみると……。

#キューを実装するためのライブラリを追加
import collections

def tansaku(points):
（省略）

#初期化
points = collections.deque()
points.append([0, 0, 0])

#実際に動かす
tansaku(points)

#最終的な点の個数を出力
print(len(points))

意気揚々と動かしてみると、こんな出力が。

RecursionError: maximum recursion depth exceeded

エラーですね。恐らく再帰を勉強する際に1回は絶対に見ることになるエラーです[4]。端的に言えば「再帰の上限回数に引っかかってるよ！」という内容です。
以下のコードを書くと、再帰の上限回数を確かめることができます。

import sys
print(sys.getrecursionlimit())

出力はこうです。

1000

つまり私の環境では、再帰関数が再帰を回せる上限回数が1000回までになっているようです。思い出してみると、この問題では最終的に4096個の点の位置をシミュレートするはずですから、1000回では全然足りません。

こういう時は再帰上限を引き上げないといけません。今回なら、以下のようなコードにする必要があります。

import collections
import sys

sys.setrecursionlimit(10000)

def tansaku(points):
（省略）

#初期化
points = collections.deque()
points.append([0, 0, 0])

#実際に動かす
tansaku(points)

#最終的な点の個数を出力
print(len(points))

理論上は5000回あれば充分ですが、余裕をもって10000回まで回せるように上限を解放します。

するとしっかり、以下のように出力されます。

4096

ちゃんと4096個の点が最終的に吐き出されているのが分かります。中身を全部見てもいいのですが、4096を人力で見つめるのはキツいですので、個数をもって一旦大丈夫だということにしましょう。

これで最もヘビーな探索用関数の実装が終了です!

あとはもう流れ作業ですから、さっさと実装してしまいましょう。

import time
import collections
import sys
import fractions

sys.setrecursionlimit(10000)

#探索用の関数を定義
def tansaku(points):
    head = points.popleft()
    if head[0] <= 5:
        t = head[0]
        x = head[1]
        y = head[2]
        for i in range(-1, 2, 2):
            points.append([t + 1, x + i, y])
            points.append([t + 1, x, y + i])
        tansaku(points)
    else:
        points.append(head)

#時間計測開始
start = time.time()

#pointsをqueとして動作するように作成
points = collections.deque()
points.append([0, 0, 0])

#探索用の関数を動かす
tansaku(points)

#(1)の場合の数と(2)の場合の数を格納する変数を初期化
count_1 = 0
count_2 = 0

#pointsの中で条件を満たすものをカウント
for i in points:
    if i[1] == i[2]:
        count_1 += 1
    if i[1] == 0 and i[2] == 0:
        count_2 += 1

#分数として表記
bunbo = 4 ** 6
answer_1 = fractions.Fraction(count_1, bunbo)
answer_2 = fractions.Fraction(count_2, bunbo)

#時間計測終了
end = time.time()

#結果の出力
print('(1)の答えは' + str(answer_1))
print('(2)の答えは' + str(answer_2))
print('in' + str(end - start) + 'sec.')

timeモジュールを使うことで、時間の計測を行いました。

またfracitionsというライブラリを使うことで、有理数を表現できるというのはかなりありがたいですね。約分も勝手にやってくれるので、本当に出たままの値を放り込んでおけば問題ないというのも素晴らしい。

これを実行すると以下の通りの結果が出ます。

(1)の答えは5/16                                                                                 
(2)の答えは25/256                                                                               
in0.0013930797576904297sec.

0.013秒です。
だいたい60fpsのゲームにおける1フレームがこれくらいの時間ですから、訓練されていない人間には正確に見極めるのが難しい時間、しかしゲームのスピードランをする人の中には自覚的に見極められる人がいる、それくらいのラインです。

そのわずかな時間で、コンピュータは正確な答えをはじき出すわけです。恐ろしい。今皆さんが手に握っている、或いは相対している四角いインターフェースの奥にすさまじい能力があるということが直にわかって面白いですね！

2.直線と点とコンビネーション　～itertoolsで組み合わせの問題を破壊しよう！～

次に扱う問題はこちら。2020年の東京大学文科の問題です。

先ほどとは違う趣がある問題ですね。点を5個選び、いくつの直線をカバーするのかを考えるという問題です。

漏れずにすべて調べ上げるのはやや難しい問題ですが、コンピュータならきっと1秒と掛からず処理を終えてくれるので、頑張ってコードを書いてみようと思います。

今回は16個の点から5個の点をピックアップするというルールですから「点に0～15までの番号をふっておき、その数字の中から5個選ぶ」という風に問題を読み替え、0～15の数字の中から5個選んでできる数字の組を漏れなくダブりなく数え上げることから始めていきます。

……何のライブラリも使わずにやるとなったら結構きついですね。一応5重くらいにforを噛ませてなんやらかんやら処理を記述すれば行けそうな気もしますが、とてもやりたいとは思えないです。

ここで登場するのがitertoolsです！ 組み合わせや順列に関するイテレータを作ってくれる超便利なライブラリで、これがあるおかげで非常に簡単になった入試数学の問題が結構あります。

例えば、先ほど書いた「0～15の数字で作れる5つの数字の組をすべて列挙してほしい」という要求に対しても、以下の通り書けば済む話です。

import itertools

zhunretsu = [ i for i in range(16)]
it_zhun = itertools.combinations(zhunretsu, 5)

5重のforなんて書く必要はなく、たったこれだけでit_zhunという変数の中に所望のイテレータが格納されることになります。最高か？

あとはイテレータの中から順番に点の選び方を取り出していき、それぞれについて(1)と(2)の条件を満たしているか検証していけばよいです。

(1)の条件は一見難しそうに見えますが、具体例を見てみると分かりやすいです。

例えば5つの点として(1,1),(1,2),(1,3),(1,4),(2,1)を選んだとき、y=1,2,3,4上には点があることが分かります。また、x=1,2上にも点があることは明らかです。一方で、x=3,4上にだけは点が一切ないので、これは(1)の条件を満たしていることになります。

これは「x座標に出てくる数値の種類数」と「y座標に出てくる数値の種類数」の和がぴったり6になっていればよい、という話に一般化できます。種類数をカウントしたければ、pythonにはset型がありますから、これをうまく使えばよさそうです。
同じように(2)も処理することを考えると、以下のようなコードが書けます。

import time
import itertools

#時間計測開始
start = time.time()

#対象となる点を全列挙
points = []
for i in range(1,5):
    for j in range(1,5):
        points.append([i, j])

#数の選び方の組を全列挙
zhunretsu = [ i for i in range(16)]
it_zhun = itertools.combinations(zhunretsu, 5)

#答えとなる数値を格納する変数を初期化
count_1 = 0
count_2 = 0

#列挙の仕方に応じてチェック
for i in it_zhun:
    lines_x = set()
    lines_y = set()
    for j in range(5):
        lines_x.add(points[i[j]][0])
        lines_y.add(points[i[j]][1])
    if len(lines_x) + len(lines_y) == 6:
        count_1 += 1
    if len(lines_x) + len(lines_y) == 8:
        count_2 += 1

#時間計測終了
end = time.time()

#答えを返す
print('(1)の答えは' + str(count_1))
print('(2)の答えは' + str(count_2))
print('in' + str(end - start) + 'sec.')

これを実行すると、以下のように返ってきます。

(1)の答えは1824
(2)の答えは432
in0.004859447479248047sec.

実に0.0048秒……3～4フレームくらいでしょうか。さっきの問題の3～4倍かかってるという見方もできますが、結局0.01秒にも満たない短時間で解かれているので誤差かもしれません。

いずれにせよ、人間ではとてもできないことを機械がやってくれたわけです。

3.おわりに

ということで、今回は2問ほど東大入試の問題を解いてみました（解いたといえるのかこれは）。普通、入試問題はこうやって解くものではないのですが、時にはこういう「なんかちょっといけないことをしている感じ」の解法も悪くないのではないでしょうか。

ところで、いわゆる技術系の話としては、今回の内容は「初心者が通過する大したことはない話」というレベルの話だと思います。逆に言えば、さほど高級なことを一切せずともちょっとした頭の体操で数学の問題が解けてしまうという面白さや、実際に再帰やitertoolsを使うのはどんな場面か、みたいな部分が伝わればいいかなと思っています。

※当たり前ではありますが、すべての入試数学がプログラミングで解けるわけではありません。というか解けない問題の方が多いでしょう。組み合わせや整数問題の、ごくごくわずかな有限の事象のみを扱う問題しか解けないです。
これはあくまでも入試数学の解法としてはおふざけ記事にすぎませんので、真に受けて怒らないようによろしくお願いします。

[1] いつかC++で書いたコードを載せたいです（願望）

[2] 平たく言うと迷路などの最短経路を求める際に使う探索手法が幅優先探索です。今回の記事では詳しく扱いませんが、深さ優先探索と並んで迷路を解くアルゴリズムとしては基本であり重要なものでもあります。

[3] 平たく言うと、データを追加する際は後ろから、データを取り出す際は前から処理するデータ構造のことです。つまりラーメン屋の行列みたいなもので、並ぶ人は後ろから並び、列から抜けて飯を食う人は先頭の人、みたいな感じ。Pythonだとcollectionsライブラリのdeque型を使って実装するのが一般的（だと認識しています）。

[4] 最初このエラーを見たときは頭の中に疑問符が大量に浮かびました。多分同じ気持ちになった人も多いんじゃないでしょうか。