AtCoder青コーダーになりました

競技プログラミング 色変 AtCoder

始めまして、競技プログラミングをしていますFlkanjinといいます。
1/23のABC189でAtCoderのレートが1668となり入青しました。


もともと色変したらブログをはじめて色変記事を書こうと思っていたのですが、色変したタイミングが大学の期末試験の直前だったので、1週間たった今記事を書いています。

0. 競技プログラミングを始めるまで

中学生の時からプログラミングに興味があり、いつか始めたいなぁ...と思っていたら、高校で仲良くなったクラスメートにプログラミングのできる子がいて、1年生から2年生になる春休み前にその子に教えてほしいと頼んだのが、プログラミングを始めるきっかけでした。C++をある程度教えてもらった後5月頃にAtCoderについて教えてもらい、参加するようになりました。

1. 緑色になるまで

今と違いAtCoderの人口が多くなく、今ほど要求される知識がなかったことと、ある程度言語を習得してから参加したことにより、あまりアルゴリズムの知識をつけることもなく緑になっています。もしかしたら、数学が得意だったのもあるかもしれません。あまりこの時期についてはあまり書けることがありませんし、今から始めるという人はあまり参考にならないかもしれません...。一応AOJに登録して螺旋本を買って勉強は少しはしましたが、計算量についてはそこまで意識していませんでした(アルゴリズムが分からないので意識したところで解法が思いつかない...という感じでした)。
一応この時に習得したアルゴリズムとしては

  • 尺取り法
  • 累積和、imos法
  • DFS、BFS
  • bit全探索
  • 二分探索
  • DPについて少し

が挙げられます。

このときJOIに出ましたが、後1問のところで予選敗退でした。余談ですが、JOI予選は修学旅行の前日でした。
3年生になった時に受験勉強に専念するために競プロからしばらく離れることにしました。

2. 競プロ復帰から水色になるまで

受験に失敗して1年浪人したのち、無事に大学に受かり入学しましたが、4, 5月はまだ競プロに復帰していませんでした。大学で同じクラスになった子が競プロを始めるという話をしていたので復帰しようと思い、6月にAtCoderに戻ってきました。久しぶりのコンテストでレートが下がらず、また高校の時と違って時間に余裕ができて段々とのめり込むことになりました。
ここから螺旋本を読み直してAOJの問題を解いたり蟻本を購入しちゃんと勉強するようになり、また高校の時は家族共用のPCだったのでライブラリを作っていなかったのですが、マイPCを持つようになって、ちゃんとライブラリをつくり、整理するようになり、この時は

  • Union-Find
  • 行列
  • 2次元幾何
  • グラフの最短路(Bellman-Ford, Dijkstra*1, Warshall-Floyd)
  • 最小全域木(Prim, Kruskal)
  • 順列、組み合わせ、冪乗、逆元の計算

のライブラリを作りました。
アルゴリズムとしてはそれまでほんのちょっとしか理解できておらず、苦手意識のあったDPについてEDPCで少し勉強して区間DPやbitDPができるようになりました。
また、この時Codeforcesに登録し3回コンテストに出ましたが、日本だと深夜となることが多くあまり参加できていません。
また、2回生になってから大学のコンピュータ系サークルに所属し、競プロ練習会に参加するようになりました。

3. 青色になるまで

 水色に上がってからはレート1400附近で少し停滞した後、1574まで上がった後1450附近まで落ち、少し停滞したのち、徐々にレートが上がっていった後、ABC189で初の黄パフォを出して青に上がることができました。
実は速解きするべき問題で悩んでしまったり、A問題でつまらないミスでWAを出して焦ってしまってなかなかレートが伸び悩んだりすることがありました。それでも継続は力なりと思って参加し続けているうちに、そういった事は少なくなってきたように感じます。また、何回も出ることによって、自分の知らない知識や考え方を知ることができ、それがレートの上昇につながったのだと思います。

学んだこと

アルゴリズムとしては

  • 座標圧縮
  • 半分全列挙
  • ダブリング
  • Rolling Hash

あたりを学びましたが、実際の所まだまだ、未消化の所があり、空で書けるかと言われると少し厳しいです。
また、この時期にACLが配布され、そのコードを基に

  • セグ木
  • BIT

を理解しようとして自分で実装してみました。

4. これから

今度は黄色を目指していきたいと思います。黄色になればABCがUnratedになりますね。勿論簡単な事ではないので時間はかかると思いますし、そもそもできないかもしれない...それでも努力は報われると信じて精進していきます。
また、これまではあまり界隈の人々とのつながりがありませんでした。これからは交友の輪を広げ、様々な知識を吸収していきたいなと思います。

*1:このijは合字の方で書いていますが、二重音字であり合字ではないという人もいます。オランダ語で用いられる文字で大文字で書くときはIJと両方とも大文字になります。[ɛi]と発音されるのでダイクストラというよりかはデイクストラの方が近かったりします。筆記体が似ているという理由でÿと書く場合もあったりします。