AtCoder緑になるまでにやってきたこと
タイトルの通り、AtCoder緑になりました！！！！！！
ということで今回は、(よくある)私が緑色になるまでにやってきたことを書いていきます。
精進量について
私が習得したアルゴリズムなどに触れていく前に、どれだけ精進したかについて書いていきます。
精進量は多くも少なくもないといったものだと思います。
次は精進量の推移についてです。今年に入ってから精進量を一気に増やしました。
今年に入ってからは、ABCのA・B埋めと新しいアルゴリズムの開拓の2つを中心に精進しました。
結果として、ABCのA・B埋めは早解きを安定させた要因の一つになったはず。
開拓したアルゴリズムは直近のコンテストには出てこなかったので今後に期待という感じです。
取り組んできた内容
この部分は所謂、「こんなアルゴリズムを習得した」とか、「このようなテクニックが少し使える」とかを書いていきます。また、テンプレの作成や特定のアルゴリズムを用いる際に参考にしているサイトも合わせて紹介していきます。
その1. 基本的なものであれば取り扱えるようになったアルゴリズム・テクニック
- 全探索(DFS・BFS)
- 順列(next_permutation)
- STLの一部
- 最大公約数・最小公倍数・約数列挙
- 累積和
その2. 理論部分は曖昧だが、何とか取り扱えるアルゴリズム・テクニック
- DP(ナップザックDP・桁DPを含む)
- bit全探索
- MOD演算(逆元を用いたものも含む)
- 二項係数(テーブルを事前作成するタイプのもの)
- ダイクストラ法
- ワーシャルフロイド法
- Union Find
その3. アルゴリズム・テクニック以外で取り組んだ内容
- AtCoderの自動提出ツール
- タイピングの練習
全探索(DFS・BFS)
ここで挙げるDFS・BFSを除いた全探索のレベルとしては、ABC85 C Otoshidamaのような問題をスムーズに実装出来る程度です。
DFS・BFSについては他のアルゴリズムと組み合わせて解く高度な問題を除いた基本的な問題を解くことが出来るレベルです。
例 : ARC31 B 埋め立て, ABC160 D Line++
参考にしている記事
BFS : BFS (幅優先探索) 超入門！ 〜 キューを鮮やかに使いこなす 〜
DFS : AtCoder ABC 119 C - Synthetic Kadomatsu (300 点)
順列(next_permutation)
ABC150 C Count Order で学びました。たまに出てくるので覚えておいて損は無いと勝手に思ってます。
STLの一部
vector, set, multiset, queue, priority_queue, pairなど使えます。二部探索のlower_bound, upper_boundはつい最近知ったばかりなので扱えないです...
最大公約数・最小公倍数・約数列挙
これは他の人のテンプレを参考に
私のテンプレなどは最後にリンクを載せていますので気になったら見て(より効率化して)いただけると助かります。
累積和
階乗計算だったり色々なところで計算量落とし役として私の中では活躍しています。
後に紹介するDPの基礎(らしい)ので抑えておくべきポイントだと思ってます。
DP(ナップザックDP・桁DPを含む)
DPはかなり練習しました(それでもあまり満足に扱うことが出来ない)。
DPまとめコンテストではF問題までは普通に解けるレベルです。
桁DPは2つほどテンプレを用意しつつ理論部分も(他のアルゴリズムよりかは)勉強したのである程度は扱えるようになったと思います。
以下は何とか解ける例
ナップザックDP : ABC153 E Crested Ibis vs Monster
桁DP : ABC154 E Almost Everywhere Zero
参考にしている記事
DP + ナップザックDP : 動的計画法超入門！ Educational DP Contest の A ～ E 問題の解説と類題集
ナップザックDP : 典型的な DP (動的計画法) のパターンを整理 Part 1 ～ ナップサック DP 編 ～
桁DP : 桁 DP の思想 〜 K 以下の整数を走査するとはどういうことか 〜
桁DP : 世界一わかりやすい？桁DPの実装
桁DP : 桁DPの痒いところに手が届く解説
bit全探索
bit演算部分はあまり理解しないままテンプレを使いまわして問題を解いてます。
例 : ABC147 C HonestOrUnkind2
MOD演算(逆元を用いたものも含む)
逆元を用いればなぜMOD演算が出来るのかといった理論部分はさっぱり理解できていません。
テンプレも完成していなく、今後問題として出てきた場合は事故の可能性も...
例: ABC156 D Bouquet
参考にしている記事
「1000000007 で割ったあまり」の求め方を総特集！ 〜 逆元から離散対数まで 〜
よくやる二項係数 (nCk mod. p)、逆元 (a^-1 mod. p) の求め方
二項係数(事前にテーブルを作成するタイプ
二項係数は様々な問題で出てくるのでテンプレを持っています。
二項係数のみで解ける問題が思いつかないので例は省略します。
ダイクストラ法
序盤の方で書いていた新しいアルゴリズムの開拓によって得られた知識その1です。
演習量も少ないのであまり満足には扱えません。
例: ABC70 D Transit Tree Path
ワーシャルフロイド法
よるかつで登場したABC79 D Wallで知りました。
理論部分は未だに理解出来ていません...
参考にしている記事 : 素人によるワーシャルフロイド法
Union Find
新しいアルゴリズムの開拓によって得られた知識その2です。
演習量はそれなりにこなしましたが直近のコンテストでは使ってないので今後に期待といった感じです。
例: ABC97 D Equals
AtCoder自動提出ツール
コンテスト中により多くの時間を問題に使うために自動提出 + 自動テストツールを導入しました。
私の環境はUbuntu18.04LTSなので以下の記事などを参考に導入しました。
atcoder初心者こそ環境構築しよう！(atcoder-cli,online-judge-toolsのインストール、使い方)
タイピングの練習
AtCoderの早解きはタイピングゲーという内容をTwitterの方で見かけたのもあってたまに練習しています。
速さとしては、寿司打の10000円コースで20000円取れると絶好調といった程度のものです。
タイピングの練習だったりホームポジションの練習は、以下のサイトで練習しました。
タイピング練習 (日本語編)
参考・使用させていただいたサイト
精進量のグラフ: AtCoder Problems精進量の推移のグラフ: AtCoder Scores
私のテンプレ
コメント
コメントを投稿