AtCoder灰→緑までにやったこと・意識したこと
ども、hayaaaaaです。
ABC471で入茶、ABC477で入緑して一区切りついたので、これまでのAtCoder生活を振り返ろうと思います。
自己紹介
- 大学3回生（情報系）
- プログラミングは大学から始めた
- 二分探索やダイクストラなど、有名なアルゴリズムは何となく知っていた
- 数学は好きな方
灰色時代
初参加したのは5月30日のABC460でした。
記録を見るとABC400にも参加していたらしいですが、全く覚えていません。
AtCoderを始めたきっかけは単なる好奇心です。
問題を見た感じ、
まぁコードの書き方さえ覚えれば3か月で入水できるやろw
くらいの気持ちで始めました。
6月あたりは、とりあえず何かやろうということで「鉄則」と「けんちょん本」に手を出しました。
アルゴリズム自体は7割くらい知っている内容だったのですが、当時はコードが全く書けない状態だったので、「これをどうやったら実装できるんだろう」と考えながら眺めていました。
今振り返ると、眺めるだけではなく、しっかり手を動かして進めた方が良かった気はします。
この頃はC++の書き方が分からないことも多く、問題の解法以前のところで苦しんでいました。
コンテストも基本的に2完だったと思います。
7月になると精進の成果もあってか、初めて3完できました。
perfも600以上で安定してきて、「まあこのままいけば入茶できそうだな」という感じでした。
話は変わりますが、このあたりで競プロ典型90問を始めました。
この頃はやる気に満ちあふれていたので、10日間くらいで★4以下の問題を一通り解き終わりました。
期末テストがあるというのに何をしているんでしょうね。
そんなこんなで、8月のABC471で入茶しました。
茶色時代
入茶直後かつ夏休みということで、この時期はかなり真面目に、そして楽しく精進していました。
具体的には、
- 鉄則を最初から解き直す
- 典型90問の★4・★5を進める
- 暇なときにE8さんの記事に載っている問題を解く
ということを並行してやっていました。
どう考えたってやりすぎですね。
この時は無限に時間とやる気があったので、15日程度でこの精進は一通り終わりました。
この時期のAtCoderは、基本的にやればやるだけ成長を感じられたのでかなり楽しかったです。
入茶してからはコンテストで4完することも増え、出るたびにレートが50くらい上がっていました。
初めて水perfを取ったのもこの時期です。
そして、そのままの勢いでABC477で入緑しました。
意識していたこと3選
1. とにかくやる
単純ですね。
最初から高速な解法が思いつかなくても、とりあえずTLEする愚直解を書いてみて、
ここからどうすれば高速化できるか？
を考えるようにしていました。
いきなり正解のアルゴリズムを思いつこうとするより、愚直解からボトルネックを探した方が考えやすい問題も多かったです。
2. 制約を見る
「当たり前だろ」と思うかもしれませんが、意外と忘れがちです。
制約もかなり大きなヒントなので、しっかり見るようにしていました。
例えば、
N, Q <= 2*10^5
なら、少なくとも各クエリについて全要素を見るような O(NQ) は無理そうだな、と考えられます。
逆に特徴的な制約をしている問題なら、そこから解法を予測できることもあります。
この制約ならこの計算量まで
↓
その計算量で使えそうなアルゴリズムは何か
という流れで考えられるようになると、かなり解法を絞りやすくなりました。
3. 典型を知る
累積和、動的計画法、BFS、DFSなどのアルゴリズムには、それぞれよく出てくる問題の形があります。
例えばABC473DはDFSによる列挙の典型例ですし、ABC476Eは区間の最大値・最小値をSegment Treeで処理するタイプの典型だと思います。
ABC476Eは実装がかなり重かったですが……。
こんな感じで典型を知っておくと、問題を見た瞬間に
これ、あのパターンじゃない？
と解法が浮かぶことがあります。
浮かばないこともあります。
それでも、使える選択肢を増やしておくことはかなり重要だと感じました。
意識していたけどできなかったこと1選
1. 確認用出力の消し忘れ
僕がWAしたうちの半分くらいはこれのせいです。
確認用に書いた cout を消し忘れたり、
ここコピペして、あとで変えればいいや
と思った場所をそのまま提出したりしてWAすることもよくありました。
こういうWAをすると、問題が解けないときとは別方向に自分にイライラしてくるので、なるべく避けましょう。
僕も避けたいです。
今後について
もともとの目標は「年内に緑になる」だったので、想定よりかなり早く達成できました。
ということで、これからはいったんAtCoderから離れようと思います。
もしかしたら、ふらっとコンテストに参加することはあるかもしれませんが、今のところ積極的に精進する予定はありません。
これからは、
- 応用情報
- TOEIC
- GCI
- 院試
- 就活
- 研究
あたりに集中します。
今までのサボりの代償ですね。
自分でやると決めたことなので、ちゃんとやろうと思います。
短い期間でしたが、灰色から緑になるまでかなり楽しめました。
またAtCoderをやりたくなったら、そのときは水色を目指して頑張ろうと思います。
では。