競プロ

「ビット演算の使い方を総特集 -マスクビットからbitDPまで」

ビットを用いることで、データ量を少なく済ませたり、計算コストを小さく抑えたりすることができるメリットがある

1 ビット演算の基本

ビットの用途として、ゲームの状態管理、業務システムの状態管理、エラー処理分岐の管理、RGB値の操作、ビットマップ画像マスク、TCP/IPのサブネットマスク、ハードウェアからの割り込み制御、Linuxのファイルパーミッション、.NetのKeys列挙隊などがある

数字を二進数表記したときに格桁ごとに演算をしたもの

2 bitset

coutするときはそのまま整数値を出力するが、bitsetを用いると見易い出力ができる

3 ビットを用いたフラグ管理

a番目のフラグが立っている状態は1<<aと表せる

a番目とb番目とc番目に立っている状態は||を使って表現できる



4 マスクビット

ビットの使い方として最も多いものの１つが、マスクビットである

基本的なアイディアは共通で、

・複数のフラグをまとめて立てる

・複数のフラグをまとめて消す

・必要な情報だけを取り出すためにマスクした部分の情報のみを取り出す

といったものを効率よく実現するもの



5 ビットを用いた集合演算

ビット演算によるフラグ管理の表を集合の言葉で記述してみる



6 bit全探索

bit全探索とは、n個の要素からなる集合の部分集合を全て調べ上げる手法のこと

部分和問題が解ける

だが、部分和問題はDPでもっと効率よく解ける

7 与えられた部分集合の部分集合を列挙

bit全探索は{0,1,,,,,n-1}の部分集合を列挙するアルゴリズムだったが、今度はからなずしも0,1,,,9の全てが揃っているわけではない集合が与えられ、その部分集合を列挙する方法を考える

8 next_combination

n個の要素の集合の部分集合のうち、要素数がkのもののみを列挙する方法を考える

9 XorShiftを用いた高速乱数生成

Xorshiftはビットを用いたシンプルな乱数生成方法

乱数の質が高い割に超高速であり、rand()よりずっと早い

10 Binary Indexed Tree

BITは区間に対する処理を高速に実現するデータ構造

・配列のa番目からb番目までにvを加算する

・配列のa番目からb番目までの総和を求める

これらは普通にやるとb-a+1箇所にアクセスすることにあんるが、もし配列が巨大な場合、このようなクエリが飛んでくると途方もない時間がかかることになるが、BITを用いると上のクエリを超高速で実現できる

11 bit DP

bitDPはn個の要素の順列としてあり得るものの中から最適なものを求めたい場面でしばしば使えるテクニックである

最後の要素が何だったかで場合わけをする

巡回セールスマン問題に適用できる

「レッドコーダーによる競プロ上達のガイドライン」

AtCorderのレーティングが完全に実力通りになるには15回程度コンテストに出る必要がある

茶色コーダーに要求されること

・ABCのA、B問題を確実に、C問題も少しは解ける

モチベ管理が大切

水色コーダーに必要なこと

・7割以上の確率でABC4完

・2~3割の確率でABC５完

基本的なアルゴリズムとデータ構造を全て理解する

・全探索

・二分探索

・DFS

・BFS

・DP

・ダイクストラ

・ワーシャルフロイド

・クラスカル

・高速な素数判定

・冪乗を高速に

・逆元を計算

・累積和

・グラフ

・木

・Union-Find

これらがコンテスト中に使えるようになる

・全探索

大きく分けて、全列挙、ビット全探索、順列全探索の３つに分かれる

・二分探索

半々にしていくやつ

・DFS

深さ優先探索

・BFS

幅優先探索

・DP

ナップザックDP、区間DP、bit DPの３つがわかれば水色にはなれる

・ダイクストラ

N頂点M辺のグラフにおける頂点1から各頂点への最短経路長をO(MlogN)で求める

・ワーシャルフロイド

N頂点M辺のグラフにおける全頂点対間の最短経路長をO(N^3)で計算する

・クラスカル

最小全域木を求める

・高速な素数判定

Nが素数であるかO(√N)で計算する

・冪乗を高速に

a^bをmで割った余りをO(logb)で計算する

・逆元を計算

ax ≡ b(mod p)(pは素数)となるようなxをO(logp)で計算するアルゴリズム

・累積和

テクニック

累積和の亜種として、いもす法というアルゴリズムもある

・グラフ

頂点とへんで構成されるデータ構造

・木

N頂点、N-1辺の連結なグラフ

・Union-Find

競プロで頻出のデータ構造

黄色コーダーになるには

・ABCでほぼ確実に5完

・ABCで5割ぐらいは全完

・AGCでも2問以上正解

蟻本に乗っている大半のアルゴリズムとデータ構造を理解する

・座標圧縮

・半分全列挙

・行列累乗

・ダブリング

・Grundy数

・Rolling Hash

・平方分割

・最大流

・最小カット

・二部グラフ判定

・二部マッチング

・セグメント木

・BIT

・座標圧縮

とても大きい座標で、現実的に扱えないサイズのときに圧縮して計算量を抑えるテクニック

・半分全列挙

２つのグループに分けて全列挙して、１つは全探索、もう１つは二分探索などで高速に処理

・行列累乗

行列の累乗を繰り返し二乗法を利用して効率的に求める

フィボナッチ数の10^9番目や漸化式の10^9を高速に求めるのに使われる

・ダブリング

N個次の要素を知りたい時に頻繁に使われるテクニック

・Grundy数

ゲーム理論の問題を解く時に使われる

・Rolling Hash

文字列系の問題を解くために知っておくべきアルゴリズム

・平方分割

平方分割（バケット法）は長さNの列を√Nこごとに分けて考えるアルゴリズム

・最大流

最大流は、グラフ上の流れを扱うアルゴリズムの中では最も競プロで使われる

・最小カット

フローで解ける問題の中には、最小カット問題に帰着することで解ける問題も多い

・二部グラフ判定

二部グラフは特殊な性質を持っているため、競プロで問題にされることが多い

そのような問題を解くためにはまず、グラフが二部かどうか判定しなければ家kない

・二部マッチング

輸送問題など、現実世界の問題を解く時によく使われるアルゴリズム

・セグメント木

単純なセグメント木(RMQまたは亜種)

遅延評価セグメント木の２つがある

・BIT

競プロで頻出のデータ構造の１つ

AtCorderの過去問を1000問以上解く

10分でパフォーマンス250以上変わるのでタイピング速度を鍛えろ

黄色コーダーと橙コーダーの差は演習量である

橙後半相当の難易度の問題を1時間以内で解ける確率が2~3割になると橙コーダーの実力がついたと言える

橙レベルの問題になると考えた分だけ考察力がつく

「AtCorder版あり本」

「アルゴリズムのスライドまとめ」

「C++の読み込み高速化」

強い人のきれいなコード

「tourist」「rng_58」「snuke」「beet」「drken」

個人的な競プロメモ

おじさん、競プロ始めるってよ

beetブログ

アルゴリズムロジック

「cpu実験でlinux」

「競プロブログ」

「Maspyさん」

「木の表現」

「シュタイナー木」

・大量の入出力データを扱う課題を解く際に、入出力の処理にcin, cout ストリームを使用したC++プログラムはscanf, printfを使用した同等のプログラムに比べて遅くなる

それでも使いたい場合は、

冒頭にios::sync_with_stdio(false);を入れることで同期がなくなり、早くなる

cin.tie(0)も同様

これらは、iostreamとstdio、cinとcoutの同期を切るものである

