Motsu_xe 競プロのhogeやfuga

Motsu_xeが競技プログラミングに関する何かを適当に書き連ねるブログになるはずです。

AtCoderでレート2093になるまでしたこと

競技プログラミング 自分語り

こんにちは！私はMotsu_xe、またの名をもつ鍋xeという、しがない競技プログラマの一人です。今日は私が競技プログラミングに出会い、今まで何をしてきたのかを振り返っていきたいと思います。
皆の疑問はわかります。2093って中途半端すぎるだろ！みたいなところでしょう。いやぁ、ブログを始めたらやっぱり色変エントリを書きたいと言う憧れはあるじゃないですか。ところがどっこい、自分しばらく色が変わりそうにないんですよね、まあ橙になれって話ではあるんですが、この前-49して2100割ったばっかですし…()。と言うことで、まあ色変エントリは諦めて、自己紹介をかねて今までを振り返る記事を書いてみようと相成ったわけです。書いてる途中で思ったんですが、人に見せるものじゃないです。

競プロとの出会い

さて、中高時代、父親がプログラマなのにも関わらず、私はプログラミングの類とは一切縁の無い生活を送っておりました。そして勝手な先入観で、プログラミングは自分には向いてないし、多分好きじゃ無いと思い込んでいました。そのため、物理や地学、ちょっと数学など色々手を出して遊んではいましたが、情報系には一寸も手を出そうとしませんでした。
転機が訪れたのは2018年3月。高3の私が二次試験も終わって、割と暇しており、前々からTwitterで名前を見ていたAtCoderと言うサービスに気まぐれて登録することになります。「今の時代、プログラムの１つも書けないんじゃ話にならんだろ、コンテストで競いながら進めれば、興味なくても多少勉強にはなるだろ。へのk*1とかも最近始めたみたいやな、とりあえずへのを目標に頑張るか*2」みたいな思考でとりあえず登録をしました。これが伝説の始まりと言うわけです。


始めるや否や翌日にはABC088-DをACしてて強さが伺えますね。BFSもDFSも知らん状態で最短経路問題を0から解き切ったのは余りにも頭がいいと言わざるを得ません。思えば一番頭が良かったのは始めた頃で、単調に頭が悪くなっていってますね、最悪です。

第１期

無事競プロとの出会いを果たしたもつ鍋少年ですが、全く精進もせず、適当にコンテストだけ出る生活をしていました。コンテストは楽しかったですし、競プロ自体も面白かったのですが、まあのめり込むほどではありませんでした。しかしまあ地頭がそれなりにあったので*3、適当にやってもレートは上がっていって、一月ちょいで水色になることができました*4。そして、これ以上は精進しないとレート上がんないなと悟り、また精進するほどのやる気もなく、2018/06/03のAGC025を境にしばらく競プロに触れない生活が続くことになります*5。

第２期

さて、半年間ほとんど競プロに触れない期間が続き、次にコンテストに出たのは2018/12/15のAGC029。周りでも競プロerが増えてきて、ちょっとずつモチベが上がってきて、水色から落ちない程度に勉強して春休み頃に復活しようかなぁ、と企んでいてフライングして復活しました。ここから競技プログラマとしての自覚が生まれるわけとなりました。精進を始めたのもこの頃からで、段々と競プロの魔力に取り込まれていくことになります。

行った精進

どんな精進をしてきたのかを、大雑把にまとめていきたいと思います。

開始時期 終了時期 精進内容 備考
2018-12-15 2018-12-16 ABC-A埋め(Python練習) 大体スマホ
2019-01-09 2019-01-17 AGC-A埋め 全部ではないけど、えらい
2019-01-18 2019-02-01 AGC-B埋め 7割くらい(なんで通せてるの？)
2019-02-03 2019-02-04 ABC-B埋め
2019-02-13 2019-02-24 EDPC埋め これでDPがだいぶわかった
2019-02-25 2019-02-25 2718点埋め は？
2019-02-27 2019-03-19 200-300点埋め
2019-03-19 2019-03-25 400点埋め スピードが早い
2019-03-26 2019-04-07 500点埋め
2019-05-07 2019-06-13 旧ARC-C埋め これで強くなった気がする
2019-05-25 青色になる 5/11のdivertaで青になってるはずだった
2019-06-22 黄色になる 青が短すぎるね
2019-11-30 2019-12-04 旧ABC-C埋め
2019-12-04 旧ABC-D埋め 今やってるよ

