AtCoder 水色になりました
AtCoder 水色になりました。
ということで、簡単に振り返りで、モチベーションについてと、精進してきたことを書き残しておきます。 精進部分については緑や水色を目指す方の参考になれば幸いです。
まずは簡単な自己紹介です。
- 社会人です。
- 修士卒です。一応数学科にいて、途中から統計学の方へシフトしました。
- SIer です。業務でコードは書いてません。
- AtCoder 初参戦は2019/11 本格参加は2020/03 です。
- PAST は第3回、第5回ともに中級です。
モチベーションについて
色々な方が竸プロのモチベーションについて書いていたりしますが、私の場合はレートです。完全にオンラインゲーム感覚です。 昔から結構オンラインゲームにハマっていて、そのゲームでのウデマエ(=レート)を上げるのが楽しいんですよね。竸プロの場合、ウデマエはアルゴリズムの理解と応用力でしょうか。一目見て解法が思い浮かぶ人は本当にすごいと思います。
直大さんのブログでの色の説明や、E8さんの記事を見るとおおよそ水色が竸プロerにおいては中級者なのかなと思い、2020年中に水色を目指してプレイしてました。5ヶ月ほど遅れてしまいましたが、水色になることは達成できました。
精進方法について
今までにどういう方針で何をやったかを前半で、問題を解くときにやっていたことを後半で記載します.
どういう方針で何をやったか
目標の色レート帯になるには、なりたい色のパフォーマンス値を取る必要があります。パフォーマンスはコンテストの出来で決まりますが、「自分と同じレート帯が解ける問題を早く解くこと」、または「自分と同じレート帯の人が解けない問題を解くこと」で高い値を得ることができます。
よって、精進の方針として、「見た瞬間わかる」くらいになること(数の暗黙知？)と、「自分にとって難しいと思える問題を解けること」の二軸で進めることにしました。
さて、水色を目標としたときに、水色においての基礎知識を E8 さんがまとめた記事があります。精選100問です。こんな素晴らしくまとめてくださった記事を使わない手はないと思い、最初はこれに取り組み始めました。
しかし、DPは全く理解できず、、自分にとってわかりやすそうなものと出題頻度をみて、優先順位を決め、精選100問のうち以下の内容を先に取り組みました。
また、上記がわかったつもりでもコンテスト中気づけなかったり、解ききれないことも多く、そもそも竸プロの問題に慣れる必要があると思いました。そこで、AtCoder Problems の bootcamp を使います。 Atcoder Problems では、Beginner 向けに bootcamp 300問が用意されてます。これの easy 2 問、medium 2問、hard 2問の計6問のバチャを作ってやってました。
これらを解き切った頃には緑色に到達し、レートも1000越えしていたと思います。ちょうど2020年の11月ごろで、半年間はかかってます。 その後はだいぶ問題に慣れたので、精選100問の中級編の余りと、上級編でコンテストによく出てくるものを一旦さらっておくようにしました。以下が取り組んだ内容です。
- DP(ナップザックDP、区間DP、bitDP、LIS)
- ワーシャルフロイド法
- 最小全域木の構成法(クラスカル法)
- 座標圧縮
- 半分全列挙
- 平方分割
- Binary Index Tree
- セグメント木
- 遅延評価セグメント木
他に、コンテスト中に知っておく必要があるなと思って調べたことです。
- エラトステネスの篩
- 桁DP
- 確率DP、期待値DP
セグメント木などは、自分で実装してみたりしたものの、使えるようにするだけで一週間くらいかかってました。 これらを履修した後でも相変わらず緑でした。おそらく周りの方々も精進し続けて、全体のレベルが上がっているのでしょう（そう思いたい）。
上記全て取り組み終わったのがちょうど2021年2月くらいです。それ以降は水・青diffを時間が取れそうな日に取り組んでいましたが、コンテストでDPがまだ解けていなかったため、あんまりやりたくなかった Educational DP Contest に取り組みます。
現状まだ取り組み途中ですが、ちょうどABC201のD問題が水diffのDPの問題で、このおかげ？で色変することができました。 引き続き EDPC に取り組み、そのあとは上級編の残り、典型90問 と ACL に取り組もうかと思ってます。
ここまで、やったことをまとめるとこんな感じです。
- (灰~茶 のとき) 2020/03 ~ 2020/05: 精選100問 中級編 （全探索、DFS/BFS、累積和、unionfindあたり）
- (茶~緑 のとき) 2020/05 ~ 2020/11: AtCoder Problems Bootcamp for Beginner 300問
- (緑後半のとき) 2020/11 ~ 2021/02: 精選100問 中級編のこり、上級編一部
- (最近) 2021/03 ~ 2021/05: 水青埋め、EDPC
問題を解くときにやっていたこと
よく議論になる点について私の考えを書いておきます。
- 解説をどのタイミングで見るか？
解説を見る前に10〜30分は自分の頭で解法を考え、計算量を見積もって、イケそうなら実装するまでやったほうがいいと思います。そうするほうが記憶に残りやすいのと、「自分の考えた解法がなぜダメなのか」を考えることができます。これは間違った解き方において反例を出す能力が向上すると思います。
解説をさっさとみたほうが効率的な気もしますが、結果的に記憶に残る方を選んでやれば良いと思ってます。
- Streak を切らさないほうがいいのか？
一時期 Streak を切らさないようにしていましたが、切らさないようにABCのA問題を解くなどした時期もあり、いい面も悪い面もあるかなと思います。
難しい問題に取り組んで Streak を繋げようとすると、一日で解けない場合や、WAが出て焦ったりして精神衛生上良くないことが私にはあったので、コントロールが難しいですね。
問題を解く週間をつけたいとか、問題に触れる時間がなくなってしまった時に、無理矢理時間を作る意味で取り組むのがいいかなと思ってます。
終わりに
振り返りで色変記事を書いてきました。他の方の精進の参考になれば嬉しいです。 これからもウデマエを上げて、青を目指していきたいと思います！
