問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1269 動的計画法。 dp[使った素数の数][使った素数の最大のid][作りたい数]:=場合の数 #include<iostream> #include<vector> #include<algorithm> #define all(c) (c).begin(),(c).end() using namespace std; vector<int>w; </int></algorithm></vector></iostream>…

文字列がいくつか与えられるので全ての文字列に現れる部分文字列の中で最長のものの長さを求めよ。 suffix arrayを使えば良い。共通部分文字列は蟻本に詳しく書いてる。嘘解法だった。隣同士の最長共通部分文字列しか計算してないのに通っていた。 #define I…

問題文 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[ 最後に使った文字 ][ 今まで使った文字の集合 ]:=長さ…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1257連続する素数の和でnを作る場合の数を求めよ。 素数の数が1000くらいしかなかったので尺取り法した。 #include<iostream> #include<vector> #include<algorithm> using namespace std; int main(void){ bool prim[10</algorithm></vector></iostream>…

典型DPコンテストB問題。 http://tdpc.contest.atcoder.jp/tasks/tdpc_game 自分は自分の得点を最大化する。 相手は相手の得点を最大化する→相手は自分の得点を最小化する と言い換えることができる。 #include<iostream> #include<vector> #include<algorithm> #define INF (1<<29) using</algorithm></vector></iostream>…

問題文 https://icpcarchive.ecs.baylor.edu/external/42/4201.pdfバルブを光らせるパターンが与えられるので、クエリで与えられるとおりにバルブを光らせるまでの最短手数を求めよ。 ビットDP。 dp[パターンのid][バルブの状態]:=最短手数 とすると、DAGの…

問題文 http://poj.org/problem?id=1159与えられた文字列を、文字を挿入する操作のみを行って回文にする。挿入する文字の最小個数を求めよ。 ↓と同じ。メモ化再帰。int型を使うとMLEする。 http://d.hatena.ne.jp/TobiasGSmollett/20130702/1372785990 #incl…

問題文 http://poj.org/problem?id=1157訳 http://wikiwiki.jp/pku/?1157%20LITTLE%20SHOP%20OF%20FLOWERS メモ化再帰した。 #include<iostream> #include<algorithm> #define INF (1<<29) using namespace std; int h,w,v[102][102],memo[102][102]; int rec(int a,int b){ if(a=</algorithm></iostream>…

問題文 http://livearchive.onlinejudge.org/external/40/4058.pdf縦3横nの長方形が、与えられた回転できないブロックで作る方法がいくつあるか求めよ。 f[ n ]:=横nの長方形の場合の数 とする。 g1[n],g2[n],g3[n],g4[n]についてはそれぞれ以下のような図形…

問題文 http://poj.org/problem?id=3254グリッドが与えられる。マスの数が1であるようなもののうちで、それぞれ4近傍に隣接しないような選び方がいくつあるか求めよ。 1行を覚えておくDP。 dp[ マスの番号 ][ 直前の1行の状態 ] := 場合の数 #include<iostream> #inclu</iostream>…

問題文 https://icpcarchive.ecs.baylor.edu/external/36/3673.pdfn×nの黒と白のグリッドが与えられる。任意の行と行、列と列をスワップすることができる。この操作を繰り返すことで、縦と横の番号が同じようなマスを全て白にできるか判定せよ。 斜めに並べ…

問題文 https://icpcarchive.ecs.baylor.edu/external/61/6133.pdf補完機能を使って文字を打つとき、ひとつの文字を打つのに必要な最小の打たなければいけない文字数の平均を求めよ。 トライ木を使った。そのノードの子が2つ以上なら、そこまでで補完機能一…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2151 拡張ダイクストラした。 d[ ノード番号 ][ ノードについた時の残金 ] := 襲われた人数優先順位付きキューは、 P3( 襲われた人数 , P( 残金 , ノード番号 ) ) としている。 #include <iostream> </iostream>…

問題文 http://poj.org/problem?id=2441n頭の牛がいて、m棟の小屋がある。牛にはそれぞれ入れる小屋が決まっていて、全部の牛を小屋に入れるような入れ方が何通りあるかを求めよ。 ビットDPした。 dp[ 牛の番号 ][ どの小屋を使ったか ] := 場合の数配列がと…

問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0099 優先順位付きキューを上手に使う問題。 #include<iostream> #include<vector> #include<queue> #include<algorithm> using namespace std; typedef pair<int,int> P; int main(void){ int n,q,cnt[1000001]; priority_queue<P>que; que</p></int,int></algorithm></queue></vector></iostream>…

問題文 https://icpcarchive.ecs.baylor.edu/external/42/4210.pdfグラフが与えられる。最短経路に含まれる辺をひとつも使わない経路の中で最短のものを求めよ。ただし最短経路は複数ある場合もある。 ダイクストラを2回やる。一回目で最短経路に含まれる辺…

問題文 https://icpcarchive.ecs.baylor.edu/external/42/4212.pdfn*mのグリッドが与えられる。マスの数字はそのマスにあるキャンディーの個数だ。このグリッドのあるマスからそのマスにあるキャンディーを全てとるとき、図のようにそのマスの左右のマスと上…