無知の学生が3ヶ月で緑色コーダーになるまで

Last updated at 2024-07-24Posted at 2024-07-19

タイトル

皆さん、こんにちは、kazuppaです。この度、(7/14)、ABC362において入緑しました！!

そこで、今回は私が灰色コーダー・茶色コーダーの頃にしたことを紹介したいと思います！(ベタな記事ですがお許しください)

そもそも競技プログラミングとはなにか

競技プログラミング(以下、競プロ)とは与えられた問題をプログラミングを用いて実装して、その正確性やコーティングをする速さ、およびプログラムの速さを競う競技。
そういうふうに私は考えています。
また、Wikipediaによると

参加者全員に同一の課題が出題され、より早く与えられた要求を満たすプログラムを正確に記述することを競う
(Wikipedia　競技プログラミングより)

と書いています。
その中でもAtCoderとは競プロを扱っているサイトです。
実際のコンテストでは次のような問題が複数与えられます。

A - Wrong Answer
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 100 点
問題文
$0$ 以上 $9$ 以下の整数 $A,B$ が与えられます。
$0$ 以上 $9$ 以下の整数であって $A+B$ と等しくないものをいずれかひとつ出力してください。
制約
0≤A≤9
0≤B≤9
A+B≤9
A,B は整数
ABC343-Aより

これは与えられた数字AとBを足し算して、その答えと違う数を出力すればいい問題です。
実際にこのような問題が複数与えられて、それに対するプログラミングを早く正確に書く能力を競うのが競プロです。

また、AtCoderにはレートというものがあり、コンテストの結果によってレートが変わっていきます。
400ごとに色が灰、茶、緑、水、青、黄、橙、赤とあり、今より上のレートに上がり、新たな色になるのが競プロerの目標の大きな一つとしてあります。
僕としては、灰から茶、茶から緑...というような感じで順々にどんどんすぐ上がっていくものだと思っていました。しかし、実際のところはそう簡単ではありません。

これはおよそ一年前のデータですが、参加者の大半が灰色。茶色の時点で上位24.1%にも君臨します。つまり灰色から茶色になることはそう簡単なことではないのです。

茶コーダーになるために

AtCoder Beginners Selectionは最初にやろう

AtCoder Beginners Selectionとは問題の提出の方法や、実際に出た過去問で大事なものをまとめたコンテストです。
実際に典型といえるような問題も多く、また初めてのコンテストで提出の仕方がわからなくて終わるということがなくなります。

AB埋めの大事さ

AtCoderを始めてすぐの人（僕も同じく）はまずB問題で詰まります。実際にB問題はAに比べ難易度が高く、実装も大変になります。
しかしAB問題とは
・入力、出力(cin,cout)

・変数の概念、四則演算などの計算(+,-,*,/,%)

・条件分岐(if)

・繰り返し処理(for,while)

。文字列(string)

・浮動小数点(double)

・配列(vector)

これらができれば、あとは組み合わせてコードに落とし込むことで解くことができるレベルだと思っています(Bは多少の工夫が必要ですが)。実際にこれができればだいたいの問題は解くことができるはずです。

一般的にAB問題には三種類のタイプがあるといわれています。
パターン1：答えの可能性があるものを全探索する

B - Mex
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 200 点
問題文
長さ N の整数からなる数列 $A=(A_1,…,A_N)$ が与えられます。
$A_1,…,A_N$に含まれない最小の非負整数を求めてください。
制約
$1≤N≤2000$
$0≤A_i≤2000$
入力は全て整数である
ABC245-Bより

この問題の解としてあり得る数字は$0$~$2000$のみしかありません($0≤A_i≤2000$のため)。
よって、それらの中の数で$A_i$に含まれない最小の数を求めればいいのです。

パターン2：実際にシミュレーションする

B - Uppercase and Lowercase
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 200 点
問題文
英小文字と英大文字からなる文字列 $S$ が与えられます。$S$ の長さは奇数です。
$S$ に含まれる大文字の個数が小文字の個数よりも多ければ、$S$ に含まれる全ての小文字を大文字に変換してください。
そうでない場合は、$S$ に含まれる全ての大文字を小文字に変換してください。
制約
$S$ は英小文字および英大文字からなる文字列
$S$ の長さは $1$ 以上 $99$ 以下の奇数
ABC357-Bより

