競プロをしながら、節約と株式投資でセミリタイアを目指す東大卒のブログ

東大卒でメーカー勤務の私がセミリタイアするために投資や競プロを頑張っていこうという趣旨で始めたブログです。独身男性です。お金の大切さや今後の生き方も併せて伝えられたらと思います。

競プロ初めて1年経ちましたその2~茶色を脱却する8か月~

おはようございます。しほみんです。

 

昨日の続きで茶色の時の話をします。

結論を先に行っておくと、

茶色を抜け出すには、

・D問題(簡単であればE問題も)までを丁寧に復習して解けるようにする。

・その時にアルゴリズムをきちんと学習する。実装は必ずする。

・あとは実際の制限時間内でちゃんと解けるようにする。(早く解けなくてもD問題まで実装できるなら十分緑にはなれる)

・あきらめない(とても大事だと思う)

これを繰り返し実践することでできます。

 

昨日の話はこちらです。

 

www.yuriyurusukejasmine.work

 

 

 

レートの推移です。

f:id:yuriyurusuke:20200601224630p:plain

 

 

茶色入ってから600になるまで

ここでは600に入って安定的になるまでは、さらに3か月かかっています。

このレベルだとC問題が安定的に解けて、D問題が解けたり解けなかったりですね。

ここらへんから安定的にC問題が解けるようになってきたので、アルゴリズムを勉強し始めた感じです。

 

問題中でできるようになったこと

・二分探索

・1,2個の組み合わせの数の求め方

・動的計画法の本当に簡単なもの(数列的なもの)

・簡単な全探索

・数学的に解く問題(三角関数など)

・頭から決めていくようなfor文

・超簡単な計算量の見積もり(Nの3乗はたぶん厳しい...けど方法はわからない的な)

・独自関数を作り二変数処理をする

 

多分この程度です。どっちかというと数学的な要素でここまで上がってきました。

ここでようやくプログラム的に処理をしていくことを学び始めたって感じです。

 

時間中に実装できていないこと

・貪欲法

・尺取り法

・BFS

・DFS

・データ構造的処理(Union-Find法とか)

・priority queue

・queue

・桁DP

・bit全探索

・二項係数を求める

・根付き木関連

・ワーシャルフロイド

・ダイクストラ法

・プリム法

・zアルゴリズム

 

ここら辺は実装も難しく理解も浅かった感じです。というかここら辺がわからないのに問題挑んで解いていくたびに理解していたので、茶色の後半に無事たどり着くのが遅かったってイメージでしょうか。(ここら辺の理解を深めると正直緑まではあっという間な気がします。)

 

600から緑になるまで

ここが結構長かったです。5か月間もかかってますし...

 

具体的にやったことは単純で、上のできないことをほとんど実装できるようにしました。多分、priority queueとBFS、ダイクストラ法、プリム法、zアルゴリズム以外はきちんと理解してライブラリを作成しました。ただ、この時期でもグラフ問題はほぼ捨ててました。

 

あとはこいつらを適切に使えるようにしてました。(これが結構ムズイ)

方法が適切でも細かいミスで解けないこともあったりして、苦労は多かった記憶があります....。

 

時間かけているのになかなかレートが上がらず苦しかったです。ただ、気持ちとしては、一度は解けなくてもよい。しかし今度似た問題が出たら絶対にACするぞって気持ちで復習と勉強をしてました。

 

その結果なのか微妙なレートも徐々に上向いてようやくパフォーマンス900-1000程度を重ねて、緑にたどり着くことができました。

 

最後に...

ぶっちゃけ茶色から緑ってよっぽどできる人じゃなきゃ結構な試練だと思います。

しかし、とにかく復習による学習と実際の問題への適応の癖を身に着ければ、おのずと上がっていけるといえます。

地道に努力していけばいつかはたどり着けると信じてやるのも大事かと。

 

明日は緑になったのでその維持と今後どう上げていくかを話していこうかと思います。

ではでは。