はじめに
AtCoderを始めてもうすぐ半年&ちょうど前回のABC338にて入茶を達成したので憧れの色変記事を書きます！
自己紹介
- 新卒3年目のエンジニア
- 大学は国立理系
- 業務では競プロ弱小言語のtypescriptを主に書いています
- AtCoderは職場の後輩に教えてもらって始めました
茶色レートの実力ってどのくらい?
AtCoder公式ホームページのAlgorithm部門のレーティングと業務における期待できる活躍からの引用です。結構嬉しい事が書いてありますね
AtCoderにおける分布(2023/11/20現在)
実レーティング分布： 上位28.462%
内部レーティング分布： 上位45.928%
期待できる能力
コーディングへの安心感がある程度持てます。学生や派遣社員などが茶色のレーティングを持っていたら、とても喜ばしいです。
基礎的なアルゴリズムへの理解があります。典型的な処理であれば、動的計画法、二分探索などのメジャーなアルゴリズムを適用することが出来ます。一方、少し典型から外れてしまうとまだ解くことが出来ません。
競技者としては、多くの参加者がまず目指すべきラインはここでしょう。数学的素養がそれなりにあり、しっかりと練習すれば到達可能な水準です。逆に言えば、才能や素養が十分にあるか、競技者としてしっかり取り組んだかのどちらかを必ず満たしているのがこの色です。
入茶までにやったこと
C++入門 AtCoder Programming Guide for beginners (APG4b)
使い慣れたtypescriptが実行速度的に競プロに不向きなことは分かっていたので、競プロ界隈で最もポピュラーなC++の勉強から始めました。C++は完全未経験だったので公式がC++のチュートリアルを用意してくださっていて本当に助かりました。
AtCoder に登録したら次にやること ～ これだけ解けば十分闘える！過去問精選 10 問 ～
C++に慣れたら、次は競プロの問題形式やプラットフォームに慣れようということで上記の記事に載っている10問を解きました。「これだけ解けば十分闘える」というのは本当で、これを解いた後はAtCoder参加中に何にもとっかかりが無くて立ち往生するような事は無くなりました。
これから始めようという方にはとてもおすすめの教材です。
競技プログラミングの鉄則第3章まで
競技プログラマー向けに大会で有用なアルゴリズムを網羅的に解説している本です。
私は
- アルゴリズムと計算量
- 累積和
- 二分探索
の3章までしか読んでいませんが、入茶するだけなら3章までで十分でした。
可能な限り毎週のコンテスト参加
平日は仕事が忙しくてなかなか精進する時間が取れない私にとってコンテスト参加が一番の精進になりました。
初心者ボーナスでぐんぐん伸びる成績がモチベーションになりました。
入茶する上で役に立った知識・アルゴリズム
TLEになる計算回数の目安
C++では計算回数が10の9乗を超えるとTLE(実行制限時間超過)で不正解となります。
このことを知っておくと、問題の制約から全探索で解ける問題なのか、何かしら工夫して計算量を削減しないと解けない問題なのか判断することができます。
累積和
累積和を知っていたおかげで解けた問題はかなり多かったです。
実装は簡単なのに使えると解ける問題が一気に増えるため、初心者競技プログラマーはまず累積和を勉強すると良いと思います。
自分のタイプ
自分が同じレート帯の中で「多く解くタイプ」であるか「早く解くタイプ」であるかを判定してくれるAtCoder Type Checkerというツールを有志の方が公開してくださっています。これによると私は「かなり多く解くタイプ」のようです。
自分のタイプを知っておくと、下記のように効率良くレートを上げるための対策を行う事ができます。
- 多く解くタイプ=比較的高難度の問題も解けるが、解答スピードが遅い
⇨早解きができる工夫をするとレートが上がりやすい - 早く解くタイプ=比較的解答スピードが速いが、高難度の問題は解けない
⇨より難易度が高い問題も解けるようになるとレートが上がりやすい
AtCoderを始めて良かったこと
楽しみが増えた
まず第一に競技プログラミングは単純に楽しいです。始めるきっかけをくれたN君ありがとう。
コンテストへの参加の楽しみ、レートや順位が上がる楽しみ、新しいアルゴリズムに触れる楽しみがあります。
実務にも役立つ
私は普段フロントエンドエンジニアをしているので、業務で複雑なアルゴリズムを実装したり計算量の削減を求められたりはしないです。そのため、AtCoderを介して知ったアルゴリズムが直接業務に役立つことはありませんでした。
しかし、デバッグの速さだったり、コードの理解力、新しい言語やフレームワーク、ライブラリにキャッチアップする能力には成長を感じています。
今後の目標
今後の目標としては、今年中に入水を目指してやっていきたいです。
最近サボっている鉄則本を再開します