この問題は実際に大文字の個数と小文字の個数を数え、大文字の方が多かったらすべて大文字にする、そうでないなら小文字にする。というような感じで問題文通りに実装すればいいのです。

パターン3：数学的考察力を使う
ABC249-A
ABC259-B
これらのように数学的な考えを使う問題です。

一般的に出るのは上二つ(特にパターン2)。過去問を解いて上二つのパターンに慣れていればABを安定して解く力がつくということです。
プログラミング力=(データ構造に関する知識+アルゴリズムに関する知識)*コーティング力
で決まると僕は思っています。B問題までに使うデータ構造やアルゴリズムなど高が知れているので、それよりかはコーティング力が大事。そのため、過去問演習でまずやるべきはAB埋め(特にBを優先すべき)だと思います。僕の場合だと、200問弱過去問を解いたあたりで、Bまでの高速ACができるようになっていきました。(個人的には25分弱で2冠はしておきたい)

次はC埋め

B問題を解けるようになり、その次に立ちはだかるのはC問題。C問題はABと違い、
・計算量およびアルゴリズムについての知識
・計算量をできるだけ減らすプログラムの作成
を要求します。
例えば、このような問題があります。

C - Sort
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 300 点
問題文
$(1,2,…,N)$ の並び替えである数列 $A=(A_1,…,A_N)$ が与えられます。
次の操作を 0 回以上 N − 1 回以下行うことで、
A を $(1,2,…,N)$ にしてください。
操作：$1≤i<j≤N$ を満たす整数の組 $(i,j)$ を自由に選ぶ。
A の $i$ 番目と $j$ 番目の要素を入れ替える。
なお、制約の条件下で必ず $A$ を $(1,2,…,N)$ にできることが証明できます。
制約
・$2≤N≤2×10^5$
・$(A_1,…,A_N)$ は $(1,2,…,N)$ の並び替えである
・入力は全て整数である
ABC350-Cより

これは、実際のコンテストに出たC問題です。
愚直な方法だと、Aの1番目の要素が1じゃなかったら1を探し続けてswapをして、Aの2番目の要素が2じゃなかったら2を探し続け....とできます。
しかし、この方法だと実行時間がおよそ$O(N^2)$かかります。この問題の制約は$2≤N≤2×10^5$です。一般的には2秒で計算できるコンピュータの回数は$10^8$~$10^9$ほどなので、$O(N^2)$だと計算量が多すぎてしまい、TLE(Time Limit Exceeded,実行時間オーバー)となってしまいます。
例えばこの問題だと、新たに配列countを作り、count[i]にはiという数字が何番目にあるかを代入し、Aをswapするときにはいい感じにcountもswapするという方法で解けます。
参考：
TLEコード　 ACコード
この問題からわかることとして、
・C問題は愚直な解法では解けないことが多い
一般にBとCでは大きな差があるということの原因はここに尽きると思っています。
当時僕は、解説は解けてない限り見ないというタイプだったので、ほかの問題を解きながら解法がわかったら戻ってくるという感じでやっていました(非推奨)。
直近60回(ABC301~ABC360)のC問題のうち、灰コーダーに解きたいレベル感のC問題は45問。一般に言われてる「入茶にはC問題を7~8割は解けるようにしましょう」にマッチしていると思います。
入茶にはBまでをほぼ確実にACし、C問題もある程度ACできるようになる。それが条件。だと思います。
絶対にABは落とさない。そのうえで簡単なCは必ず解く。
茶色コーダーはこの心意気で本番に臨んでいると思います。この意思で挑めばまた少し変わるのではないでしょうか。
また、Cは必ず解くという意思は大事です。ABを5分で解いて終わる人よりも、ABCを70分かけて解く人の方がパフォーマンスは高くなります。そのため、常にC問題を必ず解くという意思でCに臨みましょう。

ABCには毎週参加する

これ。すごく大事です。AtCoderにはレート補正システムがあります。これは、初めての人がたまたまいい成績を出してレートが爆上がりyay!ということを防ぐためにあります。この補正をなくすためにはコンテストにたくさん出るしかありません。しかし、ABCは週1回しかありません。一般に補正がなくなるのは10回程度出たときといわれています。そのため、ABCに出られる日は必ず出ましょう。

