問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0190 双方向bfsで解いた。 #include<iostream> #include<vector> #include<algorithm> #include<map> #include<queue> using namespace std; map<vector<int>,int>mp,used; struct State{ vector<int>v; int t; State(vector<int>v,int t):v(v),t(t){} }; v</int></int></vector<int></queue></map></algorithm></vector></iostream>…

3-SATを解く、Schoeningのアルゴリズムという乱択アルゴリズムを実装した。 変数はアルファベット１文字のみ。否定は~。 未検証。(a|~b|~c)&(b|c|~d) のように入力を与える。文字同士の間に空白は入れない。 #include<iostream> #include<vector> #include<algorithm> #include<string> #include<cctype> #</cctype></string></algorithm></vector></iostream>…

問題文 https://icpcarchive.ecs.baylor.edu/external/58/5874.pdf 二部グラフのマッチング。嘘解法だった。本当は一般グラフのマッチングで解くらしい。 #include<iostream> #include<vector> #include<algorithm> #include<set> #define INF 1LL<<62 #define MAX_V 1000 using namespace std;</set></algorithm></vector></iostream>…

問題文 https://icpcarchive.ecs.baylor.edu/external/58/5872.pdf二つの四則演算のみの式a,bが与えられる。a=bであるかどうか判定せよ。 変数の値を乱数で適当に決めて、1000回判定をした。 #include<iostream> #include<vector> #include<algorithm> #include<string> #include<cctype> #include<map> using n</map></cctype></string></algorithm></vector></iostream>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1215文字列といくつかの文字が与えられる。 文字をすべて含む、文字列の部分列の中で最小の長さのものの個数と、そのような部分列のなかで最初に現れるものを出力せよ。 尺取り法のような…

問題文 http://uva.onlinejudge.org/external/102/10299.html1以上でnより小さい、nと互いに素な数の個数を求めよ。 包除原理。 互いに素であるという事は共通素因数を持たないということ。 1からn-1のなかでこのような数の個数を求めればよい。 例えばn=30…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1283多角形の中のある点から多角形の外への最も短い距離が最も長いような点をとったときの、多角形の外への最短距離を求めよ。 二分探索+多角形切断。 値dを二分探索で決め打ちする。 多角…

問題文 https://icpcarchive.ecs.baylor.edu/external/41/4130.pdf人の名前と要らないものと欲しいもののリストが与えられる。 物々交換により欲しいものを手に入れたい。 自分が持っているいらないものが相手の欲しいものであり、かつ 自分の欲しいものが相…

問題文 http://uva.onlinejudge.org/external/110/11069.html1~nまでの頂点が一直線につながっている。このグラフから、どの頂点も隣り合っていない物の中で、これ以上頂点を追加できないものの数を数えよ。 dp[頂点]:=場合の数 とすると、頂点が2つ前のもの…

問題文 https://icpcarchive.ecs.baylor.edu/external/57/5790.pdf図のようにコストがついた玉がいくつか与えられる。ある玉を取り除くとそのコスト分だけ得点がもらえる。その玉の上に玉が無ければ取り除くことができる。得点を最大化せよ。 与えられる玉を…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1318無向グラフが与えられるので、車にのってsからtに行くときの最短経路を求めよ。ただし車には燃料の容量がある。車は燃料1で距離10進むことができる。次の町に着いたときに燃料がちょう…

問題文 http://poj.org/problem?id=2217蟻本で解説されてる問題。蟻本と週刊spaghetti sourceさんを参考にしてローリングハッシュで実装してみた。TLEになった。答えも正しく出てるのかはわからない。 #include<iostream> #include<algorithm> #include<string> #include<vector> #include<cstdio> #define</cstdio></vector></string></algorithm></iostream>…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1325二つの整数(m,n)の組をGinkgo numberと呼ぶ。 · = をGinkgo numberの掛け算とする。 また、 · = であるとき、はの約数である。さらに、あるGinkgo numberが, , , , , , , 以外に約数を…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=132014個以下の文字列が与えられる。これらの文字列を全てつなぎ合わせたときの文字列の長さの最小値を求めよ。 ビットDPした。 dp[ 最後に使った文字 ][ 今まで使った文字の集合 ]:=長さ…