AtCorderで水色になりました!
先日開催されたAGC033にて、念願だった水色にようやくなれたので*1、皆さんに倣って振り返り記事を書きたいと思います。*2
ちなみに、AtCorderで水色はどんなもんかというと↓みたいな感じです。(悪用)
AtCoderで水色って、思ってたよりすごいのか?水色以上なんてツイッターにはぞろぞろいるからそんな感じしない。はやく水色なりたい。
— tobiuo (@tobiuo1990) April 10, 2019
『水色以上の方はGoogleに入れる可能性が充分にあるといっていい』https://t.co/S79pxomrkJ
期間
初ACは2018/11/21なので、165日(5.5か月)で水色になれました。
当初思っていたよりも時間かかりました。というのも、1200くらいのパフォーマンスは割とすぐ出たので、すぐにレートも1200は超えると思っていたからです。実際にはそんなに甘くなく、目標レート相応のパフォーマンスを継続的に出す必要があることを思い知りました。
やったこと
- 1日1AC
- 時間があるときは蟻本読んで新たなアルゴリズムやデータ構造を学習
- ライブラリ作成
- 重点的なテーマ対策
1日1AC
蟻本を購入した後(競プロ初めて2~3か月目くらい)、新たな知識の習得やライブラリの作成などに取り組んでしまい、問題を解くことをおろそかにしていた時期がありました。そうすると明らかにレートが停滞してきて、初めてレートが減少したりABCで2完しかできないことが続いたりしました。(たまたま自分の能力的にここで一つ壁があっただけかもしれません。)
2回連続でABCのCがコンテスト中ACできなかったので、蟻本とかで新たなデータ構造とかアルゴリズムを習得するのを一時中断して、ABC040からC問題を一通り解き始めた。
— tobiuo (@tobiuo1990) February 28, 2019
とりあえずABC040,041は5分くらいでACできた。この差は何?
今と昔の難易度の差?
本番に弱い?
前者な気がしてる
そこでまずはABCのCを解けないと水色は厳しいよなと思いなおし、Cをとにかく埋める、できるだけ毎日ACするようにしたところ、ABCで初めて全完できました。
ABC120
— tobiuo (@tobiuo1990) March 3, 2019
全完(初!)
rank:630
perf:1406
通算
rank:5727
rate:986(+76)
全完してもパフォ1600出るわけではないのか。
今回パフォ1600だすためにな順位413位以上、1時間以内で全完が必要だったみたい。
次も全完できるようがんばろ。
また、以下のような言葉をふと目にすることがありました。
読む力、それは新たな学力を獲得していくための前提条件であり、その意味で「学力の上限を規定するもの」と言うことができます。
また書く力は、獲得した学力を定着させる主要な手段であり、「学力の下限を規定するもの」と言えます。*3
上記の引用は競プロにも当てはまると思っていて、蟻本を読んで新たな知識を習得したりするのは、上限を上げている、と言えます。一方で、問題を解くというのは、すでに習得した知識を実際に使えるようにしている(必要な時に適切に使える確度を高めている)ので、下限を固めている、と言えます。上限ばかりを上げても下限が低いままだと安定してパフォーマンスを出せず、レートも順調に上がっていかないと思うので、継続的にACしていくことは最初は重要だと思います。
いまでは必ず毎日1ACはするようにしています。旅行に行くときなども、事前にいくつかストックして毎日提出する、というようなこともやっていて、これは完全に目的が手段化しています。が行けるところまでstreakを伸ばすというのも現在の競プロの楽しみの一つになっています。
蟻本読んで新たなアルゴリズムやデータ構造を学習・ライブラリ作成
今のところ、ようやく初級編を読み終わったところです。
進め方としては
蟻本を読む(1節)⇒ ライブラリ化するようなものであればライブラリ作成 ⇒ 関連問題をいくつか解く
を繰り返しながら進めました。関連問題についてはこちらを参考にしています。(AtCorder入門時からずっとお世話になってます。ありがとうございます。)
作成済みライブラリは以下の通りです。
- グラフ生成(重みあり・なし。隣接行列。)
- グラフの最短距離を求めるアルゴリズム(ベルマンフォード、ダイクストラ、ワーシャルフロイド)
- 最小全域木(クラスカル)
- Union-Find
- GCD/LCM(ユークリッドの互除法)
- 順列組み合わせ(フェルマーの小定理)
結構作成したつもりだったけど、列挙してみると少ないですね。これからもっと充実させていきたいです。
重点的なテーマ対策
冬季休業とかで時間が多めにあるときに少しやりました。
とは言ってもやったのは、DPとグラフをちょっとまとめてやったくらいです。
競プロやってよかったこと
- コンテストに参加すると楽しい
- 新たなアルゴリズムやデータ構造を習得するのが楽しい
- その他色々
コンテストに参加すると楽しい
さまざまな理由で競プロをしている人がいると思いますが、自分の場合はこれです。コンテストに参加して自分が解けるか解けないか微妙なラインの問題をなんとかして解けたときは嬉しいし、解けなかったときは悔しいです。
あと、コンテスト後に競プロerがワラワラと悲喜交々つぶやいていくのを眺めたり自分もつぶやいたりするのも、楽しみの一つです。
新たなアルゴリズムやデータ構造を習得するのが楽しい
まだ初歩的なものしか習得出来てないですが、新たに習得するたびにレベルアップしたような感じで、楽しいです。また、普段使用しているプログラミング言語の標準で用意されている関数(ソートとか)についてもただ使うだけでなくて、どのようなアルゴリズムで実装されているのか気になって調べたりして、言語自体にも少し詳しくなれました。
これから
次はもちろん青を目指します。自分が努力しても青が精いっぱいかなという感覚ですが、まずは青になってみないとそこらへんは分からないので、何はともあれ青になってみたいと思います。なんとか2019年中に青になれるように頑張りたいです。
そのために、蟻本の中級までは習得したいです。あと400~600くらいまでは埋めたいです。(レート1600は、配点500を半分くらい解ければいいらしいので、600くらいまで埋められれば青になれるはず?)streakも継続して伸ばしていきたいです。
楽しみながら、コツコツと精進していきます。