他コンテストに出るのは...

ほかにアルゴリズム系コンテストといえばARC（AtCoder Regular Contest）とAGC（AtCoder Grand Contest）があります。
これらのコンテストに出たほうがいいかと聞かれたら、基本的に僕は出るべきでないといいます。なぜなら、この二つのコンテストは難易度がかなり高く、さらに数学的考察問題を用する問題が相当多いからです。
例えばARCではこんな問題が出ました。

A - ABA and BAB
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 400 点
問題文
A, B からなる長さ $N$ の文字列 $S$ が与えられます．
あなたは以下の $2$ 種類の操作を好きな順序で $0$ 回以上繰り返すことができます．
S の中で ABA となっている (連続した) 部分を選び，それを A で置き換える．
S の中で BAB となっている (連続した) 部分を選び，それを B で置き換える．
操作後の $S$ としてあり得る文字列の個数を $10^9 +7$ で割ったあまりを求めてください．
制約
$1≤N≤250000$
$S$ は A, B からなる長さ $N$ の文字列
ARC180-Aより

また、AGCではこんな問題が出ました。

A - Shuffle and mod K
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 500 点
問題文
長さ $N$ の整数列 $A=(A_1 ,A_2 ,…,A_N)$ が与えられます。
あなたは $A$ を自由に並び替えることが出来ます。並び替えた後の $\sum_{i=1}^{N−1}((A_{i+1} −A_i )modK$) としてあり得る最大値を求めてください。
ここで、$xmodK$ とは $0≤y<K$ かつ $x−y$ が $K$ の倍数になる整数 $y$ のことを指します。例えば、$−3mod8=5$,$9mod6=3$ となります。
制約
$2≤N≤2×10^5$
$1≤K≤10^9$
$0≤A_i <K$
AGC65-Aより

はい。これで分かる通りARCおよびAGCは灰コーダー向けではありません。
そもそもAGCは緑コーダー以下のレート変化がありません。ARCの難易度は半数近くが緑コーダー以上向けです。そのため参加してモチベが下がるのもあれでしょうし、出ないほうがいいと思っています。

学んだプログラムについて

apg4bのデータ構造

C埋めをやろうと決意したころ、もうapg4bは二章とちょいでいいやと思っていたので、のちに苦労します。基本的に過去問埋めは解説を見ないタイプだったので、データ構造シリーズはよくわからず(setくらいなら知ってたけど)。
後にせっかくだから見てみるかとSTLのコンテナ(3-03)をみてみると、あら驚き。知らないデータ構造がわらわら出てくるじゃないですか。ということで勉強。そのおかげでmapシリーズがスラスラできるようになりました。
基本的にapg4bは1章,2章,3-01~3-03,3-05までは見たほうがいいです。

いろいろなアルゴリズムについて

これはコンテスト・過去問演習で出てきた都度覚えていきました。
二分探索法→ABC353 C Sigma Problem
bit全探索→ABC356 C Keys
フェルマーの小定理とか→ABC357 D 88888888
解で二分探索→ABC341 D Only one of two
etc...

蟻本を読む

dp(動的計画法)が難しすぎて、即挫折しました。
当時dpについて簡単な知識は持っていましたが（ABC040-C「柱柱柱柱柱」くらいなら）、それ以上のことについてはさっぱりなため、一瞬で理解をあきらめました（そのせいで灰コーダー時代はdpアンチを名乗っていたくらいです）。

まずは蟻本(初級編)をやりましょう。注意点として動的計画法という初心者殺し的なアルゴリズムの存在です。こいつは言ってしまえば、RPGのはじまりの街すぐ近くにいる強いレアモンスターみたいな感じなので、この段階では理解できなくても気落ちせずに次に進んじゃっていいと思う。茶色灰色って言っているうちは本当にコスパ悪いので。動的計画法とは漸化式のことなので、こういう問題を解くためにはこういうふうに漸化式を立ててその情報を保存しているんだーくらい理解できてればよいのかなと思います。
AtCoderで灰コーダーから茶コーダーになったので灰色勢に応援するより

よってdpをとにかく何よりも先に理解したいという人はいいですが、基本的にはdpは飛ばした方がいいと思います。(それより後のページに二分探索法とかデータ構造とかいう大切なものはいっぱいあるので)。

