競技プログラミングとは何か
競技プログラミングをご存知でしょうか。競技プログラミングは制限時間内で与えられたコーディングの問題を解くコンペティションです。様々なものがありますが、中でも日本発の競技プログラミングサイトAtCoderは有名です。
入茶しました
AtCoderで競技プログラミングのレート戦に参加するとユーザーにはレートとそれに対応する色が与えられます。
色は上から、
| 色 | レート |
|---|---|
| 赤 | 2800- |
| 橙 | 2400-2800 |
| 黄 | 2000-2400 |
| 青 | 1600-2000 |
| 水 | 1200-1600 |
| 緑 | 800-1200 |
| 茶 | 400-800 |
| 灰 | 0-400 |
があります。灰色はレート戦のコンペティションに一回参加することで自動的に付与されます。
AtCoderでは上位の色に昇格することをよく「入茶する」「入緑する」と言います。
私はAtCoderを始めておよそ3ヶ月で入茶しました。そこで、その備忘録を兼ねて学習マップを記事化してみました。入茶を目指す方の参考になれば幸いです。
筆者のプロフィール
- 理学部（非情報系）の学部卒
- 基礎数学（線形代数、微分積分、統計学、解析学など）を大学で履修してる
- 基本情報技術者試験 合格
- Python 3 エンジニア認定基礎試験 合格
- PythonとJavaの実務経験は一年未満
AtCoderを始めて感じたこと
私は当時一番慣れていたJavaを使ってAtCoderを始めました。最初に感じたことは想像以上に難しいということです。準備をせずに挑んだ初めてのコンペティションの結果は惨憺たるものでした。
A問題と呼ばれる一問目（配点は１００点）はあまり難しくないのですが、B問題からは難易度が上がります。そして、C問題からはさらに格段にレベルが上がり、最初は全く手が付けられませんでした。最初は正直「しんどい」という気持ちが大きかったように記憶しています。
言語選択：Pythonに切り替えた
Javaで始めた競技プログラミングですが、途中でPythonに乗り換えました。Javaは大規模開発やアプリ開発で絶大な支持を受ける強力な言語ですが、競技プログラミングでは複数のクラスファイルを作ったり、カプセル化したりする必要がないので、Javaの良さを活かす機会が少ないように感じます。記述がシンプルで、文法ではなくアルゴリズムの実装そのものに意識を集中できるという点で私はPythonを選びました。
もちろん、CやJavaのような高速なコンパイラ言語は実行時間制限面では秀でています。ただ、PythonにはNumPyなどのCで書かれた高速なライブラリが存在するので、うまく使えば計算量を減らして処理を高速化することができます。また、Pythonで競技プログラミングに参加する人は多く、情報が多いことも大きなメリットです。
ただし、情報の多さではPythonよりもC++に軍配が上がるかとは思います。C++は非常に高速で、競技プログラミングでは最も人気のある言語です。私もC++は学習中で、ある程度うまくコーディングできるようになったらC++へ切り替えたいとも思っています。
入出力のメソッドを完璧に
AtCorderでは難易度の昇順にA問題、B問題、C問題と出題されます。A問題とB問題についてはアルゴリズムの実装自体が難しい問題は基本的に出題されません。では何が難しいかというと入出力です。
例えば、整数NとMがスペース区切りで与えられるというような状況がよくあります。そのようなときは、
N, M = map(int, input().split())
のように書きます。
また、AtCoderではスペース区切りでプロンプトからのリストの入力を与えられることがあります。そのようなときは、例えばintのリストであれば、
L = list(map(int, input().split()))
のように書きます。
さらに、複数行のリストなどが与えられるケースもあります。Pythonを使うのであれば、リスト内包表記での入出力をマスターすると良いと思います。
これらの入出力さえマスターすればA問題とB問題は多くの場合制限時間内に解くことができると思います。
テストケースは全て試してから提出
AtCoderの問題にはテストケースが用意されています。解けると気がはやってすぐに提出したくなりますが、誤答してしまうとペナルティが課されてしまいます。落ち着いてテストケースを試し、クリアしてから提出しましょう。
APG4bPythonの例題19問を解く
AtCoderにはPython入門 AtCoder Programming Guide for beginners (APG4bPython) という常設コンテストが用意されています。常設のコンテストはレートには関係しません。Python初心者の私はまずは文法の基本事項を抑えるためにもこの例題に取り組みました。
APG4bPythonは完全にプログラミング初心者でも地理組むことができる内容です。
例題は19問あります。後半には少し発展的な問題もありますが、あまり考えこみすぎずに調べながら取り組むとよいと思います。
計算量の概念を理解する
アルゴリズムの世界で重要なキーワードが計算量と呼ばれるものです。計算量は計算時間とも呼ばれ、アルゴリズムの中でだいたいどれくらいの計算が必要かを意味します。計算量は$O(N)$や$O(N \log N)$などと表されます。「だいたい」というとあいまいな感じがしますが、有用です。同じ問題に対するアルゴリズムであれば、計算量が小さいアルゴリズムの方が優秀だということができます。
計算量が分かっていれば、具体的に何回計算するということを計算せずに、$N$が大きくなったとき、計算回数がどのように増加するかを見積もることができます。
計算量は最も早く増加する項に合わせます。例えば、具体的な計算回数が変数$N$に対して、$N^2+2N+7$だとすれば、このときの計算量は$O(N^2)$です。なぜならば、$N$が十分に大きいとき、$2N+7$の項は全体に対する寄与の割合が$N^2$に対して限りなく小さくなってしまうからです。
考えるまえにfor文を書かない
Now is better than never.
ずっとやらないでいるよりは、今やれ。
Although never is often better than right now.
でも、今"すぐ"にやるよりはやらないほうがマシなことが多い。
——Zen of Python
正解を導くアルゴリズムであっても時間制限超過となるとAtCoderでは得点できません。前章で説明した計算量を考慮することは大変ですが、まずは安易にfor文を書かないというのが大切だと個人的には感じました。問題を一つ例にとって解説します。
CでもDでも割れないA以上B以下の数の個数を求めよという問題です。悪い実装はこのようなものです。
A, B, C, D = map(int, input().split())
ans = 0
for i in range(A,B+1):
if i % C == 0:
continue
elif i % D == 0:
continue
else:
ans += 1
print(ans)
一見問題ないように見えます。ロジックはシンプルで
- 変数
ansを0で初期化 -
AからBまでforループ -
CまたはDで割れる場合を除いてansにインクリメント
となっています。しかし、この方法ではTLE（時間制限超過）となります。条件から、この方法ではfor文を最悪で1京回も繰り返すことになるからです。（このときの計算量を$A$、$B$、$C$、$D$を使って表すとどうなるかぜひ考えてみてください。）
問題を前に一度立ち止まって考えてみると、先ほどよりシンプルな方法があることに気づきます。次に示すのは良い実装です。（もっと良い実装があるかもしれませんが、一応これでテストケースをクリアできます。）
import math
A, B, C, D = map(int, input().split())
def f(X):
return X - X // C - X // D + X // math.lcm(C, D))
print(f(B) - f(A - 1))
関数f(X)はX以下の整数でCでもDでも割り切れない数をカウントする関数です。実はこの問題にfor文は必要ありません。関数の内部ではXからCで割り切れるもの、Dで割り切れるものを引き、最後に重複して引いている分を最小公倍数を使って足し合わています。注意点としてmath.lcm()が登場したのはPython3.9以降です。お使いの環境でもし使えない場合は(C * D)//math.gcd(C, D)でもmath.lcm(C, D)と同じ意味になりますので、そのように記述してください。
ちなみにこのアルゴリズムにおける計算のボトルネックはmath.lcm(C, D)です。math.lcm(C, D)は、内部的に 最大公約数（GCD）を計算してから割り算・掛け算をする形で実装されているようです。GCDの計算にはユークリッドの互除法が使われており、この計算量は$O(\log(\min(C, D)))$です。
BFS、DFS、ダイクストラ法を学ぶ
A問題とB問題を解けるようになったら、次はC問題とD問題です。ここから急激に難しくなります。
ひたすら沢山の問題を解くという方法があると思いますが、がむしゃらに取り組むにしても要点を理解することは重要かと思います。頻出はBFSとDFS、そしてダイクストラ法です。これらの意味や実装ついては私の以前の記事や他の方の記事をご参照ください。C問題からはアルゴリズムの実装力を問われます。グラフを使った問題が多く出るので、BFSとDFS、ダイクストラ法を理解すると取り掛かれる問題の幅は急激に広がります。
以下は過去に私が書いたBFS、DFS、ダイクストラ法の記事です。
解けるE問題は拾う
問題は難易度の昇順なのでE問題やF問題は難問です。しかし、問題を読まずに諦めてしまうともったいないということがあります。C問題が解けるようになったら、D問題だけでなくE問題の問題も読んでみることをお勧めします。
実感として、E問題は一定の確率で数学的によく考えれば実装自体は簡単に済むという場合があります。私の場合は処理の流れを可視化するため手元に紙を用意して方針を考えるようにしています。
まとめ
C問題が安定して解けるようになれば入茶することができます。コンペティションの参加回数が少ないと実際のパフォーマンスレートより低い値が出ます。最初はなかなかレートが上がりませんが、まずは繰り返しトライしてみることが大切だと思います。