データサイズが10^5以下ならiostreamでも良いが、問題によっては使ってはいけない

「典型テクニックまとめ」

—数え上げ

ソートして大きいものから考える

状態を準同型でまとめる

多項式の係数のGCDは積に対して準同型

ちょうどk個 = k個以下 - k-1個以下

候補の区間が複数ある場合は最長のものだけ考える

区間の端だけ求めると簡単にも止まる

sum(C(i,j))の形は高速に求められることがある

—グラフ

次数1の頂点の取り除く

次数1の頂点を見る

平面上の包含関係は木構造になる

辞書順最大の独立安定集合はgrundy数になる

グラフをオイラー路に分割するときの最小の数

根付き木の同型判定は子をソートしながらするとO(N^2longN)

hashでやればO(NlogN)

—木

根を固定したとき、部分木のサイズが自分より大きくなる辺は根以外でちょうど一本存在する

部分木はオイラーツアーで１つの区間になる

パスはHL分解でO(longN)この区間になる

高さの和の部分和問題は上界と下界で挟める

—-幾何

格子点のみを頂点とする図形の面積は0.5刻み

放物線をつなげて一番高いところに行きたい場合は終点の傾きを一致させる

—ゲーム

小さい制約の問題をgrundyで解いてエスパーする

DPできる制約ならする

不変量を考える

—文字列

ある文字列をずらして一致してる部分を最大化→FFT

辞書順最小を求める場合はprefixではなく、suffixでDPする

distinctな文字の数え上げは直近の文字にだけ遷移するようにすればできる

辞書順最小のconcatはx+y < y+xでソート

文字列のソートは長さの総和をSとして、O(SlogS)でできる

文字列をいくつかの連続部分列に分けると独立して考えられる場合もある

—最適化

最適解を持ってきて性質を見る

他の情報から復元できるパラメータを探す

自由度が１つ落とせる場合は半分全列挙ができる

極大と最大が一致するか

順番を決める問題は適当にソートして貪欲かDP

操作によっていくつかの区間に分かれ、それぞれが独立なものは区間DP

f(X)の最小化はXを決めうったときの性質に注目する

—オーダー改善

ペア、トリオだけを考える

最初の１つを決めると残りも決まる

冪乗が出てきた場合、k=1を場合わけで取り除くとsqrtに落ちる

調和級数でlog

個数制限付きナップザックは2べきに分割すると高々log個の01ナップザック

使わなかったものを最後にまとめて貪欲

配るDPをもらうDPに書き換えてセグ木で高速化

多次元DPでは一番小さいパラメータを動かす

部分集合の列挙はO(3^n)

同じ状態をまとめる

各要素が高々一個のときはbitDP

階さを考える

累積わをとる

MODをとって結果が変化するのはlog回

累積和をkつずつずらすのはO(k)

—定数倍改善

setのlower_boundは遅いので変更がないならvector

キャッシュの乗り方を意識

構造体を渡すときは参照渡し

unorderd_map, unordered_set

—手抜き実装

番兵を入れると境界値判定が不要

等価に思える処理が等価かどうか確かめる

—デバッグ

オーバーフローに気をつける

lower_boundをsetに使うとO(N)

—勘違い

DAGでないグラフで最小値はメモカではなく、Dijkstra

フローで頂点の流量は無限

次数が3以上のグラフでDFSは普通むり

—その他

単調性がないかどうか考える（あれば二分探索）

k番めの値を求めるときはx以下の数を数える二分探索

入力を乱数で生成すると最悪ケースがなくなる

操作を繰り返す系は不変量

マンハッタン距離は回せ

マンハッタン距離の総和の最小化はn/2番目の値

クエリを先読み

同じ選択をする人をまとめる

操作で順序が入れ替わらないことがある

「逆元総特集」

「焼き鈍し法」

乱択アプローチを試みる焼き鈍し法は多くの最適化問題に対して何も考えずにそれなりの答えを出せる手法である

うまく乱択先を絞れると探索系のアルゴリズムでは詰めきれない部分まで最適解に寄せることができる

ある状態Aから少しだけ変化した状態A’に遷移したときのスコアをもとに最適解へ近づいていこうというのが焼き鈍し法のアプローチである

各状態間のスコア変化が滑らかな問題では有効であるが、AとA’の関係性が離れている問題では使えない

・小数点を捨てないで計算して欲しい場合は.0をつける

・真は1,trueで表現する、数値もbool型の値のように扱うことができ、0だけfalseになる

・breakはループを抜ける、continueは次の処理を飛ばして最初に戻る

・無限ループが発生すると終了コードは実行時間が長すぎることを表す9になる

・目安として、最近の多くのコンピュータはCPUは1GHzで動作しているのでCPUが100サイクル以内にできる演算なら一秒間に10^6実行可能と期待できる

「定数倍高速化テク」

QCFium法のpragma

3行追加するだけで高速なバイナリが生成される

これだけで実行時間が２割削れることも

入出力の高速化

ios::sync_with_stdio(false);

std::cin.tie(nullptr);

vector関連

無駄な要素の再構築やメモリの再確保をなくすのが基本

push_backをemplace_backに置き換えることから

pusu_backでは引数になるまでに要素が構築され、それがコピーされてvector内に要素が入るが、emplace_backではコンストラクタ引数をとるので余分な構築が減る

vectorのメモリ確保は先にやるべき

コンパイラの変更

clangよりgccの方が基本的に優秀

なるべくintを使う

long longでなくても住む場所ではintを使うとSIMDも効きやすくなってメモリ使用量も減りたくさんの値がキャッシュに乗るのでメモリアクセスも早くなる

これはかなり有効

定数にはconstexprをつける

modを撮るときのmodなどの定数やmod付き整数クラスのコンストラクタなどにconstexprをつけるとコンパイル時に決定する部分を前計算してバイナリに埋め込んでくれる

二分探索の誤差テクニック

少数で出力する問題の時、答えの値が大きくなれば許される相対誤差の値も大きくなることを利用したテクニック

徹底的前計算

割り算を減らす

割り算の実行コストは高く、足し算や引き算の50倍ほど

セグ木の非再帰化

セグ木を非再帰にすることで高速化が期待できる

セグ木の区間全体取得

セグ木で区間全体の値を取得したい時は区間全体を包含するノードを参照するだけで良い

fillの代わりにmemset

memsetの方がfillより早い

そのBITは必要か、その遅延セグ木は必要か

累積和で何とかなることがある

メモリアクセスを考える

メモリにアクセスする順序はなるべく連続させた方が良い

例として、行列の乗算がある

「競プロにおける実装テクニック14選」

実装速度が順位に大きな差を生む

1 インデントを整える

2 ステップごとに処理を行う場合はコメントをつける

3 変数名を問題文に合わせる

4 GoTo文は使わない

5 関数を多用する

6 For文やIf文の書き方を整理する

7 基本問題は空で書けるように

8 実装方針を紙に書く

9 1行にまとめられるものはまとめる

10 変数名・関数名を用途に応じて統一する

11 グローバrつ変数は用途に応じてコメントをつける

12 ライブラリを整備する

13 累積和

14 二次元座標では回転をするとうまくいくことも

「高速フーリエ変換」

高速フーリエ変換FFTとは離散フーリエ変換DFTを高速にするもの

Markov AO

競プロまとめ2

・全探索 ok

・二分探索 ok

・DFS ok

・BFS ok

・DP ok

・ダイクストラ ok

・ワーシャルフロイド ok

・クラスカル ok

・高速な素数判定 ok