入茶までの振り返り

筆者のAtCoder参加前のスペック

・某有名中学校に受験し合格
・得意教科は算数(数え上げ・幾何を除く)
・数学に関しては微妙
・プログラミングについてはPythonでfor文が使える程度(JOI一次試験ギリギリ合格レベル)
こんな風にほんのちょっとくらいならプログラミングの基礎はありましたが、その程度でした。また、あまり数学には触れていなかったので、三角関数とかいう高校数学はちんぷんかんぷんです。

初コンテスト(4/13)

当時はC++erじゃなくてPythonerだったので、最初で最後となるPythonでABC349に参加しました。
当時はlist（C++でいうvector）も知らなかったので、大苦戦。何とか一冠を収めて終了しました。

1冠できたのがすごくうれしかった一方で、B以降が難しすぎた結果萎え落ちした記憶もあります。

パ研入部(4/12)

少し時をさかのぼります。
小学校時代からPythonをほんの少し噛んでいたことや、そもそもそういう職に就きたいという思いがあったので、パ研には即効参戦しました。
パ研の先輩たちがC++をやろうという勧めだったので、Pythonを放っておいてC++の勉強に励みました。
C++なんてこれっぽっちも知らなかったので、AtCoderのコンテンツ「APG4b」で一から勉強しました。

初C++コンテスト　ABC350(4/20)

そしてC++初のABC（350）。A問題で謎のバグを出し、あきらめてBを解きAC。そのままA問題のバグを見つけて何とかACしました。
一応B問題が解けたのでパフォーマンスは151だったのですが、A問題に大苦戦してしまったのが悔しかったという記憶があります（後日、A問題のバグの原因はS=ABC000だと判明した）。
後日、なんで解けなかったのか分析した結果
・実装力不足
・問題への慣れが足りなかった
という結論に帰着しました。
よって、それ以降一生懸命AB埋めに取り組みました。

初の3冠へ　ABC352(5/04)

このころは実装力のためひたすら過去問演習に努めていました。ひたすらAを埋め、Bを埋め、と繰り返していました。
その成果か、ABC352において初の3冠を達成しました。
diffはABC301~ABC362のコンテストにおいて下から二番目の低さでしたが、かなりの速さでのAC。初の茶パフォを獲得しました。

yay!

事故回からの神回　ABC355・ABC356(5/25・6/01)

その後も順調にレートを上げ続けていっいました。
このころになると、C問題も着々と埋め続けていき、成長したもんだなと思いふけっていた頃でした。
しかし、ABC355でやらかしてしまいます。
B問題を読み間違えて3落ちしてしまったうえに、Cも解き方がわからずに終了。ABC352がら入緑するまでの中で唯一の灰パフォ。大やらかしをしてしまい萎えて寝落ちしました。
後日、あまりにも悔しかったがために、全力で過去問を解き、実装力を上げていきました。
そして迎えた6/1。ABC356。そろそろまた三冠をしたいな～と思いながらコンテストに挑みました。この回のC問題は初めてのbit全探索。無理なので飛ばしてDを見てみると、あら何とか解けそうという印象。ということで頑張ってコードを書いてみて提出した結果、なんとAC。
さらにCに戻って一生懸命15回forループを書いてみて、頑張って提出してみたらなんとAC。
しかも驚くことにD問題が緑diff。これまで茶diffをACした過去がなかったのでその二つ上をACするという奇跡。
ということで初4冠・初緑パフォをゲット！
参考：
当時のC
当時のD
地獄の仲間分けをしたC

すごく感動してた。

灰色コーダーkazuppa。最後のコンテスト。ABC358(6/15)

当時のレートは399（仲間たちと悲しみを共有してた）でした。そのため、このコンテストは絶対に落とせない。その思いで勉強をしていました。
bit全探索・順列全探索・簡単なグラフ理論を学び、勝つ準備は万全で挑んでいました。
また勝てるという自信もありました。というのもABC358はCodeQUEEN 2024の予選。一般に予選形式のコンテストは途中から一気に難しくなるという事実があります（ABC288、ABC313はとてもいい例）。タイピング速度・早解きには慣れていたので、勝てる。というわけです。
その予想は無事当たり、A~Dまでは灰diffなのに対し、Eから急に水色diff。Cのbit全探索も学習済みだったので、高速4冠に成功。学校のパ研のレート青以下で2位にもなることができ、かつ初めての色変もでき、とても喜んでいました。
ということで無事に入茶。憧れの色変に成功しました。

