atcoderで青色になった話

# はじめに


'21年末あたりから競プロに本腰を入れて取り組み始めまして、目標にしていた青色になったので、区切りとしてポエム（普通のほう）を書いておこうと思います。


# バックグラウンド

非情報系学部の情報系研究室修士卒の社会人です。何とも言えないですね。
プログラミング能力という観点で言えば、学生時代は講義数や周りにプログラミングができる学生が限られていて質のいい情報に出会う機会がなかったこともあり、研究用に必要なコードをそれっぽく書く程度の能力しか身に着いていませんでした。


# 競技プログラミングとの出会いと始めるまで


出会いは学生時代に遡ります。


実は、code thanks festivalへのオンサイト参加を目的に1回だけatcoderをやりました（お薬みたいですね）。アルゴ・データ構造をまともに勉強しておらず試験管灰色相当の問題しか解けませんでしたが、まだ参加人数が少なかったこともあり現地に行くことが出来ました。（おそらくchokudai氏を直接見ていた気がします。ただ、その時の認識は「チョクダイさん？なんか界隈で有名な人なのかな」という程度でした。）

ただぶっちゃけると、「オーバーフローとか重箱の隅つつくような問題解くなんて競プロダルいな」という印象だったと記憶しています。そして、その1回以降続けることはありませんでした。



そして時は流れ、

社会人になってもプログラミング自体はとても好きで、ちょこちょこコードを書く日々が続きます。
しかし、雰囲気でしかソフトウェアをやってきていなかった私は、
「なんかこの書き方良くない気がするな」
という感覚がずっと燻っていました。

一方で、ソフト専業の環境でもなく、基本的に自分用にしかコードを書かないこともあって、
ずるずるとその状況が続いていました。


そんな折、この記事に出会います。

https://mixi-developers.mixi.co.jp/動的計画法によるdvdのディスク分割の改善-438875f65528

普段お世話になっているサービスということもあって、「すごいな、こんな方法あるんだな」ととても感動したのを覚えています。
同時に「なんかよくない書き方」に対する処方箋はこれなんじゃないか、と直観的に感じ取りました。
そして、競技プログラミングの文字をみて、よしやるか、と決めました。

そのあとは元ネトゲ廃人（「真輝の術書売ります　ささよろ」とシャウトしたり「mid or top」とか言ってクソfeedしたりしてました）の血がatcoderというネトゲと大変にマッチしまして、余暇時間をほとんどここにぶち込むことになりました。


# やったこと

## 統計情報

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2522928/d7d0c951-13ab-ba79-bdce-6ad288327068.png)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2522928/376525e6-b1d2-44f4-3329-64159be72acb.png)

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2522928/c53c2b4b-a6a2-b991-9641-e6e0099c0b94.png)
※はるか昔のsubmissionのせいでめっちゃ見づらいことになっています

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2522928/5f39b05c-7361-5030-e12f-efb91a57715d.png)


## 活動の方針


先人たちが言っていることと基本筋は変わりません。

### 網羅的・体系的に知識をつける

私の場合は、まずけんちょん氏の入門記事をやってけんちょん本を一冊読んだ後、典型90問でほどほどのところまで解きました。

https://www.amazon.co.jp/%E5%95%8F%E9%A1%8C%E8%A7%A3%E6%B1%BA%E5%8A%9B%E3%82%92%E9%8D%9B%E3%81%88%E3%82%8B-%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E3%81%A8%E3%83%87%E3%83%BC%E3%82%BF%E6%A7%8B%E9%80%A0-KS%E6%83%85%E5%A0%B1%E7%A7%91%E5%AD%A6%E5%B0%82%E9%96%80%E6%9B%B8-%E5%A4%A7%E6%A7%BB-%E5%85%BC%E8%B3%87/dp/4065128447

https://atcoder.jp/contests/typical90

まずこれらをやることで、競プロにおいてどういう問題と向き合うことになるかよく分かります。

競プロはABC-C~Dあたりの計算量と減らす工夫が出始めるあたりから一気に面白くなると思うので、
とりまそのための知識あたりまでは頭に入れるといいと思います。

今だとオンラインジャッジが充実している鉄則本がいいのかなと思います。
フルカラーでとても分かりやすいです。

https://www.amazon.co.jp/%E7%AB%B6%E6%8A%80%E3%83%97%E3%83%AD%E3%82%B0%E3%83%A9%E3%83%9F%E3%83%B3%E3%82%B0%E3%81%AE%E9%89%84%E5%89%87-%E3%82%A2%E3%83%AB%E3%82%B4%E3%83%AA%E3%82%BA%E3%83%A0%E5%8A%9B%E3%81%A8%E6%80%9D%E8%80%83%E5%8A%9B%E3%82%92%E9%AB%98%E3%82%81%E3%82%8B77%E3%81%AE%E6%8A%80%E8%A1%93-Compass-Books%E3%82%B7%E3%83%AA%E3%83%BC%E3%82%BA-%E7%B1%B3%E7%94%B0/dp/483997750X/ref=sr_1_1?crid=2WIR8UB52DFAH&keywords=atcoder+%E9%89%84%E5%89%87&qid=1665327340&sprefix=atcoder%2Caps%2C620&sr=8-1