と言う感じになっています。個人的にかなり力がついたな、と思うのは400,500点埋めと旧ARC-C埋めのときですかね。当時の自分のレベルから若干重いくらいの問題で負荷をかけ続けられたので、成長を感じられました。また蟻本ゼミ*6に参加して、モチベ上昇、能力上昇していたのも同じ時期ですね。ここら辺で実力は急激に上がって、一気に黄色になれたとのだと思います。
黄色になった後なのですが、まあ上の表を見るとわかる通り、ろくに精進を積んでいません。そりゃあレートも上がらんわな、とまとめていて感じました*7。今後なのですが、今やっている旧ABC-D埋めが終わったら何をしようか悩んでいます。打ち止まり感はまだ感じていないのですが、何をしたら強くなるかはよくわからないでいます。足りないものはCodeforcesとかJOIとかICPCとかにありそうな気がしないこともないので、そっちにも手を出した方がいいのかなぁと言う気持ちはあるのですが、AtCoderから抜け出す気がおきないんですよね…どうしましょう。何かオススメの精進があればお教えください。

使える技術

どの時期にどのくらいできたかは正直覚えていないので、今使えるものを上げていきたいと思いましたが、自分はあまり考え方の名前を知らないので、言語化できません。なので持ってるライブラリだけ晒します。ライブラリ名の辞書順です(は？)。

  • Aho-Corasick
  • Bellman-Ford
  • Binary Indexed Tree
  • 二部グラフの最大マッチング
  • 座標圧縮
  • Convex Hull Trick (Li Chao Tree)
  • 組み合わせ数(線形前計算)
  • 線分の交差判定
  • 最大流(Dinic)
  • 約数全列挙
  • Dijkstr
  • Eratosthenesの篩
  • 素因数分解
  • Garner(使ったことねぇ)
  • 最大公約数
  • 最小全域木(Kruskal)
  • 最小共通祖先(ダブリング)
  • 最長増加部分列
  • 遅延セグメント木(max,min,sum,抽象化)
  • Manacher(使ったことねぇ)
  • 行列(四則演算,det,rank)
  • 最小費用流
  • Mo's algorithm
  • modint
  • 高速フーリエ変換(NTT)
  • †ペアリングヒープ†(使ったことねぇ)
  • 多項式(四則演算)
  • 部分永続Union-Find
  • 累乗(ダブリング)
  • 有理数
  • ローリングハッシュ
  • 強連結成分分解
  • セグメント木(非再帰)
  • 双対セグメント木(max,min,sum)(確か壊れてる)
  • Sparse Table(min,max)
  • Sliding Window Aggregation
  • 対称群(合成、互換、線形累乗)
  • Trie
  • トポロジカルソート
  • Union-Find
  • Z-algorithm

色々ありますね。これなんでないねん、とか言うのがあったら教えてください。

最後に

これ何のための記事何だ。自分の現状を見直すいい機会にはなったのでついでに晒しておきます。参考にしたいことがあれば参考にしてください。質問も何でもどうぞ(答えられるかは知りません)。
それではこの辺で筆を置かせていただきます。Au revoir!

*1:皆さんご存知、heno239(@heno_code)さんです。高校時代からの知り合いで、私が始めた当時は緑色でした。ところでダナン優勝おめでとうございます！

*2:いまだにこれが目標の1つです。まさか彼がここまで上の存在になってしまうとは当時は思っていませんでした。

*3:は？

*4:当時は今より水色にかなりなりやすかったことには触れておきましょう。

*5:これにはアイドルマスターミリオンライブ!シアターデイズ(みんなやろう)の1周年イベントをやってたら、競技プログラミングのことを忘れてしまったと言う説もあります

*6:ナン(@naan112358)主催の駒場で開催されたゼミです。競プロ仲間で集まって、問題を決めて解く、解説を聞く、質問する、駄弁る、くそなぞなぞするなどをする会です。

*7:精進グラフを見ると、それなりにやっていそうに見えるんですが、新ABCや適当に残ってる問題潰しているだけなので、ダメなんですね。


スポンサードリンク