・冪乗を高速に ok

・逆元を計算 ok

・累積和 ok

・グラフ ok

・木 ok

・Union-Find ok

・座標圧縮 ok

・半分全列挙 ok

・行列累乗 ok

・ダブリング ok

・Grundy数 ok

・Rolling Hash ok

・平方分割 ok

・最大流 ok

・最小カット ok

・二部グラフ判定 ok

・二部マッチング ok

・セグメント木 ok

・BIT ok

「プログラミングコンテストでのデータ構造」

slideshare.net/iwiwi/ss-3578491

・Union-Find木

・バケット法と平方分割

・セグメント木

・Union-Find木

ランクと経路圧縮があり２つの工夫をすればほぼ定数

経路圧縮のみが実装が楽で、O(logn)

まとめることはできても分割はできない

・バケット法と平方分割

列や平面をバケットに分割して管理

バケット法の列に関する特殊な場合

n個の列を√n程度の大きさのバケットに分けて管理する

各バケットに含まれる要素√n、バケットの個数√nなのでこれらより良い性質が生まれる

各バケットにどのようなデータを持っておくかによって様々な機能を実現できる

応用力が非常に高い

n個の数の列a1,,,anがあったとき

2.aiをxに変更する

これらのクエリを平方分割で高速に処理をする

・前処理

b = floor(√n)とし、列aをb個ごとのバケットで扱う

各バケットでの最小値を計算しておく

区間に完全に含まれるバケットはそのバケットの最小値

はみ出した要素は個々の値

バケットの数、はみ出した要素の数がともに√nで抑えられる

・aiの値をxに更新するクエリ

要素の値を更新

aiを含むバケットの最小値を更新

これもO(√n)

以上で、前処理O(n)、各クエリO(√n)でRMQが実現！

だが、実際にRMQが必要になった際に平方分割を実装することはあまりなさそう

・各バケットが値ではなく別のデータ構造を持つ平方分割がしばしば出題

このような場合、バケットの大きさは√n程度ではなく、それらのデータ構造の処理の計算量を合わせて調節する

平方分割は√n分木と解釈することもできる

・セグメント木

区間を上手に扱うための木

各ノードが区間に対応づいた完全二分木

平方分割と同様に、各ノードがどのようなデータを持っておくかによって様々な機能を実現できる

応用力が非常に高い

RMQをセグメント木で実装する

・方針

各ノードに、対応づいた区間の最小値を持つ

初期化として、子ノードから順に、再帰的にO(n)

完全に区間に含まれるできるだけ大きい区間で受け止めるイメージ

・aiの値をxに更新するクエリ

aiを含む区間のノード全てについて、値を計算し直す

ともに、各高さで定数このノードにしかアクセスせずO(logn)

この２種類の処理のタイプがセグメント木の処理の基本

平衡処理が必要ない

おすすめの実装方法

・ノードに番号をつける（配列でもつ）

・上の段から、同じ段では左から順に番号をふる



・番号nのノードについて

親：(n-1)/2

子：2n+1, 2n+2

なので簡単に親や子にアクセスできる

この番号づけがうまく働くのはセグメント木が完全二分木だから

・aiの値をxに更新

aiを含む区間のノード全てについて、値を計算しおなす

場所iに対応する一番したのノードの番号はn+i-1でそこから親に辿れば良い

完全に区間に含まれるできるだけ大きい区間で受け止めるイメージ

より形式的には再帰的に

どちらも出ない→2つの子ノードについて再帰的に計算、その２つの値の最小値を返す

ノードの番号から、そのノードに対応づいている区間を知りたい

３つの方法

１、頑張って計算

２、あらかじめ全てのノードについて求めておく

３、再帰関数の引数にしてしまう

３が楽なのでお勧め

この実装ならnが2の累乗でなくても動作する

値の更新はこのままではダメで、同様の手法を再帰関数でかけばok

セグメント木では、区間を考える際に、半開区間で考えると都合が良い

セグメント木に限らず、半開区間を使うとわかりやすい場合は多い

条件を満たす最長の区間の長さがえたい

各ノードについて、そこに含まれる最長の区間の長さ、左側に繋がる部分の長さ、右側に繋がる部分の長さを持つようにすれば効率的にできる

区間に対する処理も再帰しないように実装するとより高速になる

セグメント木：同じものが実現できれば平方分割よりも高速

バケット法：セグメント木よりもさらに応用力が高い

セグメント木の使われ方

１、クエリ系の問題

２、平面走査系の問題

３、DPなどの計算を加速する問題

セグメント木をもちながら平面乗をスキャンするなど

列で、以下の操作が行えるデータ構造

・i番目の要素aiの値にxを加える

・i番目までの数の和を計算する

引き算すれば、ai+,,+ajが計算できる

BITはセグメント木からいらないのーどを削除したものと考えることもできる

セグメント木のノードに二分探索木や配列を持つ

二次元の長方形領域に対するクエリに対応

セグメントきの入れ子を増やせばより高次元にできる

重要なデータ構造

キュー、スタック、デク、二分探索木、順位キュー、Union-Find、BIT、Segment Tree

「ダブリング」

グラフでn個上の要素を求めることを考える

つまり、「頂点1の2^1個上の要素」は、「頂点1の2^0こ上の要素」の2^0個上の要素と等しいということを表す

N回親をたどる時、愚直な方法では全体でN回遷移する必要があるが、ダブリンぐを使った方法なら、Nを二進数展開すると桁数はlog2N+1となるのでその遷移回数はlog2N+1回となる

クエリO(logN)：遷移する回数を二進数展開する、二進数展開して得られたビット列において、立っているビットの数だけ次を繰り返す

立っているビットに対応するnextの値を調べ、その値がさす要素に移動する

「二部マッチング（輸送問題、ネットワークフロー問題）の解放を総整理」

０、始めに

二部マッチング問題は実世界で超頻出

二部マッチング問題とは、マッチングアプリなどに見られるように、２つのカテゴリ間で最適なマッチングを構成していく問題

男と女、ユーザと企業、従業員とシフト、荷物とトラック、工場と店舗、自チームメンバーと相手チームメンバー、選手と区など

実際のビジネス現場において二部マッチングに相当するものを輸送問題と呼んでいるケースも多い

１、問題の分類

・最大二部マッチング

ペアになってもいいという２人の間に線を引いた時に、できるだけ多くのペアを作ろうとした時に最大で何組のペアができるか問題

最適解が必ずしも一通りではない

・重み付き最大二部マッチング問題

そこがペアになったらお互いどれだけ嬉しいかが数値かされている状態を考え、そこからペアリングして各ペアの利得の総和が最大になるようにする問題

このように、に無マッチング問題は基本的に全体最適を目指す考え方

この問題にいろいろな制約が入ってくる

２、二部マッチング問題の解法の分類

・ネットワークフローアルゴリズムまたは類似のアルゴリズム

・数理最適化ソルバーを用いる

前者は簡単だが、ときたい設定が複雑になると無理ゲー

後者は有料だが、すごい

最大二部マッチングはネットワークフローアルゴリズムを用いることで非常に高速に求められる

場合によっては「数百万 × 数百万」程度のマッチング問題を現実的な時間で解ける

重み付き最大二部マッチング問題はいずれの方法用いたとしても、現実的な時間で最適解を導けるのは「数万×数万」程度だろう

それより規模が大きい問題は最適解を導くことを諦めて、現実的な時間内に少しでもより良い解を探索するアプローチをとる

なお、条件設定が複雑になると解くことが本質的に難しい問題になってしまう

