【色変記事】実務未経験がAtCoderで水色になるまで

2021/08/21に行われたABCでパフォーマンス1623をとって、入水しました。

ギリギリ水色になれた感じなので次回のABCでまた入緑するかもしれませんが。

当日のコンテスト振り返り

A〜Eまでの5完でした。
E問題は一週間前に履修したばかりのbitDPを使う問題でしたが、精進の成果が出て良かったです。
入水するかどうかの微妙なパフォーマンスだったので、コンテスト終了までドキドキしながら順位表を眺めていました。

自己紹介

AtCoderのアカウント

高卒で非IT系勤務の社会人です。ITエンジニア目指して1年半ぐらい独学してます。
WebアプリとかiOSアプリとか作りました。応用情報、基本情報とったりもしました。

↓作ったアプリの紹介記事
独学半年の実務未経験がRails＋Nuxt.jsでSPA作ったので見て欲しい
独学でAppStoreにアプリを公開するまで

Twitterでフォローしている人がAtCoderを始めているのを見て、コンテストに参加することに決めました。
もともとPaizaでBランクの問題が解けないぐらいの実力しかなかったため、実装力を高めたいと考えていた、という理由もあります。

初参加から今までの振り返り

コンテスト初参加

2021/01/10に行われたABC188が初参加でした。
ABの2完で初めてついたレーティングが4と、かなり苦労していたのが伺えます。
この回のC問題は灰diff前半と簡単な部類だったはずなんですが、それすら解けないぐらいの実力しかありませんでした。

茶色になるまで

3回目ぐらいまではRubyを使って参加していたのですが、問題の解説記事などはC++を使って書かれていることが多かったため、C++を勉強することにしました。
AtCoder公式のC++入門コンテンツである、APG4bにお世話になりました。

C++の勉強と並行して、問題を解くことになれるためにA、B問題をたくさん解きました。
最初はC問題が全く解けなかったのですが、問題形式になれたためなのか解けるようになり始めていました。

↓AtCoder Problemsのグラフです。
解いた問題の量と難易度がわかります。1月後半ごろにすごい量の問題を解いていることがわかります。

茶色になるまでにしたこと

• ABCのA、B問題を早く解けるようになる
• C問題を解けるようになる
• けんちょん本を読み始める

緑になるまで

下の画像はAtCoder Problemsで見れるヒートマップです。
その日に解いた問題の最高難易度を元に色が変化します。

見てわかる通り、緑diffを中心に問題を解いていました。
この頃にはコンテスト本番で緑diffを解くのが安定するようになり、緑後半のパフォーマンスが出せるようになっていました。

緑になるまでにしたこと

• 緑diffの過去問を埋める
• アルゴリズムを勉強する
  • BFS、 DFS、ダイクストラなどのグラフアルゴリズム
  • 約数列挙、素因数分解などの整数系のアルゴリズム
  • UnionFindなどのデータ構造
  • 動的計画法、bit全探索

アルゴリズムは他にも勉強した気がしますが、よく覚えてないです。

水色になるまで

停滞してる時期もあります。
ヒートマップ見るとわかりますが、全然精進できていません。
この時期は高校数学の復習をしたりしていて、問題を解く時間はあまり取れていませんでした。
おかげで3ヶ月ぐらいレートがあまり変動しませんでした。
実力が上がらないだけでなく、緑diffの問題も解けなくなっていたので、少し問題解く力も落ちていたかもしれません。

ここ３週間ぐらいは週末に水diffを解くようにしているので、レートが伸び始めて来ました。

6月末からはてなブログで問題の解法記事の執筆を始めました。
自分が過去解いた問題を復習しやすくする、解法を整理する、という目的で書いています。

水色になるまでに覚えたこと

• 累積和、しゃくとり法、imos法
• 二分探索
• bit全探索
• BFS、DFS、UnionFind、ダイクストラ法、ワーシャルフロイド法
• 動的計画法、メモ化再帰、桁DP、bitDP
• セグメント木、遅延セグメント木
• 高速な約数列挙,素因数分解、繰り返し二乗法
• modint

名前の付いているアルゴリズム、データ構造を適当に列挙してみました。
典型的な考察手法とか名前の付いていないテクニックも覚えたりしているので、実際にはもっと勉強しています。

これからについて

青色も目指したいと考えています。
水diffになる問題を60分以内に解くことができれば、青パフォ出るので不可能ではないと思っています。

しばらくは水diffを安定して解くことを目指したいと考えています。
青パフォ２回だしてなんとか入水できましたが、水パフォ安定はできていないので、それができないとまた緑に戻りそうだなと思っています。

AtCoderを始めて良かったこと

・コードの計算量が分かり、効率的なアルゴリズムを選択できるようになった。
・複雑な実装を素早くできるようになった。
・学習のために他の人がコードをよく読むようになったので、コードを読んで理解するスピードが速くなった。
・考察能力が上がり、複雑な問題を解決する方法を学んだ。

最後に

下の画像は自分の精進グラフです。
精進している時期は伸びてしてない時期は停滞しています。
やはりレートを伸ばすには精進が一番です！
皆さん精進頑張って参りましょう！