当時のAC問(濃い緑はコンテスト内、それ以外はコンテスト外AC)

結論茶コーダーになるために大事だと思うこと

茶コーダーになるためには何が大事か。

①確実に2冠早解きをする

これは大事です。なぜ大事かというと、C・Dがかなり難しいときの保険となるからです。

	2冠最速(パフォ)	2冠最遅(パフォ)	C問題のdiff
ABC362	461	139	521
ABC360	360	283	約800
ABC359	721	89	828
ABC352	221	136	136
ABC350	507	136	394

はい。こんな感じです。
回によっては差は100以下の時もありますが、ひどいときには600以上も差がつきます。そのため、早解きは大事なのです。
個人的には2冠5~20分くらいが理想かなという感じです。

②アルゴリズム・データ構造の知識を深める

アルゴリズム面

全探索(計算量を工夫するタイプのシンプル全探索は必須、できたらbit全探索も)
二分探索法(必須)
累積和(必須)
簡単な再帰関数(できなくてもまだ大きな支障は茶色までならなさそう)
簡単なグラフ理論(幅優先探索、深さ優先探索)(できなくても大きな支障は茶色までならなさそう)

データ構造面

APG4bの3-03(setとmapのみで大丈夫)

個人的には今現在以上のアルゴリズム・データ構造を使いこなせていれば入茶はできると思います。

さて、入茶までの記事はここまでにして、ここからは本編となる入緑までの記事となります。

茶コーダー時代

茶コーダーの間何をしたか。それはただ一つ。
「過去問演習をする」。それだけです。
もちろんそれだけというのは嘘ですが、実際かなりの時間過去問演習をしました。
しかしCより難しい（当然）D問題。

D - New Friends
実行時間制限: 2 sec / メモリ制限: 1024 MB
配点 : 350 点
問題文
$1$ から $N$ の番号がついた $N$ 人のユーザが利用している SNS があります。
この SNS では $2$ 人のユーザが互いに友達になれる機能があります。
友達関係は双方向的です。すなわち、ユーザ X がユーザ Y の友達であるならば、必ずユーザ Y はユーザ X の友達です。
現在 SNS 上には $M$ 組の友達関係が存在し、$i$ 組目の友達関係はユーザ $A_i$ とユーザ $B_i$ からなります。
以下の操作を行える最大の回数を求めてください。
操作：3 人のユーザ X, Y, Z であって、X と Y は友達、Y と Z は友達であり、X と Z は友達でないようなものを選ぶ。X と Z を友達にする。
制約
$2≤N≤2×10^5$
$0≤M≤2×10^5$
$1≤A_i<B_i≤N$
$(A_i ,B_i)$ は相異なる
入力は全て整数である
ABC350-Dより

この問題はただの全探索だと{X,Y,Z}を全て数えないといけないため、計算量が$O(N^3)$となり、確実にTLEしてしまいます。(これを正解するにはunion-findというデータ構造の知識が必要です)。このように、緑コーダーになるためにはさらにいろいろな知識を使わないといけません。
また、解の可能性があるものを全探索するというタイプでも難易度が上がります。

D - AABCC
実行時間制限: 3 sec / メモリ制限: 1024 MB
配点 : 400 点
問題文
$N$ 以下の正整数のうち、 $a<b<c$ なる素数 $a$,$b$,$c$ を用いて $a^2×b×c^2$ と表せるものはいくつありますか?
制約
$N$ は $300≤N≤10^{12}$

これも$\sum_{i=1}^{N}$として全探索し、さらに各$i$について$a^2×b×c^2$であるかの判定をするという方法だと、愚直に調べた場合
・N以下の整数iの全探索→$O(N)$
・ある整数$X$に対するabcの全探索→約$O(X^2)$
・ある整数$X$の素数判定→$O(\sqrt{X})$
少なくとも現実的でないことはわかるでしょう(中段の計算量を誰か教えてください....)。
個人的には、CとDの難易度差はBとCほどではないと思っていますが、それでもD問題はC問題に比べてかなり難しくなっていることがわかります。