例えば、荷物を積む問題などで荷重やトラックの種類が複雑な時は、ネットワークフローアルゴリズムで解くことはできず、近似解を求める専用のアルゴリズムを考案するか数理計画ソルバーに頼ることになる

３、ネットワークフロー問題への帰着

・最大流問題

SからTへとものをできるだけたくさん運ぶ方法を考える問題

各輸送経路には上限が設けられている

SとTをつけて最大流を流せば最大二部マッチングが定まっている

・最小費用流問題

最大流問題はできるだけ多くの量を運ぶ問題だったが、最小費用流問題は決められた量をできるだけ小さなコストで運ぶ問題

先ほどの各辺に乗っている値は上限容量だけだったが、今回はそれに加えて単位フロー当たりのコストが付け加えられている

重み付き最大二部マッチングは最小費用流問題に帰着できる

マイナスをつけたネットワークでコスト最小化しておけば元のネットワークでは利得最大化をしたことになる

４、最大流問題、最小費用流問題を解く

・最大流問題を解く

Dinicのアルゴリズムが知られている

ここでは、男女がそれぞれ１０人ずついてお互いにカップルになっても良いという部分には○そうでない部分には✖️が付いているとして最大で何組のカップルが成立し得るかを求める

・最小費用流問題を解く

最小費用流アルゴリズムを実装したものを参照

従業員が５人いて仕事は１０個ある

A~Eにそれぞれ二個ずつ仕事を割り振りたいとして、それぞれの従業員にとってそれぞれの仕事がどのくらい得意かが数値化されているとする

うまく全体最適化するように仕事を割り振る

必ずしも、それぞれのworkerが一番得意とするものはひとまず割り当ててしまうのが全体最適を導くとは限らない

さらなるテクニック

重み付き最大二部マッチング問題を最小費用流問題に帰着する時利得にマイナスをつけてそれをコストと考えて帰着してきましたが、もしマッチングサイズがあらかじめ決まっているのならば、gainにマイナスをつけて-gainとする代わりに十分大きいMからgainを引いた値M-gainを用いるというテクニックがある

こうすることでコストが非負になるので、より高速な最小費用流アルゴリズム（具体的にはサブルーチンのBellman-Ford法をDijkstra法に置き換えたもの）を用いることができてより高速な求解が可能になる

５、プログラミングコンテストのススメ：細かい要求に強くなる

現実世界で生じるに無マッチング問題は様々な制約が絡んできたり、最適化対象も複数にまたがるケースも少なくない

しかし、ある程度のことは最大流問題、最小費用流問題を解くグラフネットワークを工夫することで対応できる

1章の最後のその他のバリエーションであげたことは全て対応できる

６、どうしても解けない問題は数理計画ソルバーへ

現実世界の問題は応用にして複雑な制約条件が絡み、ネットワークフローアルゴリズムで解くことは難しい

そんな時は問題に応じて近似解法を考案する数理計画問題として定式化して数理計画ソルバーにとかせよう

数理最適化ソルバーを用いると、かなり複雑な制約条件も加味して考えることができる

定式化する能力をつけろ！

「二部グラフ判定問題」

二部グラフとは、全ての辺が、自分チームと相手チームを結んでいるように分けることができる

例えば、男女の複雑な三角関係や四角関係を図に書いたとき、男女間でしか線が引かれていなければ二部グラフと言える

二部グラフ判定問題とは、与えられたグラフが二部グラフかどうか、という問題

全ての辺において一方が黒、もう一方が白となるように頂点を塗ることを考える

二部グラフの場合、ある頂点の色が黒だとすると、そこに隣接している頂点は一意に白ときまる

最初は適当に一箇所を黒で塗ってあとはDFSで白、黒、とどんどん塗っていって矛盾がなければ二部グラフ

単純や！

「最小カットについて」

たくさんの制約がある問題を解く一般的なテクニックとして、いい感じのグラフを作ってその最小カットが答えというのがある

頂点がたくさんあって、それを赤と青に塗り分けるという問題を考える

最小カットで解ける問題は実は、

・頂点がたくさんある、それを赤と青に塗り分ける、全部の頂点を必ず赤か青に塗らなくてはいけない

・必ず赤色に塗らなくてはいけない頂点と青色に塗らなくてはいけない頂点が存在する

・「Xが赤で、Yが青のときにZ円の罰金がかかる」という制約がたくさん

・罰金の最小値は？

という問題だけ

これの解法は

・「Xが赤でYが青の時にZ円の罰金がかかる」ならX -> Yに容量Zの辺をはる

・SからTに最大流

・流せた量が答え

「RollingHashとSuffix Array」

テキストT：長さn

パターンP：長さm

自明な方法O(nm)

ここで、ローリングハッシュを使う

文字列を値にするハッシュ関数を用いて、値が一致した時に文字列が一致したとする

ハッシュとは、文字1文字を値とし、その値と基数の積の総和をハッシュ値とするハッシュ関数を使う

愚直にハッシュ値を毎回計算すると、ハッシュ値の計算にO(m)時間かかり、結局O(nm)時間かかってしまう

なので、ローリングしながらハッシュ値を計算することで毎回のハッシュ値計算をO(1)にする

しゃくとりみたいな感じか！

文字列のある場所から末尾までの文字列を接尾辞という

１つの文字列の全ての接尾辞を辞書順にソートしたものを接尾辞配列という

自明にO(n^2logn)で作れる

接尾辞配列で何ができるか？

文字列の検索がO(mlogn)で解ける

場合によってはローリングハッシュよりも高速に解ける

LCP array(Longest Common Prefix Array)との組み合わせで繰り返し出現する部分文字列を見つけることができる

基本的なアイディアはダブリンぐ

rank_k(i)とrank_2k(i)のペアをソートすることでi文字目からi+2k文字目まではソートされる

rankのソートをlogn回行うことで構築可能

最新の接尾辞配列の構築法として、SA-ISという手法で線型時間構築が可能らしい

「蟻本片手に学ぶローリングハッシュ」

文字列検索は、中級以上で頻出の分野

よくある形式では、検索対象文字列Sに検索文字列が含まれているかを判定する

愚直な開放ではO(nm)

より高速なアルゴリズムを使わせたい意地悪な問題作成者はO(nm)で間に合わないように問題設定する

ローリングハッシュはO(n+m)の計算量でできる

ハッシュ要素

ローリングハッシュでは文字列Aから互いにそな奇数bとmodの除数hを用いてハッシュ値を求める

hが十分に大きければ文字列ごとのハッシュ値はほとんどユニークなので、文字列s,tのハッシュ値が一致したとき、高確率でs=tであると言える

あれ？

m文字のハッシュ値の計算にはO(m)かかるので、愚直かいと変わらないのでは？

ここからがローリングのでばん

前の文字列のハッシュを利用してずらした部分文字列のハッシュを求める

この連鎖的な生成によって１つの文字列についてのハッシュ値の計算がO(1)になる

「座標圧縮」

その問題の配列とかを関係性を保ったまま小さくすること

大小関係が重要なら、小さい順ランキングをつける感じ

sort(v.begin(), v.end());

v.erase(unique(v.begin(),v.end()),v.end());

広大な領域を対象とする問題はコンピュータの手に負えない



要するに座標圧縮とは、各値の大小関係を崩さないように新しい数値を割り当てること

座標圧縮するにはソートと再割り当てが基本でO(nlogn)



「競プロにおけるDP更新最適化まとめ(CHT, MongeDP, AlianDP, インラインDP, きたまさ法,行列累乗)」

