練習会でフロー関連の発表をした。内容は↓のとおり。 今までフローを避けてきたので、まとまった勉強をする良い機会となった。しかし、一般マッチングや最大マッチングと最小点カバーにおける関係などはまだ理解できてないので、もう少し蟻本を睨む必要があ…

二分探索するだけ。 #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<(int)(n);i++) #define ll long long class ProblemSets { public: bool judge(ll E,ll EM,ll M,ll MH,ll H,ll num){ ll x=max(0ll,num-E); ll y=max(0ll,num-H); if(x>E</bits/stdc++.h>…

制約からして二分探索なんだろうとは思ったが本番では解けなかった。 a,bを最初にソートしておき、付値関数C(x)として次のものを考える。C(x): a[i]*b[j]a[i]*b[pos]x のとき、a[i]x なるpos'について pos>pos' が成り立つ。従ってC(x)はO(N)で計算できる。 …

蟻本等の内容を復習していく。 Bellman-Ford法 頂点sから頂点iまでの仮の最短距離をd[i]とする 0: d[s]=0, d[i(≠s)]=INF とする 1: u,v∈V に対してd[v]=min(d[v],d[u]+w(u,v))で更新。更新できなくなったら終了 step1がV回実行されても終了しない場合、負の…

dp(i,j):i番目の操作でj番目のパンケーキを置く確率 class RandomPancakeStack { public: int N; double memo[300][300]; double dp(int i,int j){ if(memo[i][j]>1e-9) return memo[i][j]; if(i==0) return memo[i][j]=1.0/N; double res=0; for(int k=j+1;k

n日までに得る弁当の総数の期待値を計算すればいいわけだが、漸化式がうまく作れない && 他の人のコードを読んでも自明のようにdpしていてよく分からない、というツラさがあったので、この問題の漸化式が私のように漸化式が思いつかなかった人のために愚直に…

量子力学の教科書を読んでいて、球Bessel関数とかLaguerreの陪多項式がある微分方程式の解だと言われてもいまいちピンと来なかったので適当に実装してmatplotlibでグラフを書いてみようと思っていたところ、scipyに特殊関数のmoduleがあることを知った。Spec…

Ford-Fulkerson法を最近勉強したのでやっと解けるようになった。二部グラフの最大マッチングのサイズを求めるという典型題中の典型題。 #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<(int)(n);i++) //Ford-Fulkerson's algorithm struct </bits/stdc++.h>…

をmod 1e9+7 での逆元を使いながら計算すれば良い。最初 #define MOD 1000000007 としていたが、これだとMODはint型と判断されオーバーフローを起こしてしまってつらかった。 #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<(int)(n);i++) </bits/stdc++.h>…

以下のBNFに従ってparserを書く。 ・<Cipher>:=(<String>)+ ・<String>:='[' + <Cipher> + ']' | <Letter> ・<Letter>:=('+'|'-')* + <Alphabet>但し、'?'を含むの要素は'A'と同一視する。 #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<(int)(n);i++) string expr_string(); char expr_letter(); int</bits/stdc++.h></alphabet></letter></letter></cipher></string></string></cipher>…

i番目の町にいて残り時間がjである状態を(i,j)としてこれらの状態間を移動にかかる時間ないしは経過時間をコストとする辺でつなぎ、グラフを作る。あとはDijkstra #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<(int)(n);i++) #define INF</bits/stdc++.h>…

左端から順に塗りつぶして考えていくと、テストケースにうまくいかないものがあり、そこから手が出なかった。 最終状態からk*kの正方形領域内に'B'と'W'の一方のみが存在するものがあれば、その領域を'?'で塗りつぶす。以下これを繰り返して最終的にn*n全体…

string:size_typeとかstring:nposとかよく知らなかったので調べながら書いた。BFSで調べていくが、文字列の長さで枝刈りするだけではTLEしたので、setで既に生成された文字列をメモした。 #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<(i</bits/stdc++.h>…

区間[a,b]と[c,d]の共通部分の長さはmax(0,min(b,d)-max(a,c))であることに注意して全探索する。最初、配列を小さく取り過ぎてREした。 #include <bits/stdc++.h> using namespace std; #define REP(i,n) for(int i=0;i<(int)(n);i++) typedef pair<int,int> P; int blessedTime(int </int,int></bits/stdc++.h>…