maxflow 個人的備忘録
色々読んで適当に掴んだ雰囲気をなぐり書きしていくので表現の厳密さ，丁寧さには欠けると思います 読み込んだのをそのまま吐き出す感じだったりするのであらゆる記事の丸パクリっぽくなるかもしれないし，独自の解釈が混ざっているので信憑性に欠ける部分も多いかも，あと読みやすさも全く考慮していません（ごめんなさい）
maxflowとは
maxflowはあるグラフを考えたときに，そのうちの２頂点s→tにできるだけ大量に水を流すとmaxどれくらい流れますかという問題です（それはそう）
双対問題について（最小カット）
では，上記の問題で「tに水が流れないような辺の取り除き方を考えた時の，取り除いた辺の容量の総和を最小化せよ」という問題を考えてみます．まず，最大流量をFとするとFまでは流せちゃうわけですから，F未満であれば絶対に水を流せてしまうのは明らかです．
最大流量が流れる時の辺の状態に思いを馳せてみると，任意の辺(u→v）に流れる流量fはその辺の容量をcとして，
f=min(c,(uに入ってくる流量)-(uから出る他の辺に流れていく流量))
であると表せます．ここでuから直接到達できる頂点の集合Vを考えると，
(V全体に入ってくる流量の総和)<=(uに入ってくる流量)
であるはずです．ここで，始点sには無限の水が注がれているものと考えてください．すると，u→（V内の各頂点）へ流れるときにもし辺の容量が十分大きかったら，流量は減らないはずです．つまり元々のmaxflowを「なんで高々それだけしか流せないんだ」という問題であると考えると，実際に流したかった流量に対して辺の流量が小さい，すなわちf==cとなるような辺が本質であるような気がしてきます．そのような辺集合をEとすると，Eの部分集合に辺の容量の総和がFとなるような集合E'が存在します．それは当たり前で，元々始点には無限の水を注いでたのに，その制約のせいでFしか流せなかったとみなせるからです．
さらにE'の各辺はすでに辺の容量ギリギリまで流れていることを考えると，それらの容量をさらに小さくしていけばどんどんtへの流量が少なくなっていってやがて0に収束していくことがわかります．つまりE'が元の問題を満たす集合であると言えて，また，求める総和はFであるということがわかります．
この問題を最小カットと呼び，maxflowの双対問題（＝同じ解き方で求めることができる）として有名です．
ここでのポイントはある条件Lを考えたときに「Lを満たすようにある量を最大化する」という問題だったのが，「Lを満たさなくするようにコストを最小化する」という問題に帰着できるということです．最大化する問題だったはずなのに最小値を求めるのと等価であると言う事実は凄く気持ち悪いですが，最大流量はあくまで下界を与えるものだと思うとすっと入ってきやすい気がします．
結局何
さっきの文章である条件Lを言及しましたがもう少し具体的に言えば，Lは「複雑な制約が絡んでいるうちで（これはグラフ全体に対応します），P（頂点sに対応）ならばQ（頂点tに対応）である」といえて，またLを満たさないとは「複雑な制約が絡んでいるうちで，PならばQでない」であると言えます．後者の方に注目してみると，「PならばQでない」は，対偶を取ることにより「QならばPでない」と同値です．つまりこのことからP,Qは独立であるようにするということが言えます．よって
「独立な操作P,Qが存在して，各制約について，操作Pを行ったときにコストX，操作Qを行ったときにコストYかかる．どっちかに割り振れ」
という条件に帰着できるわけです．maxflowを使えばこんな形の問題を解くことができます．
チートシート
ACLを前提に考えます．
#include<atcoder/maxflow>
atcoder::mf_graph<ll> g(n+2);
が宣言されているものだと思ってください．nは制約の個数（というとやや語弊があるが）に対応します．また，頂点S,Tを操作P,Qに対応させるとします．
・最終的に求める答え
g.flow(S,T);
・制約Cは「操作Pを割り当てるときにコストがXかかり，操作Qを割り当てるときにコストがYかかる」
g.add_edge(S,C,Y);//S→Cが成り立たないときを考えるので，コストが逆になることに注意
g.add_edge(C,T,X);
・制約Cに操作Qを割り当て，制約Dに操作Pを割り当てたときにコストがZかかる
g.add_edge(D,C,Z);
・制約Cにも制約Dにも操作Pを割り当てたときに報酬がGもらえる（コストだとNP-Hardになる）
この制約自体を新しい制約Eとおく．
//あらかじめGだけもらっておく
ans-=G;
//Eが操作Qに割り当てられている場合はGだけ支払う（元の加算分を考えるとチャラ）
g.add_edge(S,E,G);
//EはPに割り当てられているが，CがQに割り当てられている場合はINFだけ支払う（EがPなら，CとDもPであるようにしたいので，Qにいかないようにする）
g.add_edge(E,C,INF);
//Dも同様
g.add_edge(E,D,INF);
・制約C,D,Eが全てPに割り当てられたときに報酬Gもらえる
この制約自体をFとおくと
ans-=G;
g.add_edge(S,F,G);
g.add_edge(F,C,INF);
g.add_edge(F,D,INF);
g.add_edge(F,E,INF);
以下は非常に参考にした文献です ありがとうございます
蟻本p188-p193
ABC146 F - Sugoroku
解法
最小回数で到達できないといけないので，１回あたりでできるだけ先に進む必要がある．
また，辞書順で最小ということは，最初の方はなるべく小さい歩数でいきたい．
ということを考えると，
最初の方は控えめ→あとの方でなるべく大きく進む
と進むのが最善そうである．
これを考えると，後ろから遡ってなるべく左端から自分の今いるところに到達できるように繰り返していけば良さそう．
よって，現在いる場所をidxとして，以下を実装すれば良い．
1.idx=Nからスタート
2.if(idx<=M)s[0]=='0'が確約されているので，idx分戻れば良くて，これで終了
else M個前から順に見ていって，s[idx-j]=='0'が初めて満たされるjだけ遡れば良い
idx-=jと更新して2を繰り返す．
ABC167-F Bracket Sequencing
ARMERIAさんのブログが非常にわかりやすかった
問題
解法
'(':+1
')':-1
と対応させると，適当に文字列を構成した時に累積和Sが以下を満たすようなパターンは存在するか？という問題に言い換えられる．
1.任意のindexに対してS[index]>=0
2.最終的な全体の累積和S[end]==0
すると，2については全体の文字列パターンが与えられたときに満たすかどうかは明らかなのでどうでもよくて，1が常に満たされるように上手いこと帳尻合わせをする必要がある．
ここで，1の条件を言い換えると，以下のように言える．
その文字列の累積和のmin>=0
また，この問題はパーツをうまい具合に組み合わせるという形式なので，もっと細かく言えば以下が言える．
ある文字列パーツを組み合わせたところまでの文字列に対してさらに新たな文字列パーツを組み合わせる．その新しい文字列パーツの区間に対応する累積和のmin>=0(★）
するとそのある文字列パーツまでの累積和を考えたときに，新しく文字列パーツを組み合わせたときの累積和のminとなるのはどういう部分かというと，その新たに付け加える文字列パーツ自身の累積和のminに対応する部分に対応するはずである．
よって文字列パーツは以下の成分によって特徴づけることができる．
1.その文字列パーツ内の累積和の最小値mn
2.その文字列パーツを最後まで辿ったときの累積和sm
あとはどういう順序で付け加えていくかというところだが，初期の累積和を0とした時に，（★）の部分から，mnはなるべく大きいものから取っていったほうが良さそうである．また，最終的にできる文字列パターンを考えると，前半は'('が多いほうが良さそうである．このことから，前半部分についてはsm>=0なるところからmnが大きいものを順に選んで組み合わせれば良さそうである．
問題は後半部分で，前半でsm>=0なるところから選んでいるので後半の方は必然的にその部分までの貯金を崩していく（＝sm<0の文字列パーツ郡から選んでいく）ことになるのだが，単純にmnが大きいものから順に選んでしまうと，mnが非常に小さいものが来た時に累積和が足りなくて構成できない場合が考えられる．よって，もし使えるなら余裕があるうちにmnが小さいものを使いたい．一方で，単純にmnが小さい順に選ぶとその文字列を組み合わせた後の累積和が小さくなりすぎて構成に失敗してしまうことが考えられる．よってsmはできるだけ大きいものを選びたい．
このことを考えるとsm-mnが大きい順に選んでいけば良さそうである．（正当性はARMERIAさんのブログを参照）
あとはこれを実装すれば良い．
ARC111-D Orientation
色々実験して性質を観察するの大事・・・
問題
解法
とりあえず頂点数が小さい範囲でどのような向き付けができるかを見てみる．
すると任意の２頂点u,vに対して
u→vの向きづけがあるならば，c[u]>=c[v]
が成り立っていることがわかる．
あとは，各頂点からDFSをしてやって，まだ向きが決まっていない辺に対してc[i]>=c[j]なるところに向きをつけてやる．このとき，i→jの向き付が決まるとjから出ている残りの辺の向きも決まることに注意する．（サイクルであるかパスであるか）
ABC169-F Knapsack for All Subsets
問題
解法
問題のタイトル通りナップザック問題を考える．
dp[i][j]:i番目までの要素までを用いた部分集合Sを考えたとき，総和がjになるようなSの部分集合の数
とすると，dp[n][s]が答えとなる．
すると，遷移としては以下が考えられる．
（要素a[i]を使う）：a[i]を使うので，当然部分集合Sにもa[i]が入っている必要があり，そして元の総和にはa[i]が足される．よってdp[i+1][j+a[i]]にはdp[i][j]からの遷移が完全に1:1で含まれる．
dp[i+1][j+a[i]]+=dp[i][j]
（要素a[i]を使わない）：a[i]は結局使わないので，部分集合Sに入っていようが入っていまいがどちらでもいい．よってdp[i+1][j]にはdp[i][j]からa[i]を部分集合に含む場合と含まない場合の２パターンの遷移が考えられる．
dp[i+1][j]+=2*dp[i][j]
あとは，上記の式を順に計算していくことによって答えが求まる．
ABC189
ABCD4完1ペナ42:17・・・Eは解けるべきだしペナの出し方も下手だったしCも正直間に合うだろうな〜って思ったのに躊躇って出さなかったのでさっさと投げるべきだったしで色々下手でした
A
if(s[0]==s[1] and s[1]==s[2])でもいいが，
std::sort(s.begin(),s.end());//文字列をソート s.erase(std::unique(s.begin(),s.end()),s.end());//連続する重複要素を削除を使えば10文字くらいあって面倒なときも一発で判定できて便利
#include<bits/stdc++.h> using namespace std; int main(){ string s;cin>>s; sort(s.begin(),s.end()); s.erase(unique(s.begin(),s.end()),s.end()); cout<<(s.size()==1?"Won":"Lost")<<endl; return 0; }
B
小数だと誤差が出るので整数で扱いましょうはABC-Bだとめっちゃ頻出なイメージ（例．ABC174-Bとか）
まあこの難易度帯に限らず小数は本当に最終手段って凄い人が言ってるので間違いない
#include<bits/stdc++.h> using namespace std; int main(){ int n,x;cin>>n>>x; int cur=0,ans=0; while(n--){ int v,p;cin>>v>>p; ans++; cur+=v*p; if(cur>100*x){cout<<ans<<endl;return 0;} } cout<<-1<<endl; return 0; }
C
制約で色々話題になったやつ（僕も惑わされた一人） 108回までは大丈夫って回数で判断したほうがいいのかもしれない・・・
ヒストグラムを考えてみる．
左端を固定してから区間を右に引き伸ばしたときに
をすればよい．
区間最小値は
min(直前までの最小値,新しく加えた右端の要素)
でO(1)で求まる
計算量はO(N2)だが，計算回数は高々(104)2/2=5*107<108なので間に合う
#include<bits/stdc++.h> using namespace std; using ll=long long; #define rep(i,s,n) for(int i=s;i<(n);i++) int main(){ int n;cin>>n; vector<ll>a(n); rep(i,0,n)cin>>a[i]; ll ans=0; rep(i,0,n){ ll mn=a[i]; rep(j,i,n){ mn=min(mn,a[j]); ans=max(ans,mn*(j-i+1)); } } cout<<ans<<endl; return 0; }
O(N)解法
ヒストグラムを考えるのはさっきと同じ
よくよく考えてみれば，答えはこのヒストグラムの中に作ることのできる長方形の最大の面積とみなすことができる
これは蟻本のp298ページに乗っていて，これをまんまコピペすればAC
ざっくり説明すると，最大長方形をなすとき，左端のindexをl,右端のindexをrとすれば
が成り立っているはずである（そうでなければそれぞれの方向にまだ引き伸ばせるはずなので） よって，a[i]を高さとしたときの左端，右端は一意に決まるはずで，これを管理していけば良さそう.それぞれはstackを用いて管理していけばいい．stackはindexを管理する．
具体的には例えば左端を考えてみると，配列aを左からなめていって，a[i]を考えた時に
stackが空になる or a[stackのtop]<a[i]
となるまでstackから取り出していく． そうすると操作後のstackの状態から以下のようにしてa[i]を高さとしたときの左端l[i]を決めることができる．
stackが空である
→自分より小さい要素が左にはない
→一番左端を取れるのでl[i]=0
stackが空でない
→stackの先頭のindexより左側に区間を引き伸ばすことができない
→l[i]=stack.top()+1
右端も同様に決めることができて，あとは各i(0<=i<n)について
a[i]:高さ r[i]-l[i]:区間の幅
と考えてやればこれらの積のmaxが答えになる
#include<bits/stdc++.h> using namespace std; using ll=long long; #define rep(i,s,n) for(int i=s;i<(n);i++) #define rrep(i,s,n) for(int i=n-1;i>=(s);i--) int main(){ int n;cin>>n; vector<ll>a(n); rep(i,0,n)cin>>a[i]; ll ans=0; stack<ll>sl,sr; vector<ll>l(n),r(n); rep(i,0,n){ while(!sl.empty() and a[sl.top()]>=a[i])sl.pop(); l[i]=sl.empty()?0:(sl.top()+1); sl.emplace(i); } rrep(i,0,n){ while(!sr.empty() and a[sr.top()]>=a[i])sr.pop(); r[i]=sr.empty()?n:(sr.top()); sr.emplace(i); } rep(i,0,n)ans=max(ans,a[i]*(r[i]-l[i])); cout<<ans<<endl; return 0; }
D
公式の解説とちょっと実装方針違うかも（方向性はだいたい同じ）
要するに
s[i]==OR→新しい要素x[i]がTrueならy[i]はどうあがいてもTrue，Falseならy[i]がTrueになればTrue
s[i]==AND→y[i]がTrueならx[i]はTrueでTrueに，Falseならx[i]がどうあがいてもFalse
なので，s[i]まで考えたときのTrueとFalseの個数を管理して（これらをそれぞれT[i],F[i]とおく）（実際にはpairとかを用いて実装すればいいと思う）
T[0]=1,F[0]=1
(s[i]==OR)T[i+1]=2*T[i]+F[i],F[i+1]=F[i]
(s[i]==AND)T[i+1]=T[i],F[i+1]=T[i]+2*F[i]
みたいな漸化式を立てればいい
#include<bits/stdc++.h> using namespace std; using ll=long long; using pll=pair<ll,ll>; #define rep(i,s,n) for(int i=s;i<(n);i++) #define rrep(i,s,n) for(int i=n-1;i>=(s);i--) int n; vector<string>s(70); pll rec(int i){ if(!i)return {1,1}; auto [T,F]=rec(i-1); if(s[i-1]=="OR")return {2*T+F,F}; else return {T,T+2*F}; } int main(){ cin>>n; rep(i,0,n)cin>>s[i]; cout<<rec(n).first<<endl; return 0; }
E
色々問題文がごちゃってて解釈がしんどいが，要するに何回か操作した後の変換式が求まれば良さそう．解説は行列と対応させているが，そうじゃなくても合成関数とかで考えられると思う（というか僕はこれでしか考えられなかった）
というわけで，変換式の係数と定数項を管理できれば良さそうである．つまり変換後の座標を(x',y')としたときに
x'=ax+by+c
y'=dx+ey+f
となるような(a,b,c,d,e,f)を管理する．
あとはこれをopに従って変換式を逐次記録していけばいい．
また，変換式の係数を持つ構造体を以下のように定義しておくと便利
struct S{ ll a,b,c; S& operator-(){ a=-a,b=-b,c=-c; return *this; } S& f(ll p){ a=-a,b=-b,c=2*p-c; return *this; } ll F(ll x,ll y)const{ return a*x+b*y+c; } };
というか我ながら割とキレイに実装できた気がする（コンテスト中に間に合わないと意味ないんだけど）
#include<bits/stdc++.h> using namespace std; using ll=long long; using pll=pair<ll,ll>; #define rep(i,s,n) for(int i=s;i<(n);i++) #define rrep(i,s,n) for(int i=n-1;i>=(s);i--)struct S{ ll a,b,c; S& operator-(){ a=-a,b=-b,c=-c; return *this; } S& f(ll p){ a=-a,b=-b,c=2*p-c; return *this; } ll F(ll x,ll y)const{ return a*x+b*y+c; } };
ll n,m,q; vector<pll>xy(200020),op(200020); vector<pair<S,S>>dp(200020); vector<bool>ok(200020,false);
pair<S,S> rec(int i){ if(ok[i])return dp[i]; ok[i]=true; if(!i){ S x={1,0,0},y={0,1,0}; return dp[i]={x,y}; } auto [t,p]=op[i-1]; auto [x,y]=rec(i-1); if(t==1)return dp[i]={y,-x}; else if(t==2)return dp[i]={-y,x}; else if(t==3)return dp[i]={x.f(p),y}; else return dp[i]={x,y.f(p)}; }
int main(){ cin>>n; rep(i,0,n)cin>>xy[i].first>>xy[i].second; cin>>m; rep(i,0,m){ cin>>op[i].first; if(op[i].first>2)cin>>op[i].second; else op[i].second=0; } cin>>q; while(q--){ ll a,b;cin>>a>>b; auto [fx,fy]=rec(a); auto [x,y]=xy[--b]; cout<<fx.F(x,y)<<' '<<fy.F(x,y)<<'\n'; } return 0; }
F
巡回しちゃう系dpはそれをxとおいて漸化式を立てると嬉しいことがある(EDPC-Jなど）
dp[i]:マスiからゴールに辿り着くまでの期待値
マスiが振り出しに戻るマスだとすると，そのマス自体を振り出しと見なすことができるので，答えをxとすると，dp[i]=xとなる．
そうでない場合は，そのマスからM通りの遷移が考えられるので，その遷移先の期待値の平均をとって+1してやればいい
あとはこれをそのまま実装するのだが，毎回期待値の平均をとっているとO(NM)になって簡単にTLEしてしまうので，累積和を持ってやる
僕はメモ化再帰だとこの表現の仕方がわからなかったのでおとなしくfor文で書くやつをやったが，書けないことはないんだろうか・・・
#include<bits/stdc++.h> using namespace std; using ll=long long; using ld=long double; using pll=pair<ll,ll>; #define rep(i,s,n) for(int i=s;i<(n);i++) #define rrep(i,s,n) for(int i=n-1;i>=(s);i--)ll n,m,k; vector<bool>trap(200020,false);
int main(){ cin>>n>>m>>k; ll seq=0; rep(i,0,k){ int x;cin>>x; trap[x]=true; if(trap[x-1])seq++; else seq=1; if(seq==m){cout<<-1<<endl;return 0;} } ld sp=0,sq=0; vector<ld>p(n+m+10,0),q(n+m+10,0); rrep(i,0,n){ if(trap[i])p[i]=1,q[i]=0; else{ p[i]=sp/m; q[i]=sq/m+1; } sp+=p[i]; sq+=q[i]; sp-=p[i+m]; sq-=q[i+m]; } ld ans=q[0]/(1-p[0]); cout<<setprecision(16)<<ans<<endl; return 0; }
ABC180 F - Unbranched
蛇足をしてめっちゃ遠回りした・・・
問題
解法
まあ雰囲気がDPなのでDP
最大サイズがLぴったりになる個数を考えたいところだが，連結成分が複数あるときにめちゃめちゃ面倒なことになる(例えば連結成分のサイズの集合を考えた時に{L}とか{L,L,L,L,...}とか{L,L-1,L-2,...}とか色んなのが考えられる）
そこで連結成分の最大サイズがL→
（任意の連結成分の大きさがL以下であるようなグラフ）-（L-1以下であるようなそれ）
と置き換えて，
dp[v][e][t]:頂点をv，辺をeまで使ったときの連結成分の最大サイズがL-t以下になるようなパターン数
を考えればよくて，答えは
dp[n][m][0]-dp[n][m][1]
になる
あとは遷移を考えるのだが，
e==0であればL-tが正の値である限り1通りに決まるのでそれ基準で考える
すると大きく分けて，頂点を1つ付加した（これをxとする）時に以下の遷移が考えられる．
1.xが孤立している
2.xがk-path上にいる(2<=k<=L-t)
3.xがk-cycle上にいる(2<=k<=L-t)
1.の場合，これは単純にもともとできていたグラフに頂点が追加されるだけなのでdp[v-1][e][t]を加算してやればいい．
2.の場合，既に使われているv-k頂点と自分を取り除いたn-(v-k)-1頂点から自分に接続されるk-1頂点を選んでやればいい．あとはk-pathがどの順番で接続されるのかを考えると逆順も考慮してk!/2通りあるので
dp[v][e][t]+=dp[v-k][e-(k-1)][t]*C(n-v-1,k-1)*k!/2
としてやればいい．（k-pathを形成する時に使われる辺の本数はk-1本）
3.の場合，基本的には2と同じなのだが，円順列なのでk頂点でサイクルを構成するときの場合の数はきほんてきには(k-1)!/2通りある．（逆順も考慮）
ただ，k==2の場合，逆順がそもそも自分自身と一致するのでこれだけ場合分けして1通りだけとカウントする．
以上を踏まえると
(k==2)dp[v-k][e-k][t]*C(n-(v-k)-1,k-1)
(k>2)dp[v-k][e-k][t]*C(n-(v-k)-1,k-1)*(k-1)!/2
を加算してやればいいことがわかる．
余談
一回v==eならサイクルの1通りに決まると思ったのだが，よくよく考えると後ろの方の頂点とサイクルを形成する可能性があり（例えば頂点{1,2,3}があったときに1-3でサイクルができるパターン），うまく行かない（これを書いてしまってて，時間を大量に消費した）