入緑までにしたこと

AB埋めについて

まず上のレートに上がるためには、自分と同色の問題は解けるようにする。その意識で過去問埋めをしていきました。
私は、色が変わってまずすべきなのは自分の元色diffの過去問埋めだと思っています。レートのキープには何が必要か。それは自分より下の色を絶対に落とさないという意思だと思っています。そのためにABを埋めるのは僕の中にあったと思います（まあそれよりかは埋まった時の快感を求めていたという方が大きいです）。

CD演習について

これは灰色コーダーにおいても共通することですが、CDはABよりもよっぽど学習効果が大きいです。もちろん基礎がなっていないとだめですが、基礎があるなら絶対にCD埋めをした方がいいと思っています。
当然ですが、CDはABよりも難しい。ですが、その理由はいろいろなアルゴリズムを盛り込んでいるからだと思っています。ならCDが解けるようになったらアルゴリズムが色々見についているということではないでしょうか？
ではどうすればD問題・難しめのCを解けるようになるか、それは過去問を解く。それに尽きる。
そのため私は過去問演習をひたすらしました。
直近のコンテスト(ABC301~360)で入緑のために正解しておきたいCは56問、Dは30問。
つまり半分の確率でD問題を解けるようになれたら入緑可能。そのために、その意識で過去問演習を進めてきました。
また、レートが600程になったとき、「解説を見る」ということを身に着けました。
中学生からしたら数式だらけでちんぷんかんぷんなこともありますが、理解できるものもまた多い。ということで分からなかったらちょくちょく解説を見る癖をつけていきました。

学んだアルゴリズム系について

蟻本

変わらず挫折中です（今見ても難しい...）。
水コーダーになるまでに改めて学ぼうか今検討しているところです。

鉄則本

蟻本の代わりに鉄則本を買いました。
dpや二分探索法、繰り返し二乗法などをわかりやすく学べて、今も愛用しています(dpめっちゃわかりやすい)。
まだ買っていない方、dpを完全攻略したいという方はぜひ買ってみることをお勧めします。

アルゴ式

友人の勧めにより始めました。
個人的な印象としてはグラフ理論がとにかくわかりやすい。よくわからなかったグラフ系をここまで理解できるようになったので感謝です。

入緑に必要だと思うこと

入緑するために必要だと思うことをまとめようと思います。

3冠早解きが常にできるようにする

必ず3冠ができるようにしましょう。
「お前何言ってんの？難しいC4つほどあるってさっき言ってたやん。」
3冠早解きを語るとこういう意見が出ると思います。しかし、実際この4つの回はDが比較的やさしめなため、Cを飛ばしでDに挑むという判断ができれば3冠は狙えた回だったと思っています(ABC347はそれでもCが難しかったですが、modの概念がわかっていれば3冠は狙えていたと思っています)。
もちろんどのような回でも早解きは大事です。

	3冠最速	3冠最遅	Dのdiff
ABC361	1017	566	1202
ABC357	933	429	970
ABC343	547	317	422

(3冠とはABC3問のみ正解した人のことです)。
はい。やっぱりいかに早く解くかによってレートが大きく変わっていきます（他の色も同様）。
早解きはタイピングの速さとその問題への慣れによって決まると思っているので、そのためにも早解きは大事でしょう。

アルゴリズム・データ構造の知識

緑になるための必要なアルゴリズム・データ構造は入茶の時に比べ増える。でも大しては増えない。そう僕は思っています。

アルゴリズム


bit全探索・順列全探索	再帰関数（メモ化再帰も）
尺取り法	二分探索法
再帰関数（メモ化再帰も）	dp(動的計画法)
累積和（imosu法も）	幅優先探索・深さ優先探索・ダイクストラ法

データ構造


set	map
queue	priority_queue
stack	union_find

個人的にはこのくらいでも十分足りるのかな～と思っています。
これらが使いこなせれば緑も現実味を帯びてくると思います。

実装力について

基本的にABCは
・いろいろなデータ構造を組み合わせて～
・計算量を工夫して～

