はじめに
最近思い立ってAtcoderを始めることにした。
それに当たってアルゴリズムについて勉強すべき項目をここにまとめておくと効率的かと思い、執筆に至る。
随時更新予定。
（追加すべき項目などアドバイスあれば嬉しいです）
自分の現状
というわけで早速パナソニックプログラミングコンテスト2020に参加してみた。(ちゃんとコンペに参加するのは初めて)
自分の出来としては全６問でこんな感じ。
- 基本、割愛
- W=1 or H=1の場合が思いつかなかった知人がいた
- 式変形をせずに苦労してる知人がいた
- 競プロの知識はないが解けた
- TLEを解消できなかった
- 余裕もなく問題文をさらっと読んで理解せず放置
パフォーマンス的には水色くらいという感じ。
自分はpythonを使用したが、５問目以降はpythonで正解してる人はいなかった。
理由としては以下のどっちかかな〜と予想。
- pythonのパフォーマンスの限界
- 強い人がC++を使用してpythonにいなかった
当面はアルゴリズムの勉強はしつつ、必要があればC++に慣れる予定。
勉強すべきもの
- 深さ優先探索
- 幅優先探索
- ビットループとか
- 貪欲法
- 動的計画法(かなり種類ありそう)
- 木・二分木
- プライオリティーキュー・ヒープ
- 二分探索
- Union-Find
- グラフ問題に慣れる
- 余り計算
- 冪乗計算
- しゃくとり法
- 反転
- 男性衝突
- 半分全列挙
- 座標圧縮
- セグメント木
- Binary Indexed木
- バケット法・平方分割
- ネットワークフロー問題
- 平面幾何問題
今後
この項目を潰しながら適宜新項目を追加していって青色を目指す。
今の所感として青と水色にかなり壁を感じる、、、