AtCoder で水色になりました
はじめに
こんにちは。高校 3 年生の ma_tw と申します。この度、AtCoder で水色のレーティングに到達したため、その記録としてこの記事を書きました。(いわゆる色変記事です。)
筆者について
以前よりプログラミングに興味があり、高校 2 年生のとき少し Python を勉強していました。しかし特に作るものもなく、適当なコードを書いているだけでした。(ゲーム開発等にはあまり関心がありませんでした。)
そんなとき、競プロの存在を知ります。恐らくは Twitter で見かけたのだと思います。それで何となく AtCoder Beginner's Selection を解いてみたところ競プロに興味を持ちはじめ、コンテストに出始めるようになりました。またそのとき競プロには C++ が向いているということを知り、C++ を勉強しはじめました。そして今に至ります。
記録
初めてコンテストに参加したのが 2021/9/4 なので、およそ 1 年と 2 ヶ月での入水となります。
履修したアルゴリズム等
あくまでなんとなくです。(以下に並べたものの中でもまだまだなものもあります。)
- 二分探索
- DP
- ナップサック DP
- 区間 DP
- bitDP
- 累積和
- いもす法
- 座標圧縮
- 繰り返し二乗法
- 素数あれこれ
- 基本的なゲーム問題
- セグメント木 (ACL のみ)
- UnionFind (ACL のみ)
- DFS
- BFS
- 01BFS
- ダイクストラ法
- ワーシャルフロイド法
- クラスカル法
心がけたこと
「たくさん問題を解く!」等は既に何度も言われているので、私なりに役に立ったと思うことを書きます。なお、これらはあくまで私個人の考えですので、参考程度に読んでください。
精進の際は教育的問題を解く
ABC 埋め等も大事だと思いますが、AOJ の Course*1 や、こちらの記事にまとまっている問題集など、いわゆる有名問題や練習問題として選ばれた問題などを積極的に解きました。これにより典型力は効率的についたと思います。
早さよりペナを出さないことを優先する
コンテスト中、早さを意識するあまり深く考えずに提出をした結果 WA が出てしまい、さらに焦ってボロボロになってしまうという経験が何度もありました。無闇に書いて投げるのではなく落ち着いて、ミスに気をつけながら解くほうがコンテストの結果は良かったです。
コンテスト中は精一杯解く
私は例えば ABC において、D が解けたあと気が緩んでしまい、「もういいか。E は無理かな」みたいな思考になりがちでした。ABC-D が碌に解けなかったころの感覚が残っているのだと思います。しかし実は E も考えればわかる問題であった、などということも多く、このような思考に陥るのは勿体ないです。E や F も解く気でしっかりと考察することで、5 完や 6 完を達成することも多くなりました。
これからの目標
とりあえず誕生日 (2023 年 6 月) までに AtCoder 青色を目標にします。そのために、
- UnionFind を自分で実装
- セグメント木 (遅延評価も) を自分で実装
- フロー
- よりレベルの高いゲーム問題 (Grundy 数等)
- struct 関連に強くなる
- 幾何
あたりを履修していこうと思います。(特にセグメント木実装とフローは頑張ります。) また、入水したらやろうと思っていたヒューリスティックにも挑戦していきます。
おわりに
正直、まだ入水した感覚が掴めていないです。競プロを始めた当初は遥か遠く思えた Rating 1200 という場所に到達できたということを考えると、なんだか感慨深いです。そもそも、自分がここまで競プロを続けられということが予想外でした。何はともあれ、さらなる高みを目指して、今後も取り組んでまいります。
稚拙な文章でしたが、最後まで読んでくださりありがとうございました。
*1:すみません、今見返したところ AOJ はあまり埋めていませんでした。