はじめに
kureha といいます。この度 AtCoder にて入黄を果たしました。本記事はその記念に書いたものとなります。
自己紹介
・ハンドルネーム : kureha
・年齢 : 20 + n 歳
・職業 ? : 大学生
・競プロ歴 : 約 2 年
・使用言語 : C / C++
AtCoder 入黄
見出しの通り、AtCoder 入黄を果たしました。
黄色に到達するまでのコンテスト参加回数は 53 回、期間は約 1 年ほどとなります。競プロ全体で見ても黄色コーダーの中で見ても短い方だと思います。
初めてのコンテスト参加が競プロの始まりだったわけではなく、以前から過去問には挑んでいました。それも含めると約 2 年くらいになります。まだまだ短い方ですかね、どうなんでしょう。
ちなみにプログラミングに出会ってからは約 3 年になるらしいです。最初の一年間の記憶がほとんどないのですが。
振り返り
レーティングを上げるために何か特別なことをしたかといわれるとそうではない気がします。基本的にはコンテストに出るなり、過去問や有志サイトの問題を解くなりしてその復習をするの繰り返しだったかと思います。
とはいえこれだけですべて片付けるのは味気ないし、初めての色変記事でもあるし、今までのことを思い出せる限りで羅列していきます。
プログラミングの世界へ
一番最初に触った言語は C です。約 3 年前、大学の講義の一つとして出会いました。あまり覚えていないのですが、当時使っていたオンライン教材を見るに基本的な知識を学んでいたようです。単純な計算方法から始まり、入力、偶奇判定、FizzBuzzを経て、最後にバブルソートと選択ソートとなっていました。
この記事を書くために大学でやったプログラミング関係の講義を見ていたときに偶然思い出したわけなのですが、もう少しで亡き者にされるとこでした。危ない危ない。
競技プログラミングの世界へ
一年後（今から約二年前）に競技プログラミング (AtCoder) と出会いました。どんなルートでたどり着いたかは覚えていませんが、『AtCoder における初めての提出』がそう言っているので間違いないです。
AtCoder にある問題を少し解いて、二週間から一か月くらい空いて、また AtCoderを見に行くという期間が四か月くらい存在しました。このときに解いていた問題は、主に灰diff、茶diff と呼ばれる簡単なものでした。問題の難易度は AtCoder Problems という有志サイトで見ることが出来ます。むしろそれ以外の見方を知らないともいうけど。
当時の装備は大学の講義でやったことのある内容だけで、標準的に使用可能な関数やアルゴリズムをほとんど知りませんでしたが、『ソートすることができればこの問題が解けるのに』とかは何回か思っていたようです。幸いにもソートを速く行う方法があるという知識は持っていましたが実装が分からなかったので、調べて他所からコピペして使いまわすなどしていたことは割とはっきり覚えています。今思えばこのときから『○○があれば解ける！』といった考察ができていることは結構よかったのではないかと感じていたり。
その期間が明けた夏休み +α。それまでに比べて頻繁に問題を解くようになります。ここで C++ で提出するようになり、緑や水色の問題も少し解けるようになりました。インクルードに numeric とか alogorithm とかが追加されましたがソートしか使ってなかったような。
初めてのコンテスト
2022/02/27、コンテストに初めて参加します。ABC ではなく ARC だったようです。問題 A が灰diff、問題 B が水diff で、このときの実力なら最低一問は解いて、二問目は解けたら御の字みたいな難易度でした。結果としてはペナルティを何回か出したものの最低限の一問を解き切りました。問題 B にも挑んでいたみたいですが、テストケースの一つに敗れていました。なんでダメなのかわからん、みたいなことは思っていました。当時の書いたコードを見ても何をしようとしていたかはさっぱりわかりませんでした。もしかしたら理解を諦めただけかも。
翌々日、問題をたくさん解いたようです。常設コンテストに『アルゴリズムと数学 演習問題集』があるのですが、前半 40 問弱を一日で解いた跡が見られます。コードの中身を見てみると、（典型的な）アルゴリズムを知らないなりの工夫が見られました。アルゴリズムを知らない故に鍛えられる考察力もあるのかもしれませんね。頑張ってた自分を褒めたい。
次の話に移るまでの約半年間、まとめて問題を解いたのはこの日ぐらいで、この後は散発的に問題を解いたようです。ARC と ABC に一回ずつ参加して茶色になりました。
本格的な競プロ道
2022/08/06、この日からほとんど毎週のコンテストに参加し、本格的に競プロの道を歩くことになります。初めてレートが下がった日でもあります。2ヶ月ほどは競プロ漬でした。ちょうど大学の夏休みだったのも大きいです。
本来であれば色ごとにやったことを分けるべきかなとも思うのですが、茶色と緑色は超特急で飛ばしてますし、水色での一か月半ほどの停滞期は毎週コンテストに出ていただけらしいので、全部まとめてここまでやっていたことを書き連ねます。
- 『競プロ典型90問』をやった。
常設コンテストの一つです。全部をやったわけではないです。知識を得るにしたって知らなければ調べようがないので、実際に問題を解いて「どういった問題があるのか」「どんなアルゴリズムやテクニックが必要なのか」を身をもって体験します。ちなみにこの理由は後付けです。
- ABC / ARC 過去問を解きまくった。
夏休みの 2ヶ月で 430 問ほど解きました。一日当たりコンテスト1，2回分と考えればそうでもないように見えると同時に暇だったんだなぁと思います。このときは終了したコンテストを適当に選んで突貫していました。過去に解いた問題を選ぶことも偶に。AtCoder Problems で過去に自分が解いた問題を見れますが、当時は知らなかった。
- 鉄則本を読んだ。
競プロにも問題集や参考書のようなものが存在します。鉄則本はそのうちの一つで、正式名称は『競技プログラミングの鉄則』です。ここに掲載されている問題は、実際に常設コンテストとして解くことが出来ます。
大学で研究室に早期配属されたときに先生から貸し出されました。最大流・最小カット問題と二部マッチングが初知りでした。半年後、別の研究室に移動した模様。
- 毎週のコンテストに出た。
出なければレートは上がらないので、レートを上げたければ出るしかないです。
振り返りのまとめ
こうして書いてみると、問題を解いて復習するの繰り返しだけで特別なにかしたわけではないなぁと思います。参考になるような点もそれほどないかな。夏休みに解いた量は異常かも？
勉強すべきアルゴリズムやテクニックについては人それぞれでしょうし、個人的には実際に問題を解いて『こんなアルゴリズムがあれば ...！』というのを感じてみるか、著名な方の記事や本を参考にしたほうが良いと思うのでここには載せないことにします。
ちなみに今まで解いた問題は 1303 問とのことです。
今後
競プロについてはとりあえず橙を目指します。ただその前に青落ちしないといいなぁという感じです。当分は往復しそうです。黄色になった翌日に早速落ちそうでしたし。
ICPC があるとのことで、大学の競プロサークルの力を借りて出ることにしています。ルールの都合上、ライブラリなどは印刷して写すことになるのですが、他人のコードが読めない病にかかっているため部内で作成されているライブラリがいまいちわかっていなかったりします。AtCoder ライブラリも使えなさそうなので、余所から引っ張っていたものを自分で構築しなければならなそうです。
個人的には作問したいなぁと思いつつ、どうしたら問題が出来るのかと不思議に思う日々が続いており。数学の徒なので数式をこねたら解ける問題しか作れない...。
競プロ以外について、院試があるので勉強をしなければ...。院試終わりまでは青落ちしなければ ABC はほどほどになるかと思います。卒研が終わるまでもつれ込むかも。いい研究室に入れたので何とかはなりそうです。鉄則本を貸していただいた研究室とは別のところです。
あとがき
最後まで読んでいただき有難うございます。
また次の記事でお会いしましょう。それでは。
