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

はじめに

先日ABC167で水色コーダーになりましたので、記念にこの記事を書きます。

AtCoder Scores

f:id:riida:20200524184709p:plain

 

アカウント名、サックスのスペルを間違えていますね。

4月ごろから本業での在宅勤務が始まり、気力・体力に余裕が出ましたので本格的に精進を始めました。

この4~5月でレートが200近く上昇したのはその成果かなと感じています。

(といっても、コンテスト中の点数が上がったというよりは、安定して早解きできるようになったのが実態ですが)

スタート地点での経験

機械工学系専攻で学生時代は数値計算(FEM)の研究をしていました。

指導教員の秘伝のC++ソースに継ぎ足し継ぎ足しで実装していたので、C++とは何たるか体得していたわけではありませんが、vectorやstringといったC++の代表的なライブラリ群に触れていました。流行りのPythonもチョットワカリマス

本職でプログラミングをする機会がほとんどなく、寂しい思いをしていたのが競プロを始めたきっかけです。

モチベーション

  • 緑になるまで(~800)

正直このころは体系的に何かを学んでいたわけではありませんでした。

計算量はどの程度まで制限時間に間に合うか、ということも把握せずに取り組んでいたので、とりあえず何も考えずに二重のN回ループを回していました。

上ぶれのパフォーマンスが出せたときに200くらい上がってなんとかレート800を超えることができました。

精進を真面目にしていなかったことからも、とりあえず週末にプログラミングができればいいやといったところでしょうか。

  • 水色になるまで(~1200)

プログラミング欲が少しずつ満たされてきました。

「作りたいものは特に無い」「でもプログラミングは続けたい」というモチベーションの私にとって競プロはちょうどいい題材だなぁと思い始めたので少し本格的に勉強を始めました。

下記頻出アルゴリズムを学び始めてのもこのころからです。

少しずつ土日の空いた時間や平日の本職後の時間を使って勉強を始めました。

 

学んだこと

学んだアルゴリズムや考え方は下記です。

こうしてみると主に蟻本の2章の内容がほとんどですね。

 

勉強したいこと

  • ローリングハッシュ
  • セグメント木
  • LCA
  • PASTの過去問
  • JOIの過去問
  • Educational Codeforcesへの参加

PASTやJOIの過去問はABCの問題よりも良い教材なんじゃないかと感じているので、じっくり解き進めたいです。

 

青になるために必要だと感じていること

学んだアルゴリズムを素早く、正確に実装する力

緑~水色難易度の問題は典型的な解法のものが多いように感じます。

こうした問題にあまり時間をかけず、きっちりと青diffの問題に時間をかけられるように、ある程度のライブラリ化や考え方の定着が必要だなぁと感じています。

強い人のコードをよく読むこと

ACした=その問題から学ぶことはない

ではないという意識をもって、自分より早く、簡潔なコードを書いている人の書き方を参考にしたいなぁと感じています。

理論的な貪欲法、動的計画法

雰囲気貪欲・雰囲気DPから卒業したいです。