お盆は地元に帰省していたんですが、頻繁に会って遊ぶような友達はいないし、テレビ見ないし、平日は仕事があっても夜が暇という状況に悩んでました。
すると、おぼろげながら浮かんできたんです。
「AtCoderやってみるか」
なぜこう思ったか、多分何かしらのきっかけがあったんですが覚えてません。
実はAtCoderとか競プロというものにはこれまでそんなに興味はなくて、むしろ少しマイナスに思ってました。
本業のWEB開発だと競プロはそこまで役に立たないとよく聞いてましたし（レベルの高い企業はコーディング面接とかに活かせそうですが）、AtCoderにランクシステムがあって、高いランクを目指すこと自体は楽しそうだと思いつつも、週１のコンテストに出場しないといけないのが面倒だったのもあります。
1回だけ、同級生から「君AtCoderやってみなよ。C問題解けるの？」と誘われてAtCoder Beginner Contest （ABC）に参加したことがありましたが、その後は続きませんでした（ちなみに解けたのはA,B問題のみでした）。
ただ、何はともあれ今回興味が湧いてきたので、趣味として、または時間潰しとして、取り組んでみることにしました。
早速、土曜夜のABCに参加してみました。
競プロだとC++がメジャーなようですが、個人的にはPythonが馴染んでたのでPythonでの挑戦です。
時間ギリギリでA,B,C問題を正解することができました（３完というらしい）。
とりあえずCまで解ければいいだろうと考えてたので、気分上場でした。
D問題も少し考えてみましたが、全くわからず。
コンテスト終了後に解説みてみると、どうやら動的計画法というものを使うらしいです。そういえば大学の講義で聞いたことがあります。選択制の科目で、自分は1回目だけお試しで受講してから結局履修しなかったので、内容はよく知りませんでした。
解説とコードサンプルは思ったよりも短くまとまっていて、「ちゃんとシンプルに解けるんだな」と思いました。E問題以上はちゃんとみてないのでわからないですけどね
この勢いで本を買ってアルゴリズムの知識をつけよう。
以前YouTubeとかで動画を見てたのもあり、問題解決のための「アルゴリズム×数学」が基礎からしっかり身につく本が欲しくなったのですが、地元が田舎すぎてどの本屋にもこの本が置いてません。
自分の悪いところで、買うと決めたものが手に入るまで1日すら待つのが辛いので（通販に向いてないな）、いつもは紙の書籍を買うとこですがKindleを買うことにしました。
Kindleだと買いっぱなしで読まなくなることが多いのでそれだけ不安でした。この記事を書いてるのは購入２週間後ですが、今のところ半分以上読め進められてます。これからも、わからないことがあったら調べる使い方ができると思います。
大阪は思い立ったときにジュンク堂に買いに行けるのがやはりいいですね。
さて、大阪に帰ったあと、上の本を読み終わる前にジュンク堂で別の本を買ってしまいました。
競技プログラミングの鉄則 ~アルゴリズム力と思考力を高める77の技術~
Amazonでこの本も評価が高かったのと、立ち読みしてみて図解がわかりやすく、内容の質も高そうと感じたためです。
買ったあと気づきましたが、これらの本って実は同じ著者さんなんですね。競プロに手を出す初心者が情報収集するときは必ずと言っていいほどこの著者さんが出てくるのでないでしょうか。
レッドコーダーが教える、競プロ・AtCoder上達のガイドライン【初級編：競プロを始めよう】というQiita記事もこの方が買いています。
両方ともまだ全部読み切ってないですが、少しずつ読み進めてます。
まだ本をぱらぱらと拾い読みしたくらいの状態で、次のABCへ挑戦です。
前回はPythonでやってましたが、学習効率を上げるため、C++に移行を決意しました。競プロに限れば、覚えることはそこまで多くないはず。。
C言語は高専で学んでたので、C++も多少はいけるやろということで今回のコンテストから使い始めることにしました。（フラグ）
Windows・MacでのC++環境構築と、IDEでの設定までなんとか完了してます。
結果としては、A,B問題までの完答でした。
C++での文字列（string型）の文法やライブラリがわかっておらず、デバッグが間に合わなくてコンテスト終了の20分後にACしました。
問題の解き方自体はわかっていたので、Pythonでやっていたら間に合ってたかもと考えるとちょっと悔しいですが、この程度の単純な知識不足なら、継続してればすぐに解消するだろうということで「来週は絶対3完するぞ」と逆にモチベが上がりました👍
現在、分野別 初中級者が解くべき過去問精選 100 問を解いています。
上で買った２冊の本を参照しながらやってますが、いい感じに楽しいです。
とりあえず順番に解き、順列全探索の途中の問題まできています。
これまで自力で解けなかったのが1つあって、7番目の情報オリンピックの「最古の遺跡」というやつです。正方形を探索する問題ですが、自分のやり方だとどうしても時間切れ（TLE）となりました。正方形チェックのアルゴリズムの計算量が多かったのが原因だと思ってます。それまで全問順調にできていて自力で解きたかったので、3日以上かけましたがギブアップしました。。
とはいえ問題を解く過程で計算量を見積もるという習慣（時間計算量のオーダーを意識するとか）がついたのは自分でも大きく成長したなと感じます。
まだ、具体的に何回ループまでなら何秒で終わるという感覚がほとんどないので、その辺はこれから身につけていきたいですね。（そのまえに継続できればだけど！）
まあどこかに目安がまとまってるんでしょうけどね。
https://atcoder.jp/contests/apg4b/tasks/APG4b_cb?lang=ja
AtCoderのジャッジでは1秒あたり10^8回程度の計算が可能です。不正解だった場合TLEとなります。
さあ、前週はC++自体に手こずってBまでしか解けなかったので、1週間の成果を発揮するぞと気合いを入れて臨みました。
A,Bは少し時間かかりながらも18分で終わり、C問題を見ます。グラフを同型にするにはどうするかという問題でした。探索をすればよさそうですが、グラフの問題自体には慣れてないので、一旦D問題ものぞいてみました。
D問題は数直線にデータを配置する問題で、まだ解けそうだと感じたのでD問題から解くことにします。
とりあえず真面目に計算して答えを出すコードを提出しましたが、TLE。そのあと、本で紹介されていた累積和のことを思い出し、なるほど！となってそこからはずっとスムーズに進みました（実際に累積話の問題を解いたことがなかった）。setのupper_bound・lower_boundのイテレーターがよくわかってなくて少し苦戦しましたが、なんとか時間内にD問題クリア。
残り10分を切っていたのでC問題は問題理解までで時間切れでした。
とりあえず3問は完答し、現時点での実力は出しきれたと思います。
ランクは152に上がりました。
AtCoderやってみようと思い立ってから２週間が経ちました。
平日も含めてほぼ毎日問題を解くかアルゴリズム本を読むかしてますが、今の段階でメリットに感じていることをまとめてみます。
- 問題を解く過程で計算量を見積もるという習慣（時間計算量のオーダーを意識するとか）がついた。
- 上でも同じこと書いてます。業務でもパフォーマンスを考えるときに役に立つ、重要なスキルだと思ってます。
- C++の基本文法や標準ライブラリの使い方が身につく
- アルゴリズムの知識が身に付く
- コードの実装力がつく
- 思いついた処理を書くという作業をする点では、個人開発よりも数をこなしやすいです。
- 言語や書く内容が実務と異なるとはいえ、コーディングそのもののトレーニングになる気がします。
これまで２週間、思ってたよりもかなりハマって継続できてます。
だんだんとモチベは下がってきてる感は否めませんが、やれるだけやってみたいです。
ひとまずの目標としては２つ、
- 分野別 初中級者が解くべき過去問精選 100 問 を解ききること。
- 緑色ランクになること。
最終的には、水色ランクを目指したいですね。