ただまあ、データ構造・アルゴリズムという意味では緑あたりから今まであんまり必要なものが増えた感じはしてなくて、
書籍1冊分の知識を入れたらあとは実践あるのみという気はします。


### 自分の色のdiffを解く

という訳で、青になるまでに緑diff埋め＋水diff埋め（試験管除く）をしました。

さんざん言われていることですが、ある色の問題はその色の人々が50%解ける問題です。
これが全部解けたら次の色になれます。
灰色を除いて各色高々300問ぐらいしかないので、自分の色のdiffを全部解きました。

### コンテストに出る

本番が何より面白いので、常時rated一択です。
もちろんそれだけではなく、レーティングシステム的にパフォーマンスに対して上昇量が限られるので、なるべく出た方がいいのと、
本番でめっちゃ頭を回した問題は、解けるにしろ解けないにしろ、学習効果が高く次に繋がります。（復習はもちろんいります）


## 過去問の解き方

さて、少なくとも水diffまでで高度な考察が必要な問題は限られていて、
典型的なアルゴやデータ構造、考察テクニックがせいぜい2つぐらい組み合わさっている程度の肌感覚です。

とすると、その時点でものにできていない典型テクニックをどれだけ学べるか、というのが過去問を解く目的になります。

### 解説ACする

上記の通り、問題を解けない時は典型のアプローチを知らない・またはものにできていないので、
適当な時間を決めて切り上げていました。
目安の時間は[E8氏の記事](https://qiita.com/e869120/items/eb50fdaece12be418faa#2-4-3-%E9%81%8E%E5%8E%BB%E5%95%8F%E3%81%AF%E4%BD%95%E5%88%86%E3%81%A7%E8%A7%A3%E8%AA%AC%E3%82%92%E8%A6%8B%E3%82%8C%E3%81%B0%E3%82%88%E3%81%84%E3%81%8B)を参考にしました。


### デバッグを諦めて写経しない

上記と相反するかもしれませんが、デバッグ能力はデバッグすることでしか見につかないと考えています。
なんというか、これは理屈じゃないです。
これは言われて覚えるものじゃなくて、血反吐を履いてWAを取り除く事でしか臭いがするところが感じとれません。
ただ、手詰まりになるケースもちょいちょいあるので、どうしようもない時はdropboxに上がっているテストケースを参照したり、twitterで聞いてみたりしていました。

### 複数の解法を把握する

1つの問題に複数の解説がある時は、一通り目を通していました。
自力ACできた場合でも、自分が思いつけなかった解法の引き出しが増えて良かったです。

### 自力ACできた問題は人の提出を見る

自力ACできたとき、すごい気持ちいいです。これぞ競プロです。

ただ、過去問ではそれ以上の価値を生みません。
その問題を解くことで使った時間は単に空費された事になります。

それだともったいないので、ACできた後「よりうまく解く方法はないか」を探すようにしていました。
具体的にはatcoder上の全ての提出で「コード長が短い順」「実行時間が短い順」でソートし、
いくつかの提出を参考にしながら、自力ACしたコードをブラッシュアップする、といった具合です。
結果としてこんな提出になります。
![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2522928/b2856e2d-3675-77e2-0825-be53754b2528.png)


atcoderのすごいところだと思うんですが、
同じ問題に対して最大何万もの解き方が一つのところに集まっているわけです。
これは強力な情報です。活用しない手はありません。

コード長が短い実装からは、バグの少ない実装を学べます。
大変直観的な話で恐縮ですが、コード全体のバグ混入率は、
人固有のうっかり率とコード長に依存していると考えています。

うっかり率は残念ながら改善できません。でもコード長は減らせます。
人のコードにはたくさんの素晴らしいアイデアや知らなかったライブラリが転がっています。


実行時間が短い実装からは、定数倍TLEと戦う術を学べます。
緑diff後半あたりから、Python/pypyにおいて「計算オーダー的にOKだけどTLEになる」としばしば向き合うことになります。

ただ、原因はたいてい自分の実装が悪いだけで、早い人のコードは制限時間から一桁少ない、ということがままあります。
解けた場合でも制限時間ギリギリでひやひやした場合は見直すケースが多いです。

この辺をすることで、自分の色以下の問題の安定化であったり、
崖回でのレート上昇につながったのかな、と思っています。


# おわりに

![image.png](https://qiita-image-store.s3.ap-northeast-1.amazonaws.com/0/2522928/e6140124-d2bc-782f-bfdb-1ff665202fd9.png)

ここから入れる保険ってありますか？