・セグメント木や累積和

・行列累乗

DPの更新式を見ると一回の更新操作が行列の形になることがある

この場合は繰り返し二乗法の容量でN乗しておくことでN番目の要素を高速に取り出せる

・Conve Hll Trick

関数の形式になっている区間最小値を素早く見つける手法

・分割統治

・MongeDP

最適二分木問題

・AlienDP

よくわからん

・インラインDP

セグメントツリー全体をDPの配列として更新

・きたまさ法

k項多項式で漸化式が与えられた時、N番目の要素をO(K^2logN)で求める

「半分全列挙による全探索の高速化」

Nこの要素の組み合わせを計算する際、半分ずつの２グループに分けてそれぞれを列挙し、組み合わせ方を高速に求める工夫を半分全列挙という

例えば、N=40の時、2^40 = 10^12なので間に合わない

だが、Nが20なら間に合う

こういうときに半分に分けて高速化する

グループの中からいくつか選択して合計値を計算することを考える

２つのグループがあるので、10^6通りの組み合わせが２つできる

普通にAとBを組み合わせて合計値を計算しようとするとやはり間に合わない

しかし、問題の条件は合計値がS以下となる最大の値を求めること

Aの要素aを固定すれば、「S-a以下の最大の要素をBから選ぶ」という話に変わり、これは二分探索で構想に求められる

「競プロにおけりNim, Grundy数とNimK」

Nim, grundy数がわかっていると、盤面を共有して二人で対戦し、勝敗が必ず決まるタイプのゲーム問題がさくっと解ける

Nimとは

一般的に2人で盤上の石とかコインを取り合う

１つの山を選択し、そこから１つ以上、好きなだけ取り除ける

１つも取れなくなった方が負けになる

これには必勝法が存在し、ゲームが始まる前に必勝か必敗かわかってしまう

必勝判定は、各山の枚数をXORでまとめたときの値が0ではない先手の勝ち

0である：先手の負けとなる

１山の時 先手が勝ち

２山の時 先手がとった数だけ後手が一方の山から取れば常に後手が勝てる

山の枚数が違う時は、先手が山の枚数が同じになるように取ると、後手を先手が入れ替わった先の状況が再現できる

3山ある時、のこり枚数のxorが0になるように相手に手番をの渡すことができれば勝ち

N山ある時も、残り枚数のxorが0になるように相手に手番を渡すことができれば勝ち

Grundy数

ゲームの値、ざっくりいうと0の時負け、そうでない時かち

求めかた：現在の状態から移行できる状態のGrundy数の集合のうち、存在しない最小の非負整数

Nいっちゃだめゲーム

0から初め、各プレイヤーは1から3までの数字を選択し、現在の数字に加算する

最初にN以上の数字を作成した人の負け

2人が最適な選択をするとして、Aliceが先手の時、Aliceは必勝か？

O(1)解法：周期から求める

O(n)解法：何も考えずGrundy数を求める

負けの状態のGrundy数は0

今回負けなのは数字がN-1の時

Grundy数を繰り返し求めて行って、0の時0かどうかを見ることで必勝かどうか判定できる

「BIT」

次のことができるデータ構造

・iが与えられた時累積和を計算

・iとxが与えられた時aiにxを足す

これはセグ木でも表現できる

計算クエリは、区間を完全に被覆するまで下がっていけばいい

更新クエリは関係ある区間を更新していけば良い

セグメント木の無駄なところ

例えば、左と上の情報から得られるところ（右側）は覚える必要がない

この考え方を使えば、BITのデータ構造に辿りつける

BITのしくみ



区間の長さは配列のインデックスを二進表示したときのLSBと関係があるので、各操作をビット演算で表現できる

BITでの和の計算

0になるまでLSBを減算しながら足していけば良い

aiにxを足すときは、iにLSBを加算しながら更新していけば良い

BITの特徴

要素数Nに対してサイズNの配列で実現可能

和の計算も値の更新もともにO(logN)の計算量ですむ

実装が比較的簡単

LSB は i & (-i)で取得できる

二次元への拡張も簡単

「繰り返し二乗法」

1 求めたい数字を二進数で表す

2 これを計算できる漸化式を考える

3 この漸化式による計算を考える

long myPow(long x, long n, long m){

if(n == 0)

return 1;

if(n % 2 == 0)

return myPow(x * x % m, n / 2, m);

else

return x * myPow(x, n - 1, m) % m;

}

for文の方が早い

というのもプログラムにおいて関数のcallを使うのは重い処理だから

int test_pow4(int _x, int _n)

{

int ret = 1;

while(0 < _n)

{

if((_n % 2) == 0)

{

_x *= _x;

_n >>= 1;

}

else

{

ret *= _x;

--_n;

}

}

return ret;

}

「nCkを素数で割ったあまりの計算と逆元のまとめ」

aに項係数が大きくなると、二項係数がオーバーフローしたり、1つの二項係数を計算するのにO(n)だけかかってしまったりする

１、k <= n <= 10^7でPが素数のとき

はじめにO(n)でmodpでの階乗とその逆元を求めておくと、1つの二項係数をPで割ったあまりが定数時間でもとまり、高速に計算ができるようになる



nが非常に大きいと、階乗と逆元を覚えておくためのメモリが足りなくなるので注意が必要

using namespace std;

const int MOD = 1e9 + 7;

vector<long long> fact, fact_inv, inv;

/*  init_nCk :二項係数のための前処理

計算量:O(n)

*/

void init_nCk(int SIZE) {

fact.resize(SIZE + 5);

fact_inv.resize(SIZE + 5);

inv.resize(SIZE + 5);

for (int i = 2; i < SIZE + 5; i++) {

}

}

/*  nCk :MODでの二項係数を求める(前処理 int_nCk が必要)

計算量:O(1)

*/

long long nCk(int n, int k) {

assert(!(n < k));

assert(!(n < 0 || k < 0));

}

２、nが巨大でPが素数の時(k<=10^7, n<=10^9)

クエリ：nCk = n/1 * (n-1)/2 * ***

計算量

nが固定じゃない時は

前処理：O(k)

クエリ：O(k)

nが固定の時

前処理：O(k)

クエリ：O(1)

３、k<=10^5の時

直接計算すれば良い

４、k<=n<=5000でPが素数じゃないとき

DPで前計算しとけばよい

逆元とは、ModPの世界で、掛け算すると1になるものである

つまり、mod5の世界では、2の逆元が3になる

つまり、modpの世界で考えれば、普通にnCkを式で表して分母にきてるものは逆元として扱いそれを掛け算してやれば良い

modPの世界における1/iの値aはmodpの世界におけるiの逆元になる

逆元の計算方法（拡張ユークリッドの互除法）

拡張ユークリッドの互除法を利用すると、iの逆元をO(logP)で求められる

逆元の計算方法（フェルマーの小定理と繰り返し二乗法）

拡張ユークリッドの互除法

フェルマーの小定理と繰り返し二乗法

では0からnまでの逆元を求める場合O(nlogP)かかってしまう

ですが、iの逆元をP%iの逆元を利用して求めることで1つあたり、O(1)で求めることが可能になる

「累積和を何も考えず書けるようにする」

累積和は添字の扱いなど、頭がごっちゃになる

応用範囲が非常に広いことから、整理する価値の高い手法

１、累積和でできること

適切な前処理をしておくことで、配列上の区間の総和を求めるクエリを爆速で処理できるようにする手法

前処理で全てを記憶しておいたら、記憶容量がめっちゃ必要になってしまう

