数学科生の自分が,「数学科生に向けて」競技プログラミングについて紹介します。
追記
最近の AtCoder は,数学力が必要とされるのはもちろん,アルゴリズム力も前よりも増して必要になっていると思います。
自分のプログラミング歴
- C言語の授業で挫折
- プログラミングとは無縁の生活
- たまたまプログラミングのレジュメを読む
- ハマる(現在)
こんな感じです。
競技プログラミングとは数学だ
- もともとの自分の中のイメージ → ソフトウェア開発??
- 実際 → めっちゃ数学ですやん!!!
数学科生にはとても有利な競技プログラミング
「競技プログラミングとは,プログラミング能力を競うもの」というのは言うまでもありませんが,**競技プログラミングは数学の知識で解ける問題がたくさんあります。数学科の皆さんには"超絶有利"です。**厳密には数学だけでは駄目で,アルゴリズム的考え方も必要(問題にもよる)ですが,スペシャリストを目指さない限り,数学が出来ればアルゴリズムの知識は大して無くてもイケます。
例題を見てみましょう。
追記
最近は コンテストの形態が変わり,300点問題はもう少し易しくなっています。
例題

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

これはそこそこ難しい方の問題なので解けなくても仕方ないのですが$a,b,c$を$K$の剰余類($mod\ K$)で考えればわかると思います。
解答例(ネタバレ注意)
もちろん競技プログラミングですから,ただ答えがわかるだけではダメで,プログラミングしないといけません。問題文の変数が数値として与えられるので,それに対して正しい答えを返すコードを書く必要があります。
例えば,1問目なら$N=2$,$(a_1,a_2)=(4,7)$が与えられたときに答えである $9$ を返すコードを書きます。
それでは,Pythonというプログラミング言語で2問の答えを書いてみましょう。雰囲気だけわかれば良いです。
N = int(input()) # Nの入力を整数として受け取る
l = list(map(int, input().split())) # a_1,a_2,...,a_Nの入力を整数のリストとして受け取る
ans = sum(l) - N # 答えの計算
print(ans) # 答えの出力
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やJavaなんかに手を出すと苦労します。
(ただPythonはプログラム実行速度が遅いので,競プロを極めたいならC++等の別の言語も後々勉強していくと良いと思います)
環境構築はしなくても良い
プログラミングの最大の難関は環境構築(プログラミング環境を整えること)かもしれません。Pythonの環境構築としては,
が一般的ですが,別に必要ありません。
例えばAtCoderの場合,ちゃんとホームページ上でコードテストができるようになっていますし,他にも多くの競プロサイトでそうなっていると思います。環境構築で挫折してしまうことは非常にもったいないと思います。
プログラミングの勉強
環境構築は必要なくても,プログラミングの勉強は多少なりとも必要です。それでもそんなに難しい知識は要らず,例えばPythonなら「リスト/if文/for文」くらいの知識があれば(競プロやる上では)最低限事足りると思います。
他にも「クラス/メソッド」などの概念をなんとなく抑えておけば良いかもしれません。
勉強はググるか,本を読むか,講座を提供しているサイトを探せばいいと思います。無理に本腰を入れる必要はありませんし,とりあえずなんとなくやってみようという気持ちで良いと思います。
おわりに
数学科生向けに競プロについて紹介してきたつもりですが,数学科生以外の方にも通じるところはあると思います。自分もまだ初心者なので,一緒に頑張っていきましょう!
参考
AtCoder コンテストについての tips
AtCoderランクとは__Atcoder Jobs