競プロ N色になるまでにやったこと

 はじめまして。mokoというたこ焼きです。でもアイコンは鴨です。

 今日はタイトル通り私がN色になるまでにやったことの記事を書きたいと思います。

 N色とは言え、水色で数カ月間停滞しているので4色しか無いのですが...。 

 

- 灰色 -

 8月末です。競プロを始めました。

 折角なので初参加のコンテストの結果でも書きましょうか...。

 えーっとですね...ABCで100-200の2完でした。300が通せなかったらしく...。 それまで自分で考えてプログラムを書いたことがほぼ無かったことを思えば当たり前ではある気がしますが...。

 この初参加ABCの次のコンテストがAGCだったのですが、当時の私はABCとAGCの違いがわからずにとりあえず出て 300の1完でした。このAGCまでが灰色です。

灰色までにやったこと
アルゴリズム
解いた問題例

 やるだけが多いです。

灰色だった期間
  • コンテスト2回
  • 8/20~9/1

 

- 茶色 -

 9月最初のABCで21分で全完してパフォ上限の1600を出し、レートが400以上上がりました。この時は驚きましたね...。直感で書いた400が一発でACして全完してしまったので...。ちなみにABC072です。

茶色までにやったこと
  • JOI過去問の難易度4~5、ABC-A,B,C辺りを解いていました。典型でない問題やちょっと難しめの問題はかなり解説を見ていた記憶があります。何もわからなさすぎたのでw
  • この頃の提出を見ていると、明らかに自分で書いてないだろ、というコードが多すぎて笑えますね。
  • 解説を見ることに抵抗が無かったので(今も無いかも)躊躇せずに解説や他の方のコード見て通していました。
  • 80ACぐらい
アルゴリズム
  • BFSとDFSの違いがしばらくわかりませんでした。
  • 蟻本の動的計画法ぐらいまで読みました。
  • DPが全くと言っていいほどわかりませんでした。
解いた問題例

 自力ACっぽいもの

 絶対解説ACしただろ、というもの

茶色だった期間
  • コンテスト2回
  • 9/2~9/22

 

- 緑 -

 9/23のCODE FESTIVAL 2017 qual A で緑に上がりました。100-200-400の3完、パフォは1400ちょっとでした。 

緑までにやったこと
  • 学校が始まったのであまり精進できなくなりました。
  • JOI過去問の難易度5を主に解いていました。
  • AtCoderの300,400辺りも解いていました。500は難しかったです。
  • 蟻本の初級編を全部読みました。グラフ理論が楽しかったです。
  • 25ACぐらい
アルゴリズム
解いた問題例

 自力ACっぽいもの

 解説ACっぽいもの

緑だった期間
  • コンテスト5回(Ratedは4回)
  • 9/23~11/3

 

- 水色 -

 11月最初の初めて参加したARCでパフォ2000超えを達成し水色になりました!!!いえーい!!!

 D問題が700だったのでC問題の速解きコンだったのですが...無事(?)速解きに成功しレートを爆上げしました。+173とかなってます。

水色までにやったこと
  • JOI過去問の難易度6,7埋め。
  • AtCoderのC,D問題埋め。500点にも手を出すようになりました。幾つか600,700を解説ACしました。
  • とりあえず数をこなそうと思い、わからない問題は積極的に解説を見て通していました。多分数をこなしている内に自分でプログラムを書くことに慣れてきて、競プロの考え方が身についていった気がします。
  • 授業中に考察をしていたりもしました。
  • コンビネーションを勉強しました。
  • 謎なのですが、グラフを使う問題が好きでした。多分DPが致命的にできなかったのに対してグラフを使う問題は解きやすくて割とすんなり解けたからだと思います...。
  • 合計150ACぐらい
アルゴリズム
  • しゃくとり法
  • 二分探索
  • 拡張ダイクストラのようなグラフアルゴリズムの応用
  • トポロジカルソート
  • 強連結成分分解
  • JOI過去問を解いているとトポロジカルソート、強連結成分分解に遭遇したので勉強しました。
  • フローを1,2回書いたような気がします。
解いた問題例

 自力ACっぽいもの

解説ACっぽさが溢れ出てるもの

水色の期間
  • 現在進行形で水色です。
  • 早く青くなりたい。
  • 本当になりたい。
  • 何でなれないんだ←精進しろ

 2018/07/01 (追記) 無事に青くなることができました。

 

- 青 -

 7月1日のARCでようやく青くなることができました。AtCoder初参加から310日です。長いのか短いのかわかりませんね...。

青までにやったこと
  • 私は何故か水色になったのが早かったので水色の期間が長く...やったことと言っても色々ある気がします。f:id:moko_freedom:20180708122249p:plain
  • 水色なりたての11月~2月のJOI本選ごろまではそれまでと同じように精進していました。しかし、2月のJOI本選と高校受験が終わると、スイッチが切れたかのように精進をしなくなっていきます。
  • そしてレート停滞。
  • それが4月ごろから上がりだした...何故でしょう。
  • きっと高校に入って数学をやったからだと自分では思っています。これは感じられている方も多いと思うのですが、やっぱり数学ができる方は競プロでも強い方が多いです。高校に入ったことで中学とは違う数学をやりだして考察力がつき、解法を思いつくようになったのでは、と...。
  • まとめると、青くなったのは競プロの精進をしたからではなく、高校数学を始めたからですね、きっと。(中学受験の勉強をしていたり、学校の進度が速かったり、自主的に数学をやっていたりしなかったので...)
アルゴリズム
  • セグ木
  • 遅延セグ木
  • BIT木?(名前分からず)
  • フロー関係の基本
  • 2部グラフ など.....
  • Githubにライブラリ上げてます。

github.com

解いた問題例
  • 色々です。難易度的にはAtCoderの600ぐらいまでとyukicoderの★3ぐらいまでですかね...。
  • 多すぎて挙げられません...(笑)
  • 1問だけ思い出に残っている問題を。JOI本選前日にセグ木わからなくて焦りながら解いてましたw↓
  • D - タコヤキオイシクナール

 

 

 以上がN色になるまでにやったことなのですが...かなり時間が経っているせいで自分が何をしていたかを見事に忘れてしまっています。一部間違ってるかもしれないです...。

 やったことをあまり思い出せなかったので解いていた問題を多めに載せてみたつもりです。ご参考になれば幸いです。

 

 最近は競プロを全然していません。機械学習の本とかプログラミングに関係ない本とか読んでいたり、言語勉強したいとか思っていたり、言語処理100本ノックやっていたり...。

 

 今の目標は

  • 黄色くなる
  • 水色にならない

の2つです。

 

 最後まで読んでくださり、ありがとうございました。