Python
AtCoder
数学
競技プログラミング

数学科生に競技プログラミングをおすすめしたい

こんにちは,数学科3回生のmo-mo-といいます。ここでは,「数学科生に向けて」私が最近はじめた競技プログラミングについて紹介します。

自分のプログラミング歴

  • C言語の授業で挫折
  • プログラミングとは無縁の生活
  • たまたまプログラミングのレジュメを読む
  • ハマる(現在)

こんな感じです。

競技プログラミングとは数学だ

  • もともとの自分の中のイメージ → ソフトウェア開発??
  • 実際 → めっちゃ数学ですやん!!!

数学科生にはとても有利な競技プログラミング

「競技プログラミングとは,プログラミング能力を競うもの」というのは言うまでもありませんが,競技プログラミングは数学の知識で解ける問題がたくさんあります。数学科の皆さんには"超絶有利"です。厳密には数学だけでは駄目で,アルゴリズム的考え方も必要(問題にもよる)ですが,スペシャリストを目指さない限り,数学が出来ればアルゴリズムの知識は大して無くてもイケます。

例題を見てみましょう。

例題

キャプチャ.PNG
ソース

中国剰余定理の香りがしますね。証明の必要はないですし,答えは直感的にわかる方が多いかもしれません。

キャプチャ.PNG
ソース

これはそこそこ難しい方の問題なので解けなくても仕方ないのですが$a,b,c$を$K$の剰余類($mod\ K$)で考えればわかると思います。

解答例(ネタバレ注意)

もちろん競技プログラミングですから,ただ答えがわかるだけではダメで,プログラミングしないといけません。問題文の変数が数値として与えられるので,それに対して正しい答えを返すコードを書く必要があります。

例えば,1問目なら$N=2$,$(a_1,a_2)=(4,7)$が与えられたときに答えである $9$ を返すコードを書きます。

それでは,Pythonというプログラミング言語で2問の答えを書いてみましょう。雰囲気だけわかれば良いです。

ans1.py
N = int(input())   # Nの入力を整数として受け取る  
l = list(map(int, input().split())) # a_1,a_2,...,a_Nの入力を整数のリストとして受け取る

ans = sum(l) - N   # 答えの計算
print(ans)   # 答えの出力
ans2.py
N, K = map(int, input().split())  # NとKの入力を整数として受け取る

a = N // K  # NをKで割った商を変数aに代入
ans = a**3  # aの3乗を変数ansに代入

if K % 2 == 0:  # もしKを2で割った余りが0なら
    b = (N - K//2) // K + 1
    ans += b**3  # bの3乗をansに加える

print(ans)  # ansを出力

そんなに長いコードじゃないですね。

ちなみにここに書いた2題は,どちらも解ければ1人前のプログラマの称号がもらえるレベルの問題です。競プロerの上位3割に入れます。最近(2018/9現在)は難化傾向にあるので,それ以上かもしれません。

競プロは手軽に始められる

競技プログラミングはPCとネット環境があれば簡単に始められます。難しい手続きといえばアカウント作成くらいで,これも3分もかからないです(というか,全く難しくない)。
また,参加も好きな時(サイトによるかもしれないが大体週1くらいでやってる)に1回100分程度なので,とにかく手軽に始められます。

レーティングが自分の能力の証明に

競技プログラミングは参加すると自分のレート(スコア)が変動し,複数回参加すればそれが自分の実力証明になります。
良い成績を出せば(上の例題レベルの問題がコンスタントに解ければ)IT企業への就職の道も開けます1

競技プログラミングの特徴まとめ

  • ワリと数学
  • ネット環境があれば誰でも始められる
  • 1回100分程度で好きな時に参加できる
  • 複数回参加してスコアを貯めれば実力証明になり,プログラマへの道も開拓できる

競プロサイトのオススメは"AtCoder"

上の例題でも使いましたが,AtCoderというサイトをおすすめします。世界には競プロのサイトはいろいろありますが,AtCoderは日本語で始められるので手軽です2
AtCoderは大体週1のペースでビギナー向けのコンテスト「AtCoder Beginner Contest」を開催しています(よくABCと略されます。もちろんABC予想とは関係ないです)。まずはこれに出場してみることをオススメします。(→ABCの例__ABC109)

ちなみにこのコンテストのC問題が上記の例題です。前述しましたが,C問題がコンスタントに解ければ普通に1人前のエンジニアレベルです。(詳しくはこちら)
頭のいい数学科生なら,特別勉強しなくてもそこそこのレベルまで行けるのではないでしょうか。

プログラミング言語はPythonがおすすめ

当たり前ですが,競技プログラミングが出来るためには,プログラミングが出来なければなりません。プログラミング言語は特にこだわりがないならPythonを勧めます。理由は,

  • C言語で1回挫折した自分でもわかる簡単さ
  • それでいて機能(ライブラリー)は充実
  • AIやらで今流行り
  • 単純に使っている人が多い
  • もちろんマンデルブロー集合も描けます (→)

こんなところです。生半可な気持ちでCやJavaなんかに手を出すと苦労します。
(ただPythonはプログラム実行速度が遅いので,競プロを極めたいならC++等の別の言語も後々勉強していくと良いと思います)

環境構築はしなくても良い

プログラミングの最大の難関は環境構築(プログラミング環境を整えること)かもしれません。Pythonの環境構築としては,

が一般的ですが,別に必要ありません。

例えばAtCoderの場合,ちゃんとホームページ上でコードテストができるようになっていますし,他にも多くの競プロサイトでそうなっていると思います。環境構築で挫折してしまうことは非常にもったいないと思います。

プログラミングの勉強

環境構築は必要なくても,プログラミングの勉強は多少なりとも必要です。それでもそんなに難しい知識は要らず,例えばPythonなら「リスト/if文/for文」くらいの知識があれば(競プロやる上では)最低限事足りると思います。
他にも「クラス/メソッド」などの概念をなんとなく抑えておけば良いかもしれません。

勉強はググるか,本を読むか,講座を提供しているサイトを探せばいいと思います。無理に本腰を入れる必要はありませんし,とりあえずなんとなくやってみようという気持ちで良いと思います。

おわりに

数学科生向けに競プロについて紹介してきたつもりですが,数学科生以外の方にも通じるところはあると思います。自分もまだ初心者なので,一緒に頑張っていきましょう!

参考

AtCoder コンテストについての tips
AtCoderランクとは__Atcoder Jobs


  1. IT企業に就職したいと全力で考えているなら,何か作品を作ってGitHubで公開することもやってみると良いと思います。 

  2. というか,ここまでの解説も全部AtCoderを想定しているので,もしかしたら他のサイトでは違うという情報があるかもしれません。そのときはごめんなさい。