問題文(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1320)AOJ2022(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2022)とほとんど同じ問題。他の都市名の部分文字列になっている都市名を予め取り除いてからbitDPをする。 #inclu…

問題文(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2534)まず、与えられた文字列の組(string_i, string_j)(i このグラフの構築段階で(i,j)に辺があるのに(j,i)にも辺が張られているば矛盾しているのでfalseを返す。また、'@'は最小であるは…

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

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>…

以下の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>…

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>…