Atcoderで青色になりました。

 こんばんは。先日のARCでレートが無事1600に到達したのでブログを更新する次第です。

f:id:tempura0224:20180412144919j:plain

水色から青になるために必要だと思った知識とかをまとめられるとよいのですが水色から青までで通した問題が5問(文字列、数学、算数(偶奇)、数学、貪欲)だけなのでただただ自分語りをするだけの記事にしようと思います。

 ということで「Atcoder 青色」とかで検索してこのブログに来ちゃった人は閉じちゃってくれて大丈夫です。僕の生い立ちが見たい人は見ていってください()

1月

 僕が競技プログラミングを始めたのは今年の1月からでした。新年特有の意識高い瞬間の思い付きでAtcoderに登録しました。で、薦められるがままに蟻本と螺旋本を買い、Atcoder Problemを開いたあたりでそもそもプログラミング経験が皆無なことに気づきました(は?)。幸いにして冬休みで時間だけは腐るほどあったので

 問題(A,Bあたり)を見る→何をすればいいかはわかる→書けない→人のコードを見る→初見の関数をググる→すげえ→自分も書いてみる→バグる→つらい→直る→嬉しい

 の繰り返しで知識を増やしていきました。間違いなく正しい学習方法ではないです。で1/7にABCデビューを果たしてなぜか全完をしてしまいました。D問題が貪欲で解ける問題で知識がいらなかったというのが理由なんですがこれで調子に乗り、そこからは蟻本を読んだりABCの過去問(C,Dあたり)をばしばし解いたりしてました。

使った知識:BFS,DFS,ワーシャルフロイド,二分探索,累積和,DP(1番基本的なタイプ),BIT

2月

 2/4のAPCで緑になりました。ABCのCまでは安定して解けるようになっていたのと過去問ではDもだいぶできるようになっていたのとでARCに移りました(が本番中はなかなかDは解けませんでした)。こどふぉやCSAにも参加するようになり生活が壊れました。

使った知識ダイクストラ,Union Find,累積和(2次元imosとか),桁DP,行列累乗

3月

 こどふぉで惜敗を繰り返したりAtcoderに虐殺されたりCSAで黄色タッチにことごとく失敗したりと絶妙に噛み合わない月でした(つらい)。競プロも競技である以上こういう期間もあるんだなぁと勉強になりました。それでも何とか3/25のARCで水色になりました。

tempura0224.hatenablog.com

使った知識最小全域木,フロー(最大流とか2部マッチングとか),区間DP,木DP,LIS

4月

 4/7のARCで青になりました。大学院生活が始まってしまったりで海外コンテストを見送ることが多くなってしまって悲しい。精進も滞りがち。

おわりに

 「使った知識」はコンテストだったり過去問埋めだったりで1回でも使ったものを書き出しただけなので必ずしも使いこなせるわけではないです(おい)。学習の順番も必要になったものから順番に、みたいな感じなのでところどころ非常識だったりしますがこれくらい身に着ければアルゴ的には十分なんだなぁくらいの参考になれば嬉しいです。

 これから黄色を目指すうえではデータ構造に弱すぎる気がするので個人的にはその辺を強化していけたらいいなぁと思っています。「黄色になりました」を書ける日が少しでも早く訪れますように。