つい最近AtCoderで緑ランクになった者です。
今回は、個人的にどんなことをやってきたか、どんなことに注意しているかをまとめました。
緑ランクになるには
緑ランクになるには次のようなことが必要だと考えています。
- C問題までを15分以内に解く(3完15分)
- D問題を制限時間以内に解く(4完100分)
極論、D問題が解けなくても緑ランクに行くことは可能だと思ってます(時間はかかりそうですが)。
参考までに、僕が最近バーチャル参加したコンテストの結果を以下の表にまとめておきます。
| コンテスト名 | 結果 | レーティング※ |
|---|---|---|
| ABC127 | 3完 | 921 |
| ABC128 | 3完 | 1148 |
| ABC129 | 3完 | 1005 |
| ABC130 | 4完 | 1309 |
| ABC131 | 3完 | 524 |
| ABC132 | 4完 | 1257 |
| ABC133 | 4完 | 1115 |
| ABC134 | 4完 | 1113 |
| ABC135 | 3完 | 1175 |
| ABC136 | 4完 | 1131 |
| ABC137 | 4完 | 1451 |
| ABC138 | 4完 | 1007 |
※バーチャル参加のため、レートは推定のものです。自分とほぼ同じスコアの人のレーティングを参考にしてます。
上の表を見てみると、3完でもレート1148とか1175とか取れてる回がありますね。
ABC131はD問題が簡単だったにもかかわらず、3完で止まってしまった例です。。。
よって、個人的には次のように考えております。
C問題を毎回15分で解いて、D問題も3回に1回は解く！
C問題解くのに15分以上かかったら絶対D問題解いてやる！って気持ちになります。
以下については、A〜D問題を解く際に気を付けていること等をまとめました。
A問題・B問題
AとBは基本的な文法が分かってれば解ける問題がほとんどです。
計算量を気にする問題も特になかったと思うので、単純にfor文とかif文とかを使って解いていきましょう。
また、リストの基本的な処理はできるようにしておきましょう。
l =[]
l.append(1) # リストに追加
a = l.pop() # リストの最後尾を取り出す
l = [i for i in range(N)] # 内包表記
max_l = max(l) # リストの最大値を取得
min_l = min(l) # リストの最小値を取得
そしてB問題ではたまに「N>1の時は通常の処理をするが、N=0の時は例外処理をする」みたいな問題もある（というか自分の書いたプログラムにそういうバグができてしまっていることがある）ので、
import sys
if N == 0:
#特別な処理
sys.exit()
for i in range(N):
#通常の処理
みたいな風に書くことがあります。
C問題
Cは難しい問題もあり、計算量も考慮しなければなりません。
Point1 : 入力データの大きさ見る(計算量を考慮する)
例１：ABC133のC問題
こちらの問題では、入力の大きさが2 * 10^9です。これは1重ループでもTLEになってしまう大きさですので、単純なfor文は使えないなあと思わないといけません。
ですがプラスに考えると、確実に計算量を削減できる方法があるということなので、ヒントにはなります。
例２：ARC061のC問題
こちらの問題では、逆に入力データが10文字以下の文字列となっています。
このように入力データの大きさが極端に少ない問題では、全探索を用いることがほとんどです。
- N <= 10ならbit全探索やn!通りの全探索が使える
- 100 < N < 200なら3重ループまでなら使える
みたいな予想はつきます。あくまで予想ですが。
Point2 : 便利なライブラリ等をメモに書いておく
C問題ではPythonの様々なライブラリやモジュールをimportします。
また、よく使う関数は予め用意しておきましょう。
個人的にC問題で使うライブラリ・モジュール・関数をまとめておきます。
- itertools（組み合わせ・順列・N!通りの全探索）
- math（最小公倍数・最大公約数など）
- 約数の列挙(O(√N)で求められるバージョンのやつ)
- bit全探索（Nが小さい時のみ有効）
- deque（左右の端からappend、popできるリスト）
- heapq（プライオリティキュー）
- collections（出現頻度を数えてくれるやつ）
- bisect（二分探索）
他にもあったらコメントください！
逆に言うと、動的計画法やダイクストラ法、DFSやBFS等の難しいアルゴリズムは使わなくても解ける問題がほとんどです。
D問題
D問題は自分もまだ10回コンテストがあったら7回ぐらいしか解けませんし、30分以内に解ける時もあれば100分ギリギリの時もあるので、安定していません。
個人的には @drken さんのこちらの記事に載っている問題を苦戦せずに解けるようになれれば安定するのかなって思ってます。
ですので、ここに書いてあるアルゴリズムのテンプレートは予めコード化しておいて、あとは問題によってプログラムを追加・改変するって感じが良さそうです。
E問題・F問題
緑コーダーであれば解けなくて大丈夫です。
水色になるにはE問題が解けるようにならないとなので勉強しないと・・・。
最後に
個人的な意見が多いですが、参考になれば幸いです。