最大長方形
- 与えられた条件を満たす最大の長方形の面積を求める傾向の問題
- 最大正方形はO(HW), ヒストグラムの中の最大長方形O(N), 最大長方形O(HW)
- 最大正方形 : dp解法がある
- ヒストグラムの中の最大長方形 : stackを使った解法がある
- 最大長方形 : 「ヒストグラムの中の最大長方形」の問題に帰着させることができる
- 問題
- AOJ 最大正方形 解説
- AOJ ヒストグラムの中の最大長方形 解説
- AOJ 最大長方形 解説
- (関係無いかも知れないが)部分長方形問題まとめ
- ECR30 Forbidden Indices
Meldable Heap
- Meld(併合,マージ)ができるヒープ
- マージテクで実装するとMeldはO(log^2N)
- Skew Heapで実装するとMeldはO(logN)
- 問題
- AOJ JAG春コンテスト2013 E. Minimum Spanning Tree 解説1 解説2 解説3
- UTPC2012 L. じょうしょうツリー 解説
二部グラフ判定（二部グラフを頂点倍化Union-Findで判定する話も）
- あるグラフが二部グラフか判定するにはDFSして二色彩色していけばよい
- こういうやりかたもある
- 問題
- ARC099 Independence 解説
- CodeChef Chef and Friends 解説
- ARC036 D. 偶数メートル 解説
- ECR22 Bipartite Checking 解説 (+永続UnionFind)
木の中心、重心
立方体の和集合の体積の総和を求める
- この前のコドフォの解説でkmjpさんが言及してて知った
- 「JOI2011-2012 Day1 Fish」が初出？
- 問題
- JOI2011-2012 Day1 Fish 問題文 解説
- AtCoder ピラミッド - 球編 解説
- CF Karen and Cards 解説
- AOJ 魚の生息範囲 (Fish) ←っぽいけど違うかも(公式解説では座圧しろとあった)
全通りの組合せを考えて答える（特有のパターンがある？）
bitsetによる64倍高速化
- 用法
- 【1】到達性チェック
- 【2】yes/no系動的計画法高速化
- 【3】64倍速SCCというのがあるらしい
- 問題
- 非想定bitset
- bitsetは時に爆速なのでO(10^10/64)を可能にする。非想定解としてよく見る。やってみる価値はある。
- ECR35 Mass Change Queries
- O(NQ/64)でN=2*10^5,Q=2*10^5が処理が軽いと間に合う（処理がビット演算のみで完結する）kmjpさんのコード
- CC Chef and odd queries 解説 コード
- bitsetのfind_first, find_next 解説 よく分かってない。紹介問題も必須機能ではないみたい
- 比較開始位置のmod 64がずれると比較回数が2倍になってしまうので、開始位置 mod 64の値毎にbitsetを持つと高速化できて通る 出典
辞書順最小を最大化する
- iehnさん「辞書順最小を最大化したいだけなんだから、その時点で最小のに最大のをつなげていけばいいだけ」
- 天才すぎる
- AtCoder Largest Smallest Cyclic Shift 解説
- yukicoder No.205 マージして辞書順最小 解説
回文
- テク
- 奇数個の文字が1つ以下であれば並び替えて回文できる
- 回文の回転にはある種の周期性がある
- ある文字列を回文にするときに回文として対応する文字のペアは独立に決定できる
- 回文と区間DPは相性がいい
N頂点N辺のグラフ、Functional Graph
- 連結「なもりグラフ」
- N頂点N辺の無向グラフはなもりグラフと言い、連結であれば1つだけ閉路が存在する
- 有向なもりグラフもある（出次辺がそれぞれ1つ）
- こういうN頂点で、N頂点から辺が出てるやつをFunctional Graphという
- 各頂点からf(v)のように遷移先が決定するからだそうだ。なるほど。
- ループが1つだけある
- https://csacademy.com/contest/round-59/task/editor/
- 大切な性質として、連結成分ごとに閉路が存在する。つまり、連結成分の個数＝閉路の個数となる
- N頂点N辺の無向グラフで全ての頂点から1は辺が出ているとき、連結成分で纏めると全て閉路になるので連結成分毎に頑張る
最短経路木
一端を固定して、もう片方を伸ばしていくと状態変化がそんなに無いので分割統治っぽくでき、高速に処理できる
- ある配列の左端を固定して、右端を動かしながらANDやORを取るとする。すると、求まるAND,ORはそれぞれ高々32通りしかない。
- ある配列の左端を固定して、右端を動かしながらgcdを取っていき、gcdが同じ要素をまとめていくとO(logN)グループしか無い
- 類題
入力がランダムの場合のテク
- ランレングスが使えるかも
- CF449 Willem, Chtholly and Seniorious （クエリ2によって大幅に個数が減る）
- http://kmjp.hatenablog.jp/entry/2015/07/15/1000 （入力ランダムじゃないけどランレングスの練習）
- ランレングスはsetで管理する
- 再構築回数が少ない（もしくは再構築対象が小さい）場合は、愚直に再構築しても間に合う
約数を使って再帰していく問題
- どこかで類題を見たのだが思い出せないので、一応メモっておく
- CF450 Unusual Sequences
無向グラフの辺最小被覆パス
- 辺を全て被覆できるパスの数の最小値
- ARC088 Christmas Tree
- 「奇数次数の頂点数/2」が最小値（奇数次数がパスの端点となれば偶奇が合うため）
特殊なソートで最適解を得るテク
- 特殊な比較関数を使ったソートを用いることで最適解（のための順番）が得られるテク
- 隣接する二項間について、スワップすべきかを考えると比較関数を作ることができる
- AC 天使とふすま 解説
- 動的計画法テク2「選択するものを最初にソートしておくと、DPできたり、状態を同一化できたりする」
- AC Different Strokes 解説
実はそんなに数が無い
- 種類数がsqrt(N)になることを使うテク
- 素数とsqrt(N)は相性がいい 問題
- {数,個数}としてまとめて、数の総和がN以下であるならば、このペアの種類数はsqrt(N)となる 問題
- HUPC2019 Day2 D Two Colors Sort 解説
- a^pの形で書ける数は10^18が上限だとp=2だけとても多いけど、それ以上は全然無いから全列挙、ソート、重複削除でダブリなしで数えられる
不変量を使った問題
- ある種の変換について、ある不変量がある場合は、それを用いることで効果的に計算ができる
- 問題
- 差分をとると実はswap
貪欲法＋DPのナップサック問題
- 「個数制限付き」「複数個で1つのまとまり」なナップサックは、貪欲法をまずはしてから、DPをする
- 問題
Sliding Window Aggregation
小ネタ、小テク
- 特殊な座圧によるクエリ対応
- 特殊な座圧をすることによって回答クエリが区間クエリとして答えることができる
- CF348 Little Artem and Time Machine 解説1 解説2
- modを取ると数は半分以下になる
- 最大値、最小値の区間をstackで持ちながら[0,i]の範囲での最適解を得ていくテクがある
- CF276 Kindergarten（本当の解法はもっと簡潔） 別解
- HR The Strange Function
- 特殊な制約により計算量が抑えられる系
- 「K≦10^5でs1+s2+...+sK≦10^5」で任意のペアについてクエリを処理するとき、サイズが小さい方で全探索するようにクエリを実行するとメモ化などで間に合う これ
- どんなに意地悪してもTLEさせられないという面白いやつ
- クエリの要素数によって場合分けを行うことでならしで間に合わせることができたりする これ
- 条件を少しずつ変えて全探索は差分を計算することで全てを計算し直さずに全探索できる これ
- より制約の緩い問題を解くことに帰着する
- 「f(x) := コストがxの時の組合せ」を解くとするときに
- 「g(x) := コストがx以下の時の組合せ」を解くのが優しい場合は、それを解いてf(x) = g(x) - g(x-1)を答えとする
- この問題
- 数列の中に順列が含まれていて、順列がどんな形でも関係ない場合に、特定の順列のパターンは全てのパターン÷順列のパターンで求められる
- この問題
- この問題では順列が含まれるのではなく、複数個同じ数が含まれない数列を含む
- 特定の数列を含む数え上げは難しいので、同じ数が含まれない長さMの数列を含む数列を数え上げて、同じ数が含まれない長さMの数列のパターンで割って求めている
- 「ある盤面が列または行のスワップ操作だけで全部白にできますか？」→全ての2x2のsubrectangleについて黒マスの個数が偶数
- 問題
- 素因数分解した素数の個数はそんなに無い CF Make Square
- 一度グループになったら、分かれないみたいなやつは逆から見てくとうまくいく場合がある
- CF Trips
- 他にもたくさん見たことある気がする
- setで区間を保持しながら解く
- 右手法という方針がある
- 双方向リスト
- AOJ ピボット (Pivots) 解説
- AOJ バトンリレーゲーム 解説
- コドフォでも見たことある気がする（盤面のなんか）
- stackを利用した問題
- stackの問題では一度しか消さない、一度しか入れないということで均しで間に合う問題が多い
- AC 天下一後入れ先出しデータ構造
- Zero-one principle「長さ N の任意の 0/1 列がソートできることと、長さ N の任意の順列がソートできることは同値」
- ある集合をグループ分けするときに、適切に正規化することで、同一グループに属すものが同じ値になることを利用する
- クエリ先読み
- クエリ問題は先読みすることで簡単に計算できる場合がある
- 大体ならしO(Q)になる
- ABC133F Colorful Tree 解説
- グリッドグラフは二部グラフ（＋フロー）
- グリッドグラフは二部グラフです
- 問題
- AC 広告
- SRM788 Div1 Hard ParkPlace
- SRM570 Div1 Hard CurvyonRails