というのが多いです。
しかし、たまに実装が重たい問題というものが来るのです。
個人的にそう思うのは、ABC359-CやABC275-Cなどです。
これらの問題はどうすれば解けるようになるか。これも慣れだと思っています。実際に、A問題の早解きは緑以上ならある程度いろいろなレートが上位に君臨していますが、これらの回（特にABC359-C）はかなり上位レートの人が位置しているように思えます。
これは、実装が重い問題を多く解いてきているためだと思っています。これらが早く解けるようになれば、実装力がかなり身についてきたというふうに言えるでしょう。

過去問演習について

おそらく上記の条件を満たすために一番大事だと思っていること。それが過去問演習です。
今、ABCだけでも合計2172問あります。
これだけの問題を解かずしてほかにどういう精進の仕方があるのだろうか。
そういう風に私は考えています。過去問を解けば確実に力が身につくため、過去問演習を私は強く推奨しています。
やり方としては、AtCoder Problemsで解いてない過去問を解く。それが最適解なのではないかなと。
過去問を解いていけばいずれ同じような問題が出た時に対処できるようになる。
そのため、なかなかレートが上がらない....という人はぜひ過去問演習をやりましょう。

入緑までの道のり

最後に、僕が茶色コーダーだったときの振り返りを書こうと思います。

ABC359

僕の初めての茶色コーダーコンテストです。
CがあのTile Ditance 2。
叫びそうになりながらなんとか場合分けをしてボロボロ2落ちのAC。
そのままEが解けそうな気がしたけど、入出力例3でこの問題の難しさを実感。ギブ。
実装力の大切さを改めて思い知らされました。

ARC180

この回は茶色コンテストで3番目に焦った回です。
たまたまこの週。土曜がARCでした。
ARCは1冠しないと確実に負ける試合なので直前まで参加登録をするか悩んでいました。
で結果「まあどうせいけるだろww」という軽いノリで挑戦。
→Aを見た瞬間叫びました。（自業自得）
ひたすら紙に書きながら法則性を考え出した結果、なんとか50分かけて正解できました。
始まって10分ほどはひたすら後悔していましたが何とか1冠できてよかったです。

ABC360

多分茶色コーダーの頃の5回のコンテストで2番目に焦りました。
というのも
・Aで味噌汁をM(Miso soup)ではなくS(Soup)だと勘違いして1WA。
・Bで難読すぎたあまり1WA
・Cで問題文を読み間違え10分のタイムロス
はい。これで分かった通りA~Cで大やらかし。この段階で27分弱経っていました。降格するのではないかとびくびく震えてました。
しかし、その後何とかDをACさせたうえ、全体的にむずかしめだったこともあってか、まあまあいい順位で終わるという何ともつまりのない結果でした。

何とかセーフ....

ABC361

この回の直前、仲間たちとどんな問題が出るか話し合っていました。
・1919=361。19はbit全探索でも間に合うからbit全探索が出るはず。
・1919=361。19は素数だからそういう数字を利用した整数系全探索が出るはず。
結果、bit全探索も整数系全探索も出ないことはコンテストが始まるまで誰も知らず...
まあBとかCとかめんどくさいなーと思いながら20分でAC。
ここからが後日ミスだと思っていました。
・F解けそうだな～→無理だった
・E解けそうだな～→無理だった
・D解けそうだな～→無理だった
・無理だしお風呂入るか
・出る
・もういいやD愚直解だすか
・まあ愚直に行けるならDは幅優先探索で行ける？→AC
この段階で85分。
バラバラに生半分に解いたのが明らかなミスでした。
しかしDが水diff。なんとか緑パフォを出して緑リーチになりました。

リーチ...!

ABC362

はい。結果から言うとこの回で入緑しました。
ひたすら緊張しながらこのコンテストに臨みました。
スタート直後、ハイダッシュでABDをAC。2ペナをしながらなんとかCもAC。
しかし、Eがdpで行けるとわかりながらも解けず...
自分の順位がどんどん落ちていくことに焦りながらも結果解き方がわからず終了。
結果は3240位。直近にしてはかなり悪い結果を残してしまいました...
レートがどうなったか気になって待つものの耐え切れず寝落ち...
緊張しながらパソコンを開き、結果の確認。
入緑したとわかった瞬間とても喜びました。
「いやぁ、この瞬間が競プロやってて一番うれしい時だよな。」そう喜びをかみしめていました。
仲間も一人入茶し、この回が最高のコンテストなのではなかったのではないかなと思っています。

茶、さよなら