はじめまして
競プロerのmyauです。普段はAtCoderやCodeforcesで問題を解いて楽しんでいます。競技プログラミングの参加記や感想を書いて残しておく場所があったらいいなと思って、ブログを開設してみました!初記事では直近の大きな出来事である色変について書きます!
自己紹介
某大学にいる医学生です。じつはその前にほかの大学を出ています。前の大学では文系だったので、まだ自分は文系競プロerだと思い込んでいます。
友達に誘われてはじめたのですが、コンピュータ系の知識はほとんどなくAtCoderの教材・過去問を使って力をつけてきました💪
CPUってなあに?っていうレベルなので、コンパイルとか環境構築とかは捨ててコードテストを愛用しています。今3年目ですね。
言語はほぼC++です。たまに多倍長で殴れる簡単な問題だとPythonを使うことがあります。C++は速くていいぞ、犯罪AC・logつけてでも高度データ構造パンチがしたいならおすすめ
好きなデータ構造はSegment Tree、問題の好みは「考察すると実は典型問題に帰着される」問題です。比較的早解きが得意ですが、極端な得意・苦手はないバランスタイプです。
AtCoder
ちょっと停滞気味だったAtCoderですが、なんとか今年の1月にはじめての入黄を達成しました!!!!!!!!すごい!!!!!
コンテストと学校の試験のスケジュールが合わなかったりして、なかなかRatedに出れなかったのですが、3月にひさしぶりにARCに出て青落ちしました、かなしい😢
でも次のABCでちゃんと黄色に戻ってこれたのでなんとか黄色Coderを名乗れています。実力的にはまだ反復層にいる気がするので、最低限反復層に存在しつつ、ちょっとずつ上げていきたいですね。今年の目標はAtCoder2200です。
Codeforces
こちらは開催時間が遅いこともあってあんまり出ていなかったのですが、ABCがUnratedになってRatedが減ったので、そのぶん出てみようと思って何回か出ました。
2月下旬のえでゅふぉで早解きで勝って薄橙になりました!!!どっちも暖色になってすごく嬉しかったです。と調子に乗っていたら先日のcombinedで冷えて紫に落ちてしまいました...こどふぉはAtCoderと違って慈悲がないのでちょっとしたミスですぐに溶けてしまいますね、なんとかもう一回色を戻して濃橙を目指していきたいです!
できること
こういう色変記事の定番ですね、今もっているアルゴリズム・データ構造を列挙しておきます。
・累積和(二次元含め)
・imos
・DP
・二分探索 / 三分探索
・bit全探索
・座標圧縮
・繰り返し二乗法
・ダブリング / LCA
・二項係数
・BFS / DFS
・Dijkstra / Bellman-Ford / Floyd-Warshall
・Union-Find
・トポロジカルソート
・オイラーツアー
・行列累乗
・全方位木DP
・Segment Tree / 遅延 Segment Tree
===ここからはライブラリが使えるだけ===
・Lowlink (橋や関節点の検出)
・強連結成分分解
・中国剰余定理
・最大流 / 最小費用流
・Z-algo
・Manacher
・Rolling-Hash
・Suffix-Array
・Trie / Binary-Trie
・二次元セグメント木
・Convex-Hull Trick / Li Chao Tree
・離散対数問題
・掃き出し法
・ラグランジュ補間
・FFT
・高速ゼータ変換
・2-SAT
ざっと思いつくだけでもこのくらいはあります、頑張ったな~~という感じがしますね。勉強したけど使っていない、ライブラリ貼って理解した気持ちになってるけどよくわかっていないものもたくさんあるんですが、武器はあって損することはないです。
ただ高度なものになればなるほど登場頻度は減るので、勉強したからといって活きる機会は少なくなります。はじめはコンテストや過去問で当たったものから覚えていけば自然と頻度順に近くなるんじゃないでしょうか。
競技プログラミングとの向き合い方
モットーは「競プロを楽しむ!」、これに尽きます
自分は情報系でもなく、プログラミングで食べていこうとも研究しようとも思っていないので、スキルアップという面はほとんどなく「タダでめっちゃ遊べるネトゲ」みたいなものだと思っています。ゲームなので、自分が楽しむことが最優先です。もちろん勝てる・ACできると楽しいので、そのために頑張って過去問を解いたり、アルゴリズムを勉強したりします。レベル上げですね。
自分の中で頑張ったなと思って出るコンテストはすごい楽しいです。レベリングしたらどの敵まで倒せるようになったのかな、わくわくっていう感覚です。逆にあんまり精進できないとちょっとコンテスト出たくないなと思う時もあります。熱烈精進するか怖がらずに突撃すると実力は伸びると思うんですが、そこは自分のメンタルとの相談です。
それでもやっぱり勝ちたい・実力をつけたいという気持ちもあるので、ちょっとずつ勝負に寄せていけるといいな、それが「競技」プログラミングの世界に自分が入っていくことなのかなと最近思っています。ちょっと前までは、昔の自分との対決、昨日の自分よりレベルを上げるという割合が高かったのですが、強くなってくるにつれてほかの競技者が視野に入ってきた気がします。
これを読んでくださっているみなさん、ぼくと戦いましょう!!!
おわりに
まだまだ競技プログラミングは続けていくので、力をつけてまた色変記事が書けるようにレートを積んでいきたいです!
コンテストの簡単な参加記や解いた問題の解説を気まぐれにのせていきます。よろしくお願いします。