【色変記事】AtCoder緑色になりました【Ruby】

AtCoder緑色になりました

AtCoder という競技プログラミングに参加続けて1年と半年ほど。長い道のりでしたがこの度レートが800を超えて緑色コーダーになりました。
この記事では自分がどのように勉強し、どのように解き緑色になれたか紹介していきます。
茶色になった際の色変記事も書いていますので参考になれば見ていってください！
緑色なった時のレートは以下になります。

ちなみに自分のアカウントはこちらになります。

AtCoderとは

AtCoder とは日本最大級の競技プログラミングを開催しているサービスです。
コンテスト内容は時間内に指定された問題を解くものでアルゴリズムに関する能力が問われます。

色変

タイトルにもある色変とはレーティングが一定の閾値を超えた時にレートの色が変わることを言います。色が変わることで1つランクが上がったと考えると分かりやすいと思います。
AtCoder ではそのコンテストで自分が発揮したパフォーマンスに応じてレートが上がっていきます。
レーティングについては AtCoder公式情報サイトAtCoderInfoにて記載されています
Algorithm部門のレーティングと業務における期待できる活躍

AtCoder の社長である高橋直大さんのブログでは以下のように説明されてました。
※情報としては古いですが個人的にわかりやすいので記載しています

レーティング	色	概要
2800-	赤	もうなんか世界大会に招待されたりする
2400-2799	橙	複雑な検索サービスや研究開発でないと活かせれないレベル
2000-2399	黄	化け物。競プロの問題を解く機械だと思っておけば良い
1600-1999	青	一部上場企業で一人もいないことが結構ある
1200-1599	水	基礎的なアルゴリズム処理能力については疑いようがないレベル
800-1199	緑	大抵の企業でアルゴリズム力は十分 他社評価サイトなら高評価
400-799	茶	学生なら優秀だがエンジニアなら物足りない
1-399	灰	コーディング意欲は保証できる

緑色になるためにやってきたこと、必要なこと

ある程度のアルゴリズムは解けるようにしておく

緑パフォーマンスを出すためにはD問題を解く必要があります。
その中でもよく出るモノを列挙していきます

• 動的計画法(DP)
• 深さ優先探索または幅優先探索でグラフの探索
• Union-Findによる連結判定
• 累積和
• 二分探索
• 答えで二分探索
• 素数判定、列挙
• クエリ問題

この中でも特に D 問題でよく見かけるし解けるようになると有利なのが DP です。
自分が見たイメージですが DP は解ける人が少ない印象です。
しかし、解けないほど難しいわけではありません。一度解いてしまえばほかの DP 問題を見た時に DP っぽいと判別できますし意外と解けます。
お勧めの問題を置いておきます。D - Shift vs. CapsLock
初めて解いたDPの問題ということもあり思い出深いのですが比較的解きやすいと思います。
DPで大事なのは行う行動ではなく行った後に得られる状態を保持しておくことです。この問題であれば CapsLock キーのランプが ON か OFF かですね。

他は C 問題でも見かけるし割愛します。しかし、早く解くためにも慣れておくことは良いと思いますので考えなくとも手が動くようにはしておきましょう。

振り返り会

茶色になる際にも書きましたが先輩コーダー(水色)との振り返り会は自分の中で最も成長させてくれたと思います。
どうやって解けば良いのか、また便利なメソッドを教わり次に活かせるようにしました。
その際、解けなかった問題はちゃんと解いておくのが大事ですね。

秘伝のタレを作る

これはずっとやっていることです。
自分は Ruby で解いていたのですが問題に対し便利なメソッドがたくさんあります。他にも振り返り会をした時に便利なメソッドを教えてもらったので、活かせるように hiden.rb（秘伝のタレ）を作り継ぎ足していきました。
また使いそうなメソッドを自分で作るのもありですね
例えば数字の判定や累積和の作成、AtCoder でよく見る二次元配列の作成もメソッド化しておくとかなり時短になります
使う機会は多いので自分用に用意しておくのをお勧めします。

C問題までの早解き

緑色コーダーになるためには ABC の C 問題までは平均して 30 分以内には解いておきたいです。
緑色コーダーを目指す段階だと D 問題を解けないことも結構あります。
その際、如何ににパフォーマンスを上げるかといえば早解きです。

ARCのRatedは自信のある時に

灰色コーダーであれば AtCoder Regular Contest(ARC) に参加することもいいと思いますが茶色コーダーの参加するARCに旨みはありません。ARC の A 問題は ABC の C 問題相当の難易度です。解けなかった場合はパフォーマンスが200程度しか出ませんし、解けたとしても遅いとそこまでパフォーマンスが出ません。
参加するならUnRatedにしましょう！

緑色になった感想

緑になるラスト5回はすべてパフォーマンスが800を超えててこのまま順調に緑になれ！沼るな！ってやったらなれたので一安心です。
今後はRubyをやめてコンパイル言語を使用して参加したいと思ってます。(やっぱりRubyは遅いので)
さすがに水色を目指すのは実力的にも無理かなと感じていますが気長にAtCoderは続けていこうと思います。