naoppyです。4/21にAtCoderで水色になることが出来ました。 一つの節目として、やってきたこととかをまとめます。
レート変移
これを見てわかるのは、まあ僕に特別な才能や強い考察力がないことぐらいでしょう。
31回も参加してます。
水色時点での自分
実力と言っても色々パラメーターがあるので、難しいですが、僕のスペックを並べます。
- プログラミング歴1年、Java使い
- 競プロ歴は始めたのが去年(2017)の7月中旬、それなりに本気でやり始めたのが12月ぐらいです
- 1月ごろに300点問題は完全に安定、水色になった時点で400点が半分解けるぐらいの実力
自己紹介かよ
使えるアルゴリズムとテク
- 一次元累積和
- エラトステネスの篩
- 最小公倍数と最大公約数
- bit全探索
- BFS
- DFS
- 二分探索
- UnionFind
- 重み付きUnionFind
- ワーシャルフロイド
- ダイクストラ
- ベルマンフォード
- nCr
これだけです、こうして見ると少ないですね。 僕は何をしていたんだ
ちなみにDPはできません！！！DPできなくても水色にはなれます。
ただDPの考え方は知っておくべきかもしれないです。
Twitterがやめられない
何度ツイ禁しようとしても辞められません。 ひたすらに時間が吸われます。
結局ツイ廃状態のまま水色になれましたが、青になるにはそれなりにTwitterから離れた方がいいのは自明です。
精進方法
AtCoderProblemsで過去問を解く
誰もが使っているであろう AtCoder Problems
水色になった時は殆どABCしか埋めていませんでした。
ABCのCは80%、Dは23%ほど埋めていました。
TwitterのDMで優しい人に聞きまくる
普通に迷惑なのですが、優しい方に詰まっている問題の考察過程などを教えていただきました。 感謝しかありません。
まあこんな具体的なこと書いても誰の参考にもならないのでまとめると、優しい人(そこら中にいるはず)に特に考察過程を聞きましょう。
考察力は自分ではなかなか伸ばしにくいスキルです、精進への近道だと思います。考察力は大事です。
チーター本を読む
蟻本、チーター本等を読みましょう。チーター本は特に初心者におすすめです。
ちなみに蟻本は持ってないので、どなたか買ってくれる人を募集中です。
スライドやQiitaの記事を読む
学びたいアルゴリズム、解説を見たら知らないアルゴリズムだったときは、アルゴリズム名でググりましょう。
強い人のスライドや記事がでてくるはずです。ありがたい...。
思いつくのはこれだけですね、人によってはバチャったり教育的良問を教えてもらって解くなどしているみたいですが、僕はしませんでした。
解くときのテク
まず問題文をよく読みましょう。ある程度アルゴリズムを知っていると、問題からどのアルゴリズムを使えばいいかというのがぱっとわかる問題は多いです。
例を出すと、
平面上での迷路→BFS
頂点を結ぶ→グラフ系のアルゴリズムかDFS
Yes、Noの明確な境界がある→二分探索
などですかね。
もしあからさまな典型がでればライブラリをコピペして終わりなのですが、それ以外の時、どうすればいいかというと、まず計算量を推測します。
nlogn、nなら通るけど、n2は通らないな...、など、ある程度分かれば大丈夫です。
次に、問題のネックとなっている部分はどれか(そこさえわかれば解ける場所)を自分の中でしっかり把握します。
そして
制約が簡単な場合を考える、そこから発展させる。
サンプルを手でシュミレーションしてみて、自分が考えた過程をそのままプログラムに落とす
式を立てて、変形させる
サンプルから、規則性やルールを探し出す
などをすれば、きっとACできるはずです(自己暗示)
まとめ
DPできなくても大丈夫。
海外コン出たこと無くても大丈夫。(無論出た方がいい)
ずっと早解き3完でも大丈夫。
ツイ廃でも多分大丈夫。
これを見て、「俺でもできそう」となれば幸いです。
