はじめに
いわゆる入水記事。2019/06/15からずっと緑帯だったがついに入水した。以前はコンテスト参加がメインの学習だったが、2度の挫折後にいろいろ改善してパフォーマンスが安定してきたのでメモ。
- 2019年あたりから継続的に参加していたが、2021年に緑帯でレートが伸びなくなり挫折
- 2022年秋から再チャレンジするもむしろレートが下がって挫折
- 2023年秋から再々チャレンジし2024/01/20に水色レート達成！
2022年まではなぜレートが伸びなかったか
2022年のデータを見てみると以下のことがわかる。(濃い緑がコンテスト中に解けた問題。右下に時間とペナルティ数)
- 緑diffが安定していない
- ペナルティが多すぎる
- 水色diffは解けていない
緑diffは解説を見たら理解できるが、コンテスト中に正しい解法に到達できていないことが多かった。また、ペナルティは「証明できていない状態で貪欲法を実装した」というのが多かった気がする。これは知識不足ではなく、問題の考察力不足だったと考えている。以下の精選100問は解いていたので知識はある程度あったはず。問題を別の問題に落とし込んだり、正しい解法を選択するためにはある程度問題を問いて考察力を使える必要があった。
改善結果
2023年のデータを見ると緑diffは安定し、ペナルティは減った。水色diffは試験中に解答に近い方法である程度実装できていることもあったが、相変わらず解けていない。
しかし、スピードが改善されたおかげか(30分程度でD問題を解けていることが多くなった)、直近5回のパフォーマンスはすべて水色以上をキープすることができた。
改善のためにやったこと
解法がわからないとき
たまたま見たこの動画がめちゃくちゃ刺さった。以前は全く解法がわからない問題に対してぼんやりしたまま間違った解法を実装することが多かったが、この動画を見たあとは考察段階で間違った解法は間違っていると判断できるようになったり、エッジケースを事前に洗い出すことができるようになった。
ここで述べられている全く解法がわからない問題の対策は「解かない」、「具体例で考える」、「問題を分割する」。
- 「解かない」 -> 基本前から解いているがAC数が少なそうな場合は後回しするなど。
- 「具体例で考える」 -> 紙とペンでいろいろデータ操作してみる。
- 「問題を分割する」 -> 範囲による場合分けをしたり愚直な解き方で難しい部分を抽出して考えたり。
以下の記事も問題の性質から解法を考えるときにとても役に立つ。
解法を考える順番
間違った貪欲法でよく失敗していたので、「計算量の小さいプログラム」よりも「遅くて正しいプログラム」から始めるようにした。全探索でやったらどうなるか？をまず考える。すると、このクエリに O(log(N)) で答えれたらなぁ とか、このリストの最小値が O(1) で答えれたらなぁという願望が出てくるので、その部分だけ改善すればうまくいくことが多かった。そもそもABCのA、B、C問題は単純に全探索するだけでよいことも多い。
修行
一番大事。正直、コンテストだけ出ていれば水色に到達できるという甘い考えがあったが全く伸びる気がしなかったので以下の記事を参考に「水色到達」 or 「1100問まで問く」にチャレンジすることにした。この再々チャレンジスタート時は解いた問題数が536問。
過去問を解くことはとても重要です。実際に、mencotton さんのツイート によると、800 問解けば 60% 、1100 問解けば 90% の人が水色コーダーになれます。（2020/01/17 時点の統計です） https://qiita.com/e869120/items/eb50fdaece12be418faa
結果としてはAC数850で水色達成となった。(競プロ典型90問の☆5以下 + 緑diffをひたすら解く + コンテスト参加)
緑diffはABCのうち、ABC42以降はすべて埋めることができた。ARCもちょくちょく埋めていたが、ABCと比べて考察が難しいことが多かったため後回しにした。
おわりに
ここ数ヶ月かなり競技プログラミングを楽しんでいたのでAtCoderに感謝。青コーダーを目指す前にAtCoder Heuristic Contestや他の競技プログラミングサイトにも興味があるのでチャレンジしたい。