そこで、

・前処理にO(N)だけ時間をかける

・記憶容量はO(N)

・クエリにO(1)で答えられる

という筋の良い方法が累積和である

２、累積和とは



このような捉え方をすれば累積和は明快にわかる

「プログラミングコンテストでのDP」

ナップサック問題

品物1から順に使う場合、使わない場合の両方を試していく

この場合2^n時間かかってしまう

ここで大切な考察として、search(i,u)はi,uが同じなら常に同じ結果ということを考える

それまでにどの商品を選んだのかを重要ではないということ

ここで、同じ探索を2度しないようにする

すると、O(2^N)→O(NU)に改善できた

１、再帰関数のメモ化

２、漸化式+ループ

という２つの方法がある

メモ化再帰は、全探索の関数searchを改造すれば良い

好きな方法を使えば良い

大きすぎる配列をローカル変数として確保しない方が良い

大きい配列はグローバルに取る

・スタック領域とヒープ領域

・スタック領域の制限

DPの使いかた

おすすめの流れ

１、全探索によるアルゴリズムを考える

２、DPにする

どんな全探索を考えれば良いのか

つまり、どんな全探索を考えればDPにできるのか？

例えば、ナップサック問題の際に使った全探索について、色々と全探索は考えられる

例えば、i番目以降の品物で、重さが総和がu以下となるように選ぶ、またそこまでに選んだ品物の価値の和がvsumとして３つの引数を持たせて全探索することもできる

引数が増え、DPにできない

各(i,u,vsum)で一度ずつ計算すればできるが効率が悪い

このようなことを防ぐため、全探索の関数の引数は、その後の探索に影響のある最低限のものにする

選び方は、残る容量によるが、そこまでの価値によらないので、vsumは引数にしない！

・グローバル変数を変化させるようなことはしてはいけない

・状態をできるだけシンプルにする

「どの商品を使ったか」はだめ

「今までの使った商品の重さの和」はOK

ここで扱った事項はアルゴリズムを考える際ではなく、DPのアルゴリズムをより効率的にしようとする際にも重要

例１：経路の数

ある地点からの経路の数はそこまでの経路によらない

例２：最長増加部分列

後ろの増加部分列は一番最後に使った数のみよる

例３：最長共通部分列

(Xのi文字目以降、Yのj文字目以降)で作れる共通部分列は同じ

DPに強くなるために

慣れるために自分で何回もやるべき

典型的な問題は知るべき

ナップサック問題でも、条件によっては全探索の方が早いこともある

集合を状態にするDPをビットDPという

例えば、TSP

NP困難問題であることがわかっている

全探索はO(n!)

n <= 10ぐらいまで

DPを用いるとO(n^2*2^n)にできる

n <= 16ぐらいまで

状態は、既に訪れている街はどれか、今いる街はどれかの２つ

そこまでの順序に関わらずその後の最適な道のりは等しい

既に訪れている街はどれかをビットマスクで表現できる

メモ化再帰　vs DP

メモ探索の利点

・ループの順番を考えなくて良い：ツリー、DAG

・状態生成が楽になる場合がある：状態が複雑な問題

・起こり得ない状態を計算しなくていい

配るDPともらうDP

・配るDP：各場所の値を計算していくのではなく、各場所の値を他のやつに加えていくようなDP、メモ化探索ではできない

・確率、期待値の問題で有用なことがある

「計算量の話」

だいたい1秒がO(10^8)ぐらい

メモリはO(10^7)が限界くらい、1MBでintが250000という目安

問題の変数の制約からアルゴリズムの計算量の見当がつく

変数の値が大きいほど計算量も大きくなるので、できるだけ小さい変数の値を使うアルゴリズムを考えたい

制限から計算量予想

10^6 → O(N)かO(NlogN)

10^5 → O(NlogN)かO(N(log2N)^2)

3000 → O(N^2)

500 → O(N^3)

100 → O(N^3)

50 → O(N^5)

20 →O(2^N)or O(N*2^N)

・O(N)

貪欲法

しゃくとり法

木構造関係の前処理(深さ、部分木のサイズ、重心、DFS、BFS)

累積和の前処理

いもす法の後処理

エラトステネスのふるい

1~Nまでの数字の逆元の取得

aho crasick法による文字列探索

グラフの閉路判定：DFSするだけ

グラフの強連結成分分解：強連結成分を圧縮するとDAGになる

DAGのトポロジカルソート：辺が全て小さい番号から大きい番号に伸びているように頂点を番号付

DAGに変形した後にDP：あらゆるDPはDAGの問題に変更可能

・O(N^2)

全頂点対の走査：グラフを作る段階におこなうあらゆるアルゴリズム

ベルマンフォード法：単一始点最短経路を求めるアルゴリズム、負の閉路があっても大丈夫、特殊な線型計画問題の双対

・O(N^3)

ワーシャルフロイド法：全点対間最短経路を求める方法、実装が非常に楽で定数が軽い

二部グラフの最大マッチング：安定結婚問題みたいな

・O(√N)

素数判定

約数列挙

・O(logN)

二分探索

ユークリッドの互除法

繰り返し二乗法

set, map, priority_queueのクエリ

平衡二分探索木のクエリ

・O(NlogN)

ダイクストラ法：負閉路があると動かない

エンベロープによる走査：複数の一次式に対して、最小値や最大値をなぞる方法、グラフの下辺や上端をなぞる感じ

ソート

N^2アルゴリズムの分割統治

ダブリンぐの初期化

・O(Na(N))

Union-Find：ほぼ定数

「数え上げの基礎」

数え上げを解くことで、以下の力がつく

・問題を言い換える力

・うまいまとめ力

・個別事象を考える力

公式を覚えるだけでは確実に解けない

不得意でも思考の仕方を覚えればなんとかなる

発想の典型を知るべき

重複組み合わせは発想が必要



「プログラミングコンテストでのデータ構造（平衡二分探索木）」

・二分ヒープ

・組み込み辞書

・Union-Find木

・Binary Indexed Tree

・セグメント木

・バケット法

・平衡二分探索木

・動的木

・永続データ構造

後ろ３つをやる

ヘ〜ぐらいの気持ちでOK

アイデアだけじゃなく、実装まで立ち入り、簡潔に実装するテクを伝授



普通の二分探索木の偏りについて

1,2,3,4の順に挿入していくと、高さがO(n)になって処理にO(n)時間かかってしまう

こういった意地悪に耐える工夫をする二分探索木が平衡二分探索木である

平衡二分探索木は必要？

配列、線型リスト

set, map

BIT、 バケット法、 セグメント木

実装が面倒なので楽に避けられたら避けたい

実際のところ、本当に必要になる問題はレア

例1 範囲の大きなRMQ

クエリ先読みして座標圧縮し解けばセグ木でもできる

必要な場所だけ作るセグ木でいい

例２ 反転のあるRMQ

大人しく平衡二分探索木をかけ

いっぱいある

・ガチ勢：赤黒木

・コンテスト勢：実装が楽なのを組もう！

コンテストでの平衡二分探索木

たいてい、列を管理するために使われる

挿入、削除、分割、連結、質問、更新ができる木を作ろう！

Treapの思想

・根がランダムに選ばれるようにする

・これだけで高さがO(logN)

・乱択クイックソートと同じ

乱数を用いる平衡二分探索木

各ノードはキーのほか、優先度を持つ

１、キーをみると二分探索木

２、優先度を見ると、二分ヒープ

優先度が最高のやつが根になる

treapの実装法

・insert-eraseベース

