こんにちは！つちのこです。折角AtCoderで青色になったので、色変記事を書きました(記録になるので) 色変記事の自己紹介や精進方法は本当に自己満足に近いと思いますが(そこらへんは十人十色なので)、身に付けたアルゴリズムやデータ構造等は青を目指す方にとって参考になると思うので、是非読んでくださると嬉しいです！
1.恒例の？自己紹介タイム
といっても特に書くことないんですよね、スペックとしては始めた時点でプログラミング完全未履修、数学は高校数学までは少しだけわかるくらいの感じでした。
折角なので、競プロを始めたきっかけについてでも書いておきます。大学受験期に競プロの存在を知って、単純にゲームとして面白そう！と思ったのがきっかけです。全くプログラミングはできない一からのスタートでしたが、APG4bのお陰でc++の書き方を学んでいき、どんどんハマっちゃいました。 ちょうど初めて4ヶ月と少しで最初の目標であった青コーダーにまでなれたのでよかったです。
2.身に付けたアルゴリズムやデータ構造
昔緑コーダーになった記事を出したんですが、それから沢山増えちゃいました。今使えるのはここらへんです。
- DP、桁DP、bitDP(やや怪しい)
- 最短路(ダイクストラ、ワーシャルフロイド、ベルマンフォード)
- 最小全域木(クラスカル、プリム)
- union-find
- BIT、抽象化再帰セグ木
- Mod演算(modintクラスを作りました)
- ローリングハッシュ
- LCA
- トポロジカルソート
あれ、実は全然ないですね、、、思い出したらその都度追記していきます(ごめんなさい)もしこれは知ってるでしょ、とか青コーダーならこれは最低限使えた方がいいよ！っていうのがあれば是非教えてください。
それぞれについて一言コメントも書いちゃいます。
まずDPですが、青コーダーを目指すならある程度出来た方がいいです。EDPCがかなり良い教材なのでおすすめです。
最短路は時々使います。そこまで難しくも無いので早めに使えるようになると良いかも？
最小全域木はクラスカルでもプリムでも基本は良いですが、クラスカルの方がわかりやすい気がしました。
union-findはまあご存知の通りですね。構造体の中でもかなり作るのが平易なので、緑くらいになったら自作してみるといいかもです。
BIT、セグ木はAtCoderのコンテスト中にはほぼ使ったことがないですが、かなり便利なので持っておくと便利です。セグ木は非再帰の方が早いらしいのでこんど作り直したい、、
Modintはあると実装での事故が減り、簡潔にコードを書けるようになります。メリットがかなり大きいので勉強する価値はありそうです。
ロリハは使うと非想定だけど解ける問題がそこそこあるので、凄い子です。ハッシュの衝突には注意です！
LCAは実は使ったことが無いので何も言えません、、
トポロジカルソートはコドフォで一回使ったくらいですかね、割とわかりやすいので水くらいになったら覚えても良いかもです。
3.精進でやったこと
AtCoder上で900問くらい解いたみたいです。緑になった時が500ACだったので、およそ1.8倍くらいですね。私はそこそこ解説ACに頼っちゃうタイプなので、多分2割くらいは解説ACしています(もちろん、時間をあけて自分の力でACはしています)。
これはいろんな人が言ってることなんですけど、精進や問題を解くのにはいろんな種類があって、例えば低難易度を早く解く練習をすると、コンテストでめちゃくちゃやらかして3完茶パフォだった。。。みたいな事故を減らすことができます。逆に高難易度にじっくり取り組む訓練をすると、時々難しい問題が解けて高いパフォが出たりします。あとは、例えばめちゃくちゃ昔のABC-Dなどは典型の塊なので、割とすぐに解説を見ちゃっても典型力を身に着けることができます。精進も惰性で続けるんじゃなくて、何を目的に精進をやっているのかその都度明確に考えながら行うのが、実力向上のためには非常に大切な気がしています。
ところで、最近はCodeforcesのバーチャルコンテスト機能を割と良く使っているのですが、フォロワーさんと競えたり初見の問題に沢山取り組むことができるので、力をつけるにはかなり有用な気がしています。今後もバチャは精進に取り入れていきたいなーって思ってます。
4.終わりに
いつもフォロワーさんには色々と教えていただいたりバチャ並走していただいたり大変お世話になっています。年内黄コーダー目指して頑張る予定なので、何卒今後もよろしくお願いします！！
