こんにちは尺八です。
今回、ABC289(2023/2/11)で水色Coderになったので報告と振り返りをしたいと思ってこの記事を書いてます!(画像がAGC061を受けた後なのはご容赦ください!)
自己紹介
明治大学情報系学部在学中の大学2年生です!
兄弟で競プロやってます!(1つ上の兄がいます)
メイン言語はABG4bを習ってから、ずっとC++を使っています。
趣味はゲーム(スプラ・雀魂等)と音楽を聴くことです。
プログラミング系のサークルには入っておらず、競プロ始める前は授業でprocessingでif文・while文・配列を理解してる程度のプログラミング能力でした。
競プロを始めた経緯
(興味ない方は飛ばしていただけると幸いです!)
大学1年の12月ごろ、突然兄に「競技プログラミングっていうのがあるんだけどやってみない?」と言われたのがきっかけです。その時にAPG4bの存在を教えてもらい、少しずつ進めていったんですが当時の自分は度が過ぎた完璧主義者だったので失敗することに対して異常に恐怖を感じており、コンテストに出る意欲もABG4bを進める意欲も沸かず第1章を終わりそうなときにやめることを考えました。
やめようか考えているときに今度は大学の友達から「競技プログラミングって知ってる?」と言われて、そこから「なら一緒にやってみよう!」と言われて頑張ってみるか!と思った結果、何とか今まで続けられています。
(今振り返ると、変にクソ高いプライドなんか持って失敗を恐れて何もチャレンジせずにうじうじしてるよりも、失敗に終わったとしてもやりたいことにチャレンジしている方がよっぽどカッコいいと思います。)
灰色時代
習得した事
・pair・tuple・auto文
・bit全探索
・queue/stack/map/priority_queue/set/map等
このくらいですかね。アルゴリズムに関してはこのころはあまり学んでいなかったと思います。問題をたくさん解いてたら茶Coderになってました!
入茶するためにやっていた事
・ABG4bで1~3章をやって基礎的な部分を学んでいました。
・Atcoder Problemsで灰・茶色diff埋めをしてました。このころは、難しい問題を解くことよりもできる問題を以下に早く解くかを重要視していたのでとにかく量をこした記憶があります。
・Syntax_Error_さんとtettyあさんが作ってくださった毎日C・D問題をやってました。(現在は運用を終了してます。)
茶色時代
習得した事
・動的計画法(DP)の基礎的な部分
・再帰DFS(今も苦手)
・BFS
・二部探索
・メモ化再帰
・1次元累積和
・座標圧縮
・尺取り法(今も苦手)
以上です!自分がコンテストを受けていた時期はDPが結構出てきていたのでDP以外はあまり使っていないような印象があります。一回落茶したときは結構焦りましたけど、いつか戻るだろ精神で構えてたら戻りました。
入緑するためにやっていたこと
・Atcoder Problemsで茶・緑diffの問題を埋めていました。
・けんちょん本を読んでアルゴリズム力を鍛えていました。この本のおかげで、深くまでアルゴリズムを理解でき難しい問題に対する対応力が上がったと思っています。(けんちょんさん)
緑色時代
この時がやっぱり一番大変でした。
習得した事
・動的計画法(DP)の応用的な部分(bitDPや木DP)
・貪欲法
・ダイクストラ法
・半分全列挙
・ランレングス圧縮
・ベルマンフォード法
・ワーシャルフロイド法
・ダブリング
・2・3次元累積和
・UnionFind
・(遅延)セグメント木(微妙)
・フェニック木(Binary Indexed Tree)
・最小(大)全域木
・強連結成分分解
・その他(setやmapで二部探索可能なことやmultiset等)
くらいですね。習得したアルゴリズムの量がどっと増えました!またただアルゴリズムを覚えるだけではなく、どこら辺で計算量がかかっていてそれを解決するにはどのようなやり方をすれば解決できるのか、ということを意識的に考えられるようになったのもこの時期です。
入水するためにやっていたこと
・Atcoder Problemsで茶・緑・水diffの問題を埋めていました。
・Atcoder Problemsのバーチャルコンテストに参加してました。特にいいなと思っているのは最近参加できていませんが、buriodenさんのABCなにかは参加者も結構いますので実際のコンテストみたいな緊張感があって早解きの練習にはもってこいだと思います!
・鉄則本でアルゴリズムの勉強してました。dpやグラフ理論など様々な分野のものが網羅されており、すごくよかったです。(E8さん)
入水するまでの時系列
10~11月:このころはすごく順調でした!ARCで1回レートを落としたことを除けば全部上がってますし、水perfも3回も取れていてレートが一か月で180程度上がっていたので内心余裕で入水行けるんじゃね!?と思っていました。
11~12月:現実は厳しい....4桁突入してからレートが停滞してきて一か月で25しか上がらなくなってしまいました。このころからD問題が解けるのにC問題が解けないことやE問題が解けるのにD問題が解けなくなることが頻発するようになりました。そういったこともあり今まで以上に本気でやり始めました。具体的には1日に5分でもいいから必ず水perfの問題を考えることを決めました。
12~1 月:一か月で12しか上がらなくなってしまいほぼ現状維持です。12/24のABCで茶perfとってしまったのがすごく痛かったですね。
1~2 月:少しずつですが上がってきてようやく調子を戻せそうだなっと思った矢先......
はい...これです。 ARC0完!茶perf!-49!!wwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwwww
絶望しました。っていうのはオーバーリアクションですが、1か月やってレートが減った精神的なダメージはデカかったです。この時ARCに出ないことを強く誓いました。(嘘です。普通に出ます)
2~ 月
神はいました。
ABC288の方は問題が特殊(D問題が滅茶苦茶むずかった)ことが幸いしてE問題を解くことでうまくいきました(E問題解法思いついたときは心臓の音を体中に感じるぐらいドキドキしてました)。ABC289はE問題の計算量がどのくらいかかるかを解析して早めに方法を思いつくことが出来てA~D問題もスムーズにいったのでうまくいきました。こうして入水しました!
おわりに
今atcoderのレートが停滞していたり、下がっている人がいるならば私みたいに急に跳ね上がることもあるよ!ということを伝えられて励みになったとしたらこれ以上に嬉しいことはないです。一緒に楽しみつつ頑張りましょ!