はじめに
最近AtCoderというオンラインで開催される競技プログラミングコンテンストに本気で取り組んでみようかと思って、毎日もくもくと過去問を解いています。
ただ、プログラマーとしての実務経験はあるとはいえ、数学については高校を卒業してから一度も関わることがなかったため、数学独特の記号や定義が出てくるだけで問題文を理解することさえできません。
今年中に水色コーダーを目標にしているので基礎的な数学への理解は必須だと思い、中学校の数学から学び直すことにしました。
そんなとき、数学についてGoogle検索していると、「数学オリンピック」というワードを目にしました。
数学オリンピックって、あの数学の天才たちがやるやつだ！！
中3数学の途中まで終わらせた今の自分なら、もしかしたら一問くらいわかるのでは？という謎の自信から、問題に挑戦するに至ります。
※数学オリンピックという超高難度の問題に挑戦してそうなタイトルですが、挑戦した筆者は数学、および競プロは初心者です。温かい目で見守ってください。
数学オリンピックとは？
まったく詳しくないので、興味のある方はこちらを御覧ください。
第31回(2021年)JMO予選問題に挑戦
特に意味はありませんが、最新の問題に挑戦することにしました。
JMOは予選、本選、春合宿と進んでいくそうですが、数学の素人が予選飛ばして本選以降の問題が解けるとは思わないので、今回は予選問題に挑戦してみます。
- 問題１
互いに素な正の整数 m, n が m + n = 90 をみたすとき, 積 mn としてありうる最大の値を求
めよ.
互いに素な正の整数？
タガイニソ？
素数ってこと？
よくわかりませんが、素数ということで実装することにしました。
これは力技でいけそうですね。
実装のキモは素数判定をどうやるかです。
2から88の中からすべての素数を取り出し、それを全探索（二重ループ）で探してやれば見つかりそうです。
素数とは...
1とその数自身との外には約数がない正の整数。
さっそく実装してきます。
- 実装
def is_prime(num: int):
"""
#素数判定
"""
for i in range(2, num):
if num % i == 0:
return False
return True
def main():
P = [i for i in range(2, 89) if is_prime(i)]
Q = P
ans = [p*q for p in P for q in Q if p+q == 90]
print(max(ans))
if __name__ == '__main__':
main()
- 実行結果
2021
- 正解
おお！合ってる！！
数学オリンピックの問題解けた！
普通に感動しました。
- 実装の解説
特に難しいコードではないので解説はいらないかもしれませんが...
まずはP,Qに、2から88までの素数をリストに突っ込みます。
なぜ2から88までかというと、
・素数は2から始まる。
・p+q=90という条件があるので、最小値+最大値=90 → 2+88=90で十分だと思ったからです。
※range関数の第2引数は-1番目までしか見ないので+1しておきます。
P = [i for i in range(2, 89) if is_prime(i)]
Q = P
続いて
素数判定の関数です。
def is_prime(num: int):
"""
#素数判定
"""
for i in range(2, num):
if num % i == 0:
return False
return True
素数は、1と自分自身以外に約数を持たないので、２から自分自身−１番目までを順番に見ていき、一回でも割り切れてしまったら素数ではないのでFalseを返します。
素数の場合だけP,Qに突っ込むようにします。
そしてこの2つのリストを全探索していきます。
ans = [p*q for p in P for q in Q if p+q == 90]
print(max(ans))
p+q=90の場合だけp*qをansというリストに突っ込み、最後にそのMAX値を出力してあげればOKです。
はい！以上！
と言いたいところですが、タガイニソ？がちょっと気がかりです。
勝手に素数ということで進めてしまいましたが、これから数学を学び直すにあたってわからないことは放置するわけにはいきません。
ググりました。
wikiによると
二つの整数 a, b が互いに素（たがいにそ、英: coprime, relatively prime, prime to[1]）であるとは、a, b を共に割り切る正の整数が 1 のみであることをいう。このことは a, b の最大公約数 gcd(a, b) が 1 であることと同値である。
なるほど。。。
タガイニソは素数じゃない！！！
ということで、答えは合っていますが、実装しなおしです。
- やり直し
やり直しとはいえ、そんなに大きく変える必要はなさそうです。
上述した素数判定の関数をタガイニソ判定してくれる関数に書き換えてあげればいけそうです。
wikiにもご丁寧にgcd関数を使えというようなヒントが見えています。
import math
def is_tagainiso(p: int, q:int):
"""
タガイニソ判定
"""
# 2つの整数p,qの最大公約数が1であるときp,qはタガイニソというらしい
if math.gcd(p, q) == 1:
return True
return False
def main():
P = [i for i in range(2, 89)]
Q = P
ans = [p*q for p in P for q in Q if p+q == 90 and is_tagainiso(p, q)]
print(max(ans))
if __name__ == '__main__':
main()
- 実行結果
2021
できました！！
- 解説
タガイニソ判定のところだけ解説します。
コメントでも書いてあるとおり、2つの整数p,qの最大公約数が1であるときp,qはタガイニソというらしいので、pythonのmathモジュールに標準で用意されているgcd関数を利用させてもらいます。
これは、引数に2つの整数を渡すと、最大公約数を返してくれるというまさに、タガイニソ判定の申し子。最大公約数が1の場合はタガイニソと判断して良いので、1の場合のみTrueを返すようにします。
そして、全探索の条件に、and条件で付け加えてあげればOK。
これで初めて解けたと言えると思います。
ちゃんと疑問を持ってよかった。
2問目以降
全くわからん。。
結論
1問だけ解くことができました。
これあれですかね。1問も解けなかったらせっかく参加した学生が挫折してしまうだろうということで、1問目はわりと易しめにしてるんでしょうか。
(易しめと言いつつタガイニソがわからなかった)
もっとPythonと数学の勉強をして本質から理解できるようになりたいと思いました。
タガイニソは勉強になりましたね。
知らなかった方はこの記事で覚えてもらえると幸いです。
もっといい解き方あるとか、そもそも間違ってるとかあればご指摘お願いいたします。
(2問目以降、Pythonで解けました報告あると嬉しいです...)
JMO予選問題
そしてAtCoderも2021年3月から本気出してやってますので、一緒に頑張ってくれる仲間募集してます！！