・merge-splitベース

「動的木編」

・動的木にもいくつかある

・ポピュラーな動的木：Link-Cut木、Euler-Tour木

Link-Cut木

木を処理する神がかり的なデータ構造

「指数時間アルゴリズム入門」

NP困難問題を解くためのアルゴリズムを扱う

近似アルゴリズムやヒューリスティック、整数計画、FPTアルゴリズム、厳密指数時間アルゴリズムなど

効率的な指数アルゴリズム

2^|V|のアルゴリズムならコンテストでもよく出題されている

指数の底も重要である

・何の指数？

DP、準指数時間、グラフの幅

・指数の底は？

半分全列挙、探索アルゴリズム

・FPTアルゴリズム

FPTとは、有界探索木、カーネル

・包除原理

数え上げ、畳こみ

・余談

「指数時間アルゴリズムの最先端」

「DPの問題を機械的にときたい」

by opt_coder

１、計算量を度外視して素朴なDPテーブルを考える、高次元であるほど2と3が楽

２、DPテーブルを更新するための漸化式を考える

３、問題の答えの値をDPテーブルを使って式として表す

４、DPテーブルの要素数とDPテーブルの1要素の更新に必要な計算量を調べ、制限時間を判断

(a)DPテーブルの要素を縮めたより低次元のテーブルを作り、漸化式と答えの式を新たなテーブルを使って書き直す

(b)

「ソートを極める」

「スタックとキューを極める」

「BFS超入門」

vector<vector<int> > graph(n);

for(int i=0; i<m; i++)

{

int a, b;

cin >> a >> b;

a--; b--;

}

vector<int> dist(n, -1);

vector<int> ans(n, 0);

queue<int> que;

que.push(0);

while(!que.empty())

{

int v = que.front(); que.pop();

{

que.push(nv);

}

}

計算量はO(N+M)

DFSのが良い場合

・解がスタートから遠いところにあることがわかっていて、BFSによって虱潰しが現実的ではない場合でもDFSなら枝かりや探索順序の工夫によって解が求められることがある

・グラフの頂点の順序に意味がある場合、たとえば辞書順最小な経路から順番に探索したい場合

・キャッシュにメモしながらDPを行う場合など、帰りがけ時に子ノードたちの結果をまとめるような処理が重要な場合（メモ化さいき）

BFSのが良い場合

・最短経路

・探索空間自体はとても大きいが、解が近くになることがわかっている場合

BFSの応用

・パズルを解くための最小手数

・Facebookなどの友達関係において、ある人からあるひとへ何ステップで行けるか

また、キューの使い方を工夫することで

・サイクル検出

・後退解析

ができる

「DFS超入門」

「大規模データ探索」

「セグ木とBITについておじさんがまとめてみた」

配列に対して以下のクエリを考える

1 A[i} += w (add)

これらをO(logN)で行いたい

listは2,3がだめ

累積和はaddがだめ

なのでセグメント木を考える

セグメント木は長さ2N-1の配列

構築はO(N)

演算はaddじゃあなくても可換であればあOK(max, min, gcd, lcm)

３つのクエリをO(logN)で実現する構造体はセグ木で実現されたのにこれ以上何が必要なのか？

実は必要はない

BITはセグ木よりも時間計算量、空間計算量を定数倍短縮しただけで機能面でいえばセグ木よりもできることは限られる

だが、メリットとしては、

・実装が楽

・多次元化が容易にできる

・時間計算量、空間計算量が小さい

が挙げられる

デメリットとしては、

・Aを保持していないため復元できない可能性がある

・実はsumクエリは一般には計算できない

セグ木の各段の基数番目を消してindexを変えたものがBITである

addはLSBをたし、sumはLSBを引けば良い

sumクエリはfが逆演算を持たなければ0からの和しか計算できない

逆にfが逆演算を持てば計算できる

class SegmentTree:

def __init__(self, A, dot, e):

n = 2**((len(A)-1).bit_length())

self.__n = n

self.__dot = dot

self.__e = e

for i in range(len(A)):

for i in range(n-1,-0,-1):

def update(self, i, c):

i += self.__n

node = self.__node

while(i!=1):

i//=2

def sum(self, l, r):

vl, vr = self.__e, self.__e

l += self.__n

r += self.__n

while(l<r):

if(l%2==1):

l += 1

l//=2

if(r%2==1):

r -= 1

r//=2

return self.__dot(vl, vr)

def bisect(self, l, r, x, increase=True, i=1, a=0, b=-1):

if(b == -1): b = self.__n

if(increase):

if(i >= self.__n): return i-self.__n

