season's quarterly

数学/物理/プログラミング

AtCoderで青色になるまでにやったこと

先日のABC168で念願の青になりました。いえーい。


f:id:season1618:20200518113200p:plain
変色記事を書くのはこれが初めてだし、色々語りたいので語ります。

目次

  • どんな人
  • 競プロを始める前
  • 競プロを始める
  • 緑になるまで
  • 水になるまで
  • 青になるまで
  • 感想

どんな人

県立高校の理数科三年です。パソコン部の部長をしています。実績は、PCKとかJOIの本選にいたりしました。数学と物理とコンピュータが好きな人です。
season1618.hatenablog.jp
season1618.hatenablog.jp

競プロを始める前

中学の頃はずっと数オリの勉強をしていましたね。なので競プロを始めた時点で必要な数学的知識（ユークリッドの互除法、エラトステネスの篩、フェルマーの小定理、逆元など）は大体揃ってました。なお、数オリの勉強はしていても数オリには出ませんでした（最初に出たのは高一）（はあ？）。
プログラミングを初めてやったのは中一の時です。Javaでシミュレーションとかを作ってました。その頃からTwitterは見てたけど競技プログラミングという言葉は聞いたことがなかったです。実は科オリつながりで情報オリンピックの問題を覗いたことはあるのですが、なんじゃこりゃという気持ちになりました。（後にJOIの本選に出場するとは夢にも思わなかった。）

競プロを始める

競プロを始めたのは高一の11月です。その時期に、情報の授業でプログラミング（Excel VBA）をやってました。出された課題は全て一瞬で解いていたので、先生にパソコン部に来ないかと誘われました。放課後にパソコン室に行くと、そこでpublic_yusuke (@public_yusuke) | Twitterさんと会いました。ナチュラルに数学基礎論の本を持っていたり、タイピングが早かったりと結構衝撃的だった。その日に競技プログラミングのことを教えてもらって、いくつか問題を解きました。
f:id:season1618:20200518120507p:plain
（考察だけやって実装はほとんど先輩にやってもらいました。）考察だけとはいえ水diff下位の問題をACしているので、この時点で緑くらいの実力があったのではと思う。

緑になるまで

Javaしか知らなかったのでAPG4bを履修しました。ここでは単純な制御文とか配列、関数を覚えたようです。この時はまだ自分の気持ちをコードに反映できないことが多く、STLとかデータ構造とかは他人の提出を見て学習していました。最近のAPG4bならその辺もカバーしてるんじゃないかな。
f:id:season1618:20200518121836p:plain
初めて出たコンテストはこれですがUnratedでした（問題の不備とかではなく、最初からUnratedだった）。
（当時）レーティングが付くと聞いていたのになぜ？よく見るとrating対象が-になっているな。レーティングが付かない回もあるのか。
（現在）Unrated、めちゃくちゃ珍しいじゃねえか。運が悪すぎる。
48分で2完してました。
f:id:season1618:20200518122149p:plain
次に出たのがRaredでした。なかなか良いパフォを取っています。
自分が緑になった頃はあんまり知識は必要なかったのですが、最近だとABC4完するためには
アルゴリズム

  • 全探索、bit全探索
  • 貪欲
  • 累積和、尺取り法
  • 単純なDP
  • DFS、BFS
  • 累乗の計算(繰り返し二乗法)

数学

あたりを身に付ける必要があると思います。あとC++のデータ構造(map, set, pair, queue, deque)も身に付けると良さそう。知識をあまり必要としない問題でも、数学的な思考を要求されるみたい。
f:id:season1618:20200518134620p:plain
2月に緑になりました。

水になるまで

新たに習得したのは

  • 二分探索
  • ダイクストラ、ワーシャルフロイド、(ベルマンフォード)
  • 高度なDP
  • トポロジカルソート
  • 二部グラフ判定
  • Union-Find

などです。ABCを30分くらいで4完できると大体水パフォが出ます。
f:id:season1618:20200518135851p:plain
始めてから半年ほどで水になりました。旧ABCの内に水になれたので嬉しかったです。一旦緑落ちしたのですが、その後は安定して水パフォが取れるようになりました。この頃に競プロのTwitterアカウントを作りました。

青になるまで

ここから長い停滞が始まります。PCKやJOIの本選には出場しましたが、水の中間である1400に到達したのも12月になってからでした。3月初めには一気に1300にまで落ち込んでしまいます。本格的に精進を始めたのは4月の初め頃です。以下の内容は自分の所感なので、ほどほどに参考にしてください。

モチベーションの保ち方

レーティングにこだわるよりは問題を解きたい欲を重視していた。

取り組む問題

例えば水上位なら水diffが大体解けて、青diffが少し解けるくらいの実力だと思います。なので自分の色と同じか一つ上の問題に取り組むと良さそうです。自分も早解きよりは根本的に実力を上げたかったので、主に水diff、青diffの問題を解きました。たま～に黄diffが解けます（うれしい）。あと虚無埋めはしませんでした。

問題にどれくらい時間をかけるか

少なくとも30分は考えてると思います。長い方だと3時間くらい。コンテスト中はそうもいかないけど、趣味なのでゆっくり考えた方が楽しいです。自分に解けない問題が解けると楽しいので。数時間で解けないときは諦めます。数オリの勉強をしていた頃は、解説のある問題が少なかった（というかどこに載ってるか知らなった）こともあり、1,2週間くらい考えてました。解けない間の二週間はずっと鬱状態なのですが、解けるとめちゃくちゃ嬉しいです。ただ長考する習慣はつくけど、これはさすがに効率が悪くて、もっとやりようがあったなあと反省してます。

解説を読むとき

分からない問題の解法には次のパターンがあると思います。

まず知ってるアルゴリズムだったとき。知ってるのに解けないことありますよね（あります）。そういうときは解法のリストを作成しておくと良いと思います。リストに「二分探索、左右から累積和、単調...」的なことが書いてあって、これ二分探索で解けるじゃん！！、とか。
知らないアルゴリズムならある程度仕方ないので、その機会に勉強しました。
3番目はどうなんだろ...経験以外に思い付かないです。
あと解説ACはしませんでした。AtCoder Problemsに色がつくのが嫌だったため。

知識

水色と必要な知識はあまり変わってないと思います。青diffは数学問が多い印象だったので。Segment Tree, BIT, フローとかは使いませんでした。でも問題を解くごとに知見は得られるので、そういった経験が貯まった感はあります。

精進の様子

f:id:season1618:20200518155659p:plain
f:id:season1618:20200518155740p:plain
f:id:season1618:20200518160209p:plain

というわけで自分の所感でした。

感想

たぶん弊学初の青コーダーなので嬉しい。今年の目標の一つも達成することができました。