問題文 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>…