競プロ始めました！
近況報告 - 競プロ楽しすぎ
1週間前に競プロを始めました！
きっかけ
競技プログラミングを始めたのは期末テストがほとんど終了した日でした。 テストのために、来る日も来る日も一日中数学をしていたので、少し数学に飽きてしまって、それでなにか新しいことを勉強したいなと思って始めたのが競技プログラミングです。 前にOMC(Online Math Contest)という競技数学のサイトはやっていたので、なんとなくAtcoderの存在は認知しており、前々から機会があれば始めたいなと思っていたことの一つでした。
プログラミングの経験としてはpythonを少々...。という程度です。 具体的には、manimを触ったり数値計算をしたり、あとは少しだけpytorchを触ってみたりもしました。 いわゆるatcoderで使うようなアルゴリズムやデータ構造といった勉強は、高校の情報の授業で少しと大学の教養の授業で少し習った程度です。 クイックソートやヒープソートの実装や、素因数分解の実装が関の山です。
初めてのコンテスト
水曜日に競技プログラミングとC++を始めて触りました。 apg4bというものがあって、それをこなしていくだけでC++の基礎が身についたので非常にありがたかったです。 水曜日はこれの1章だけで終わってしまいました。 木曜日と金曜日はまだ一科目だけ残っていたテスト勉強（たしか微分方程式だったはず）の勉強に充てました。 そのため、プログラミングは殆どできなかったです。 そして迎えてしまった土曜日。 この日も夜まで外出の用事がありましたから、結局ほぼ初心者の状態でコンテストに挑むことになりました。
結果はA,B,Cの3完といったところで、なかなかにボコされてしまいました。 0-indexedと1-indexedを勘違いしてWAを出したりとなかなかに酷い提出をしたなと思います。 まぁ、ほとんど始めて2日目のようなものだったので仕方ないかなと思います。 パフォーマンスとしては茶色でした。その割にレートが30くらいしか増えていなくて、少し悲しい気持ちになりました。
D問題は累積和の2次元バージョンかな？ということには気がつけましたが、尺取法というアルゴリズムを全く知らなかったので、無事にTLEをしまくりました。 あと普通に実装もおぼつかなかったです。
精進とやらをしてみる
とにかくプログラミングが楽しかったので精進をしてみることにしました。 とりあえず、競技プログラミングの典型90問というコンテンツがあったので、これを回してみることにしました。 最初は★2だけを、次は★3だけをといった具合に解いていくことにしました。 ★2の問題でも、わからないものも多くありました。 setやmapなどの使い方と簡単なアルゴリズムが習得できたのはかなり嬉しいですね。
慣れてくると意外と★3や★4も解けるようになってきました。 新しいアルゴリズムを習得するコンテンツのはずですが、なぜか割と自力で思いつくことができて、結局、知らないアルゴリズムでも半分くらいはノーヒントで実装まで完了させてACをすることができました。 めちゃくちゃ癖になる感覚です。 あとは、知らないアルゴリズムを解説を見て学んだとき、めちゃめちゃ賢すぎて感動します。 すごい。 僕の場合は、シンプルに数学的な問題はかなり歩があると思いました。
そんな中でも、グラフに関連する問題の実装は全く葉が立ちませんでした。 木の直径を求める問題が出てきて、手も足も出ずに終わってしまいました。 どうやらBFS,DFSなるものがあるらしいということを知り、queueやstackなどと併せて習得しました。 最初の関門だなぁと言う感じがしましたが、2時間くらいやっていると慣れてきて扱えるようになりました。 嬉しい。
あとこれくらいのタイミングで、ライブラリ(?)を整備することを決めました。 htmlで、よく使うアルゴリズムをコピペできるようにまとめておく物を作りました。 非常に便利だし、忘れたときに参照できるという安心感が非常に嬉しいです。
結局、初めて1週間で学んだアルゴリズムは、簡単な累積和、set・multisetの使い方、pairの使い方、グラフの隣接リスト、bit全探索、二分探索、動的計画法、貪欲法、工夫した全探索、dequeの使い方、繰り返し2乗法、素因数分解、しゃくとり法、ランレングス圧縮、順列全探索、結果で二分探索、BFS、DFS、耳DP(?) 、Union-Find、いもす法（2次元いもす法）、ダイクストラ法、0-1 BFS（要復習） といった感じになりました。
バチャをしてみた
初めて1週間(と1日)が経った今日、初めてバチャ（バーチャルコンテスト？）なるものをしてみました。 結果としては、これまたボコボコでした。 ABC453に挑戦してみました。 とりあえず、序盤はA問題5分、B問題4分、C問題10分でACといった感じでした。 勉強したbitDPがスムーズに書けたのは良かったです。
そこから、D問題へと行こうとしたのですが、これがまぁ難しい。 問題文が長くて、迷路っぽい感じで凄く難しそうでした。 典型90で似たような問題をやったので、解けそうかとも思ったのですが、まだ迷路？グラフ？に関する問題に苦手意識があって手が動かせなかったです。 代わりに、逃げるようにE問題に取り組みました。
結局、時間内にACすることはできませんでしたが、コンテスト終了20分後に自力ノーヒントでACできました。 勉強したいもす法が身についていたのはかなり良かったと思います。 でも、これは結構数学によっていたのも大きかったかも。 1500diffくらいあったようで、始めて1週間で得意分野(?)とはいえこれくらいのdiffが解けたのは上々かなと思います。
とりあえず、当面の課題として、「知らないアルゴリズムが多いこと」「グラフや迷路の実装が苦手なこと」「データを管理する構造として何を採用するべきかの判断ができない」などが挙げられるのでこれを改善していきたい。 1つ目は典型90などで今後も補っていきたい。 2つ目についてはかなり明確で、それ系の問題をちゃんと実装までしきってACをする経験を積む。 3つ目は、問題を解いたあとにChatGPTなどに本当はどういうデータ構造を使うのが良かったのか？を毎回聞くことで解決できそうだからこの方針で頑張りたい。 この感じで行けば、緑パフォは結構安定して出せそうで、水パフォも夢じゃないという感じなので、頑張っていきたいです。 それでは、また...。