https://blog.hamayanhamayan.com/entry/2017/06/07/234608

最大長方形

与えられた条件を満たす最大の長方形の面積を求める傾向の問題
最大正方形は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. じょうしょうツリー解説

全通りの組合せを考えて答える（特有のパターンがある？）

bitsetによる64倍高速化

用法
- 【1】到達性チェック
- 【2】yes/no系動的計画法高速化
- 【3】64倍速SCCというのがあるらしい
問題
- 【1】 CF319 Flights for Regular Customers 解説
- JAG Revenge of the Endless BFS
- 何かに使えるかもしれない
- 【2】 AGC020 Median Sum 解説
- 【3】CF609 Invertation in Tournament
非想定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つ以下であれば並び替えて回文できる
  - ARC053 回文分割
- 回文の回転にはある種の周期性がある
  - ARC064 Rotated Palindromes 解説1 解説2 解説3
  - CF339 Necklace 解説
- ある文字列を回文にするときに回文として対応する文字のペアは独立に決定できる
  - CC Hasan and boring classes
- 回文と区間DPは相性がいい

N頂点N辺のグラフ、Functional Graph

連結「なもりグラフ」
- N頂点N辺の無向グラフはなもりグラフと言い、連結であれば1つだけ閉路が存在する
- 有向なもりグラフもある（出次辺がそれぞれ1つ）
  - こういうN頂点で、N頂点から辺が出てるやつをFunctional Graphという
  - 各頂点からf(v)のように遷移先が決定するからだそうだ。なるほど。
  - ループが1つだけある
  - https://csacademy.com/contest/round-59/task/editor/
  - 大切な性質として、連結成分ごとに閉路が存在する。つまり、連結成分の個数＝閉路の個数となる
    - それを効果的に使う問題
    - ABC173 F - Intervals on Tree
N頂点N辺の無向グラフで全ての頂点から1は辺が出ているとき、連結成分で纏めると全て閉路になるので連結成分毎に頑張る

最短経路木

別名、最短路木実装

一端を固定して、もう片方を伸ばしていくと状態変化がそんなに無いので分割統治っぽくでき、高速に処理できる

ある配列の左端を固定して、右端を動かしながらANDやORを取るとする。すると、求まるAND,ORはそれぞれ高々32通りしかない。
- CF441 High Cry 解説
- HR Costly Intervals
ある配列の左端を固定して、右端を動かしながらgcdを取っていき、gcdが同じ要素をまとめていくとO(logN)グループしか無い
- HR The Strange Function
類題
- CC Replace and Substring Queries

自動ベクトル化

入力がランダムの場合のテク

ランレングスが使えるかも
- CF449 Willem, Chtholly and Seniorious （クエリ2によって大幅に個数が減る）
- http://kmjp.hatenablog.jp/entry/2015/07/15/1000 （入力ランダムじゃないけどランレングスの練習）
- ランレングスはsetで管理する
再構築回数が少ない（もしくは再構築対象が小さい）場合は、愚直に再構築しても間に合う
- SRM753 Med MojisBag

約数を使って再帰していく問題

どこかで類題を見たのだが思い出せないので、一応メモっておく
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だけとても多いけど、それ以上は全然無いから全列挙、ソート、重複削除でダブリなしで数えられる
- CF471 Sad powers 解説
- ECR50 Relatively Prime Powers

不変量を使った問題

ある種の変換について、ある不変量がある場合は、それを用いることで効果的に計算ができる
問題
- ARC071 TrBBnsformBBtion 解説1 解説2
- AGC027 ABBreviate
- CC Bear and Three Colours 解説
- ARC094 Normalization 解説1 解説2
- AGC009 Eternal Average 解説1 解説2 解説3
- SRM221 Div1 Hard 解説
- APC001 XOR Tree 解説1 解説2 解説3 解説4 （不変量使ってないかも）
- AGC040 Neither AB nor BA
差分をとると実はswap
- CF Magic Stones

貪欲法＋DPのナップサック問題

「個数制限付き」「複数個で1つのまとまり」なナップサックは、貪欲法をまずはしてから、DPをする
問題

有理数、ファレイ数列、Stern-Brocot Tree

有理数を効率的に探索したいという要望がある
それ向けの数列ファレイ数列解説
それ向けの構造 Stern-Brocot Tree 解説実装図
これも関連？
問題
- GCJ2019 Round2 New Elements: Part 2

Sliding Window Aggregation

解説1 解説2
stackを2つ使ってqueueを作る手法
累積和を取ることで、queueとしての基本機能+queueに入っている要素に対する演算がならしO(1)で行える
queueだけでなくdequeも構築可能
問題
- TSG LIVE! 4 プログラミングコンテスト LCM Interval

小ネタ、小テク

特殊な座圧によるクエリ対応
- 特殊な座圧をすることによって回答クエリが区間クエリとして答えることができる
- CF348 Little Artem and Time Machine 解説1 解説2
modを取ると数は半分以下になる
- CF250 The Child and Sequence 解説1 解説2 解説3
最大値、最小値の区間を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 エレベータ
右手法という方針がある
- AOJ 遭難解説1 解説2
双方向リスト
- AOJ ピボット (Pivots) 解説
- AOJ バトンリレーゲーム解説
- コドフォでも見たことある気がする（盤面のなんか）
stackを利用した問題
- stackの問題では一度しか消さない、一度しか入れないということで均しで間に合う問題が多い
- AC 天下一後入れ先出しデータ構造
Zero-one principle「長さ N の任意の 0/1 列がソートできることと、長さ N の任意の順列がソートできることは同値」
- 原点 wiki
ある集合をグループ分けするときに、適切に正規化することで、同一グループに属すものが同じ値になることを利用する
- yukicoder No.849 yuki国の分割統治
クエリ先読み
- クエリ問題は先読みすることで簡単に計算できる場合がある
- 大体ならしO(Q)になる
- ABC133F Colorful Tree 解説
グリッドグラフは二部グラフ（＋フロー）
- グリッドグラフは二部グラフです
- 問題
  - AC 広告
  - SRM788 Div1 Hard ParkPlace
  - SRM570 Div1 Hard CurvyonRails

最大長方形

Meldable Heap

二部グラフ判定（二部グラフを頂点倍化Union-Findで判定する話も）

木の中心、重心

立方体の和集合の体積の総和を求める

全通りの組合せを考えて答える（特有のパターンがある？）

bitsetによる64倍高速化

辞書順最小を最大化する

回文

N頂点N辺のグラフ、Functional Graph

最短経路木

一端を固定して、もう片方を伸ばしていくと状態変化がそんなに無いので分割統治っぽくでき、高速に処理できる

自動ベクトル化

入力がランダムの場合のテク

約数を使って再帰していく問題

無向グラフの辺最小被覆パス

特殊なソートで最適解を得るテク

実はそんなに数が無い

不変量を使った問題

貪欲法＋DPのナップサック問題

有理数、ファレイ数列、Stern-Brocot Tree

Sliding Window Aggregation

小ネタ、小テク

メモ