lv = self.bisect(l, r, x, increase, 2*i, a, (a+b)//2)

if(lv != -1): return lv

return self.bisect(l, r, x, increase, 2*i+1, (a+b)//2, b)

else:

if(i >= self.__n): return i-self.__n

rv = self.bisect(l, r, x, increase, 2*i*1, (a+b)//2)

if(rv != -1): return rv

return self.bisect(l, r, x, increase, 2*i, a, (a+b)//2)

class BIT:

def __init__(self, A, dot=lambda x, y:x+y, e=0, inv=None):

n = len(A)

self.__n = n

self.__dot = dot

self.__e = e

self.__inv = inv

for i in range(1,n+1):

j = i+(i&-i)

def add(self, i, w=1):

i += 1

while(i <= self.__n):

i += i&-i

def sum(self, i):

res = self.__e

while(i > 0):

i -= i&-i

return res

def range_sum(self, l, r):

assert(self.__inv)

return self.__inv(self.sum(r), self.sum(l))

def bisect_left(self, w, increase=True):

n = self.__n

k = 2**((self.__n-1).bit_length())

res = 0

now = self.__e

while(k):

res += k

res += k

k //= 2

return res

from operator import add,sub

N=len(A)

bit=BIT(A,add,0,sub)

k=37

print(bit.bisect_left(k)) # 7

「ライブラリ集」

「いもす法」

「競技プログラミングで解法を想う就くための典型的な考え方」

競技プログラミングで問題を解くには

1 問題で要求されていることを言い換える

2 知っているアルゴリズムやデータ構造を組み合わせてとく

が必要

ここでは、問題の言い換えについて焦点を当てる

1 入力の大きさから考える

2 一気に２つ以上のことをしようとしない

3 操作する問題

4 数え上げ問題

5 区間問題

6 ゲーム

7 制約を満たすものを数えるとき

8 構築形問題

9 K番目の数を求める

10 xor系の問題

11 マンハッタン距離

12 グラフ系

13 上端を満たす最大値or最小値を求める

14 偶奇性に注目する

15 最大マッチング

16 その他

1 入力の大きさから考える

Nが8前後：順列の全探索など

Nが10~20：bit全探索、Nが少し小さければbitDP

Nが30~40：半分全列挙

Nが50前後：O(N^4)

Nが300~500：O(N^3)、区間DPなど

Nが1000：O(N^2logN)、O(N^4)を半分全列挙、一回当たりO(NlogN)で判定できる二分探索

Nが3000：O(N^2)

Nが10^5：O(NlogN)でソート、一重ループと二分探索、DP、二分探索の判定をO(NlogN)ならギリギリ

Nが64bitにおさまらん：桁ごとに考える、桁DP

小さめのmod：剰余を考える

2 一気に２つ以上のことをしようとしない

２つ以上のものを考えると難しくなってしまう

・分解して考える

問題設定が複雑だとしても、操作によって得られる結果を分けたりすることで問題設定がシンプルになることがある

・固定して考える

変数がいくつかあるときは同時に考えるのではなく、あるものを固定して考える

3 操作する問題

・不変量に注目する

ある操作をK回以内行う、だったり、好きなだけ行うだったり

・偶奇性に注目する

操作をしても偶奇性が変化しない場合や逆に変化する場合がある

・操作の順番を入れ替えても良いか

入れ替えて良いなら、都合が良い順番でやる

・操作を逆順に考えるとどうか

特に操作の結果が最初からわかっているとき

・操作をして元に戻せるか

操作をすると同じものになるものをまとめて、同値類として考えることも

4 数え上げ問題

〜が何通りか求めよ系の問題

単純に全探索しても間に合わないことがほとんどなので何らかの工夫をする必要がある

・DPで状態をまとめて全探索を高速化

DPを全探索の高速化とみなす

・平均がKとなる組み合わせ

合計値がK * 個数となる組み合わせ

元の値を全て-Kした数列で合計値が0となる組み合わせに変換すると良い

5 区間問題

典型と言っても良い累積和系の問題

累積情報か、セグメントツリーを利用して解ける場合がある

・左右両方から累積情報を前処理しておく

左右両方から累積和を前処理して保存しておくと、後の計算を効率よくできる場合がある

１つだけ除いたものを考える場合なども有効

・区間に足すとき

imos法や区間和対応のBITなどで解ける場合がある

・区間を削除・圧縮・合成するとき

区間DPを使う時がある

・等差数列の加算は差をみる

交差dの等差数列を区間に加算する場合は加算した値に差がどれだけ変化するかに注目してみるとそのほとんどが交差dだけ変化するのに注目すると分かりやすくなる場合がある

・区間を反転させる問題

ライツアウト系の問題

以下のことに注意する

-同じ操作を二回すると元に戻る

-操作の順番を入れ替えても同じ

-反転区間の端点に注目するとgreedyに決まることがある

6 ゲーム

最善戦略を探す

・不偏ゲームはGrundy数

不偏ゲームはGrundy数で先手後手のどちらが必勝かを判定できる

・後退解析をする（最後から考える）

ゲームが終了した時から遡って考えると最適な行動がわかることがある

・同じ手段を選び続けるのが最善

いくつか手段があるときは、同じ手段を撮り続けるのが最善の時がある

・一方が最大化、他方が最小化

-場合わけなどで何らかの最善戦略を探す

先手と後手を場合わけして最善戦略を探す

-最大化側はx以上、最小化側はx以下を達成できるか考える

両者が最適に行動するとxになることがわかる

7 制約を満たすものを数えるとき

・~が１つ以上というときは余事象を考える

8 構築形問題

・構築できない場合が存在しないことがある

できない場合は-1を出力せよという問題も全て構築できることがある

・上限ギリギリでの構築ほうが全てに当てはまることがある

~回ギリギリやNこギリギリの構築ほうが全ての場合に適用できることがある

・2N回以内に終了ならN回以内に特殊な状況に持っていく

全要素に対して１回ずつ合計N回操作を施して「N回以内に簡単に解ける特殊な状況」に持っていくと解けることがあります

9 K番目の数を求める

・要素の値が小さいとき

BITなどでK番目の数を求めることができる

・二分探索で求める

「小さい方からK番目の数がX」

⇔「X-1以下の数はKこ未満でX以下の数はKこ以上」

⇔「X以下の数がK以上となる最小のX」

中央値を求めるときにも使える

10 xor系の問題

・xorを「繰り上がりのない足し算」とみる

xorはあるビットについて同じ数字だったら0に違う数字だったら1なので繰り上がりのない足し算

逆に、繰り上がり部分も表せる

・xorを桁ごとに考える

xorが繰り上がりのない足し算ということは、ある桁がどんな数であっても、xorをして他の桁に影響を与えることはない

故に、桁ごとにxorして最後にまとめるという手法が使えることがある

・同じ数をxorすると元に戻る

11 マンハッタン距離

・45度回転させる

座標を45度回転させると、あるマンハッタン距離で移動可能な範囲が正方形になる

・差の最小値は中央値を用いる

へーーー

12 グラフ系

・代表的なグラフで実験してみる

-パスグラフ（直線上につなげたグラフ）

-スターグラフ（１つの頂点から、他の全ての頂点に１つずつ辺が出ているグラフ）

-完全グラフ（任意の２点間に辺があるグラフ）

-完全二部グラフ（二部グラフのうち、可能な限り辺を繋いだもの）

-パスグラフに少し変をたしグラフ

・木は二部グラフであることを利用する

木は二部グラフであることを利用して２つにグループ分けをすると分かりやすくなる場合がある

偶数回の移動で同じグループに戻ってくるし、奇数回の移動で違うグループへ移動する

・木の直径を考えてみる

木の直径について考えると性質が見えることがある

13 上端を満たす最大値or最小値を求める

・条件を満たすように最大化、最小化は二分探索

ある条件を満たすようにxを最大化したり最小化する場合は二分探索が使えることがある

特に、平均、最大値の最大化、最小値の最大化など

・選択肢が少ない方から見て貪欲

制約の厳しい方からみると候補が少ないようなときに使える考え方

14 偶奇性に注目する

・abs(x-y)、差の計算

・xorで偶奇をみる

・奇数を偶奇性でみる

３などの奇数が出た場合は偶奇性に注目すると良いことがある

木においては、木を二部グラフだとみると、偶奇性が分かりやすくなることがある

15 最大マッチング

・フローを利用した最大マッチング

有名問題

・貪欲にマッチングできることがある

鈍グラフじゃなかったりエッジの数が膨大になりそうなときは貪欲にマッチングが取れることがある

16 その他

・二次元座標を二部グラフで考えてみる

二部グラフの左側：x座標

二部グラフの右側：y座標

二部グラフの辺：点(x,y)とするとうまくいくことがある

・順序がある場合は有向グラフで考えてみる

特に半順序集合の場合はDAGで表現でき、これはトポロジカルソートができる

・凸関数の極値は三分探索

三分探索や黄金分割法

・数列の番号に対する単調増加な性質はしゃくとり法

lを固定したときに数列のl番目からr番目が条件を満たすような最大のrをf(l)と表せて、これが単調増加ならしゃくとりほうが使える

・等比数列や~進数は割ったあまりで考える

「ネットワークフロー総整理」

「１週間で身に付くアルゴリズムとデータ構造」

「競プロの初歩的思考法」

競プロには三種の神鬼が存在する

・数学

・メモ化

・分割統治法

例えば、DPはメモ化と分割統治法の組み合わせ

高速フーリエ変換は、数学、メモ化、二等分という概念の組み合わせである

「DPいろいろ」

「分野別 初中級者が解くべき過去問100問」

全探索：全列挙

全探索：工夫して通り数を減らす

全探索：ビット全探索

全探索：順列全探索

二分探索

DFS

BFS

ナップザックDP

区間DP

bit DP

その他のDP

ダイクストラ

ワーシャルフロイド

最小全域木

素数判定

高速な冪乗

逆元を使う問題

累積和

Union-Find

その他のテクニック

実戦問題

数学的な問題

————————————————————————————————

「上級者が解くべき50選」

座標圧縮

半分全列挙

行列累乗

ダブリング

Grundy数

Rolling Hash

平方分割

最大流・最小カット

二部グラフを扱う問題

二部マッチングを扱う問題

BITを使う問題

RMQ

遅延評価セグメント木

その他のテクニック

拡張ダイクストラ法

えびまさんのYoutube ch

なな色言語で競技プログラミングをする資料