# Atcoder # 基本の考え方 - フローチャートを作るのが最終的な形 - 基本は全探索をベースに考える - 制約条件から全探索が可能かどうか判断する - 100万オーダーまでなら全探索は使える - 漸化式だったらDPを疑う？ - 実装負荷がめちゃくちゃ高いコードは書かされない、アルゴリズムを問われてスマートに書く必要あり - アルゴリズム力は知識が問われているよ - 条件を簡略化するためにどう世界を使いやすいようにいじり散らかすか - ツリーを辿るときは探索するんや、再帰するんや - lower_boundを使うかどうかという判断ができる - シーケンシャルにインデックスを探していくもの - vectorはけつの操作が早い - 最長経路問題はdfs - dequeかvectorをつかう - 自由なアドレスを使いたいときはvector - 探索をしたいときはdeque - 要素を探す場合はvector - GCDの計算方法を身に着ける # 最適化 - 選ぶ系 graph - 調整する 二分探索？ # priority queue - ABC127-D C++ライブラリで存在する。 適当にぶちこんだ値が巨根から出力される三木ちん.のためのソートアルゴリズム。 ```cpp=aaa int main(void){ int a[] = {5, 4, 6, 3, 7, 2, 8, 1, 9, 0, 9}; std::priority_queue<int> q; for (size_t i(0); i < sizeof(a) / sizeof(a[0]); ++i) { q.push(a[i]); } while (!q.empty()) { std::printf("%d\n", q.top()); q.pop(); } return 0; } ``` # 木 ## 赤黒木 - 平衡二分探索木の一種 - 根から葉までの距離の最大と最小が二倍を超えない ## AVL木 - 平衡二分探索木の一種 - 強平衡二分探索木のこと ## B-木 - 二分木ではない - 2-3木などがある - DBMSで利用される ## スプレー木 ## treap # 入力のパターン化 関数をモジュール化する。 # 型 ``` int long long long 16bit CPU 16 32 64 32bit CPU 32 32 64 64bit CPU 64 64 64 ``` 緑・水色 70問 - 14 - 6 青 40問 黄 22問 # 計算量を減らすコツ - メモ化する（フラグで一度計算したところを計算しないようにする） - DPでメモ化する - combinationの計算、パスカルの三角形が使える（ライブラリがない場合） # 3章 全探索 ## ペアの和を最小化する問題 - 全探索と二分探索による解法がある lower_boundというkey以上の値をとってこれるに分割するライブラリがある https://qiita.com/ganariya/items/33f1326154b85db465c3 - 線形探索の場合は、N^2 - 二分探索の場合は、ソートはNlogN、探索はlogN # 最短経路問題 - BFSで考えてみる（オーダーを気にする） # 最長経路問題 - DFSを使う？ # 解くべき問題 - p.038を動的計画法で書き直す # 逆元 mint https://atcoder.jp/contests/abc133/submissions/6302633 解く時に使う - フェルマーの小定理 # now now: 146 - DP訓練 次回か - 探索 - グラフ訓練 DPくんれん　 https://atcoder.jp/contests/dp/tasks Jまで 貪欲法しらべ https://atcoder.jp/contests/abc139/submissions/7296454 https://qiita.com/drken/items/dc53c683d6de8aeacf5a https://qiita.com/drken/items/7f98315b56c95a6181a4 139-E,13.14をちゃんとやる あり本買わねば？ mint https://youtu.be/L8grWxBlIZ4?t=9858 https://youtu.be/ERZuLAxZffQ?t=4765 # テーマカウンタ - 探索 - 全探索: 3 - BFS: 1 - DFS: 1 - 二分探索: 1 - DP: ? - bitDP - 尺取り法： 1 - グラフ - 最短経路問題: 1 - 最長経路問題: 1 - 貪欲法: 1 # まだ不明なこと - シーケンシャルな処理で、処理ごとに条件分岐が生まれる場合はDP? - 木DP # テンプレート化 - chmin for DP - priority queue = 2分ヒープ - ビット演算 - rep - pair - グラフインプット関数を作っちゃう（三木案） # 記法 - long longの整数リテラル 1LL # 知識 - グラフは単純かつ連結 -> ループしない、独立な頂点がいない、多重辺でない - mint調べる # グラフ問題の場合の三木メソ 1. 探索の最小単位を考える（例：、自分と親と子の3世代、親と子のみ） 2. 最小単位内での探索関数を作る（DFS, BFSなり） 1. 再帰呼び出し、キュー構造、メモ化 3. グラフを考える場合は、何がゴールなのかを考える 4. 何を最小化したいのかなど ```cpp= int k; mint ans; vector<int> to[100005]; void dfs(int v, int p=-1) { for (int u : to[v]) { if (u == p) continue; dfs(u,v); } int nk = (p==-1) ? k : k-2; int c = (p==-1) ? to[v].size()+1 : to[v].size()-1; ans *= f(nk,c); } ``` 3. modを使うくらいでかい場合は、フェルマーの小定理を身につけ対応する（mint） 4. 入力の決まり文句？ ```cpp= int main() { int n; cin >> n >> k; rep(i,n-1) { int a, b; cin >> a >> b; --a; --b; to[a].push_back(b); to[b].push_back(a); } ans = 1; dfs(0); cout<<ans.x<<endl; return 0; } ``` # 倍数の三木メソ ```cpp= for (int i = n; i >= 1; --i) { int sum = 0; for (int j = i+i; j <= n; j += i) { sum ^= b[j]; } b[i] = sum^a[i]; } ``` # よく使うライブラリ - deque - イテレータとイテレータの引き算はintになる - push_front - priority queue - set - vector - push_backしかできない # 基本事項 - 後置・前置インクリメント - 前置インクリメントは代入時にインクリメントする # かんがえるこつ # DFS/BFS違い ## DFS - スタック、再帰 - 「行き掛け順」「帰りがけ順」を使ったアルゴリズム - 再帰を使えるので楽 - 子供の集計とか、s-t経路があるかどうかとか - 行きがけ、親頂点についての情報を子頂点に配る - 帰りがけ、子頂点の情報を集めて親頂点の情報を更新する - ## BFS - 並列化しやすい - 最短経路を見つける ## DP - マトリックス表をイメージする - 表内の範囲であれば順番に寄らず最適解が求まる - 表は大きいほど最適解である - memset 配列の初期化