問題文 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のグリッドが与えられる。マスの数字はそのマスにあるキャンディーの個数だ。このグリッドのあるマスからそのマスにあるキャンディーを全てとるとき、図のようにそのマスの左右のマスと上…
問題文 https://icpcarchive.ecs.baylor.edu/external/56/5689.pdf色のついた円が与えられる。各データセットには色が400.0の円と789.0の円がひとつずつ含まれる。この円の上を通って、400.0の円から789.0の円に行って戻ってくることができるかどうか判定せ…
問題文 http://uva.onlinejudge.org/external/109/10991.html3つの円の半径が与えられる。図のように3つの円に囲まれた部分の面積を求めよ。 3つの円の中心を頂点とする三角形の面積から、その三角形の内部の扇型の面積を引いてやればよい。三角形の面積はヘ…
問題文 http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1140&lang=jp 幅優先探索でスタート位置と汚れについて全点対間最短距離を求めておいて、パスを全部試す。 #include<iostream> #include<vector> #include<algorithm> #include<string> #include<queue> #define INF 100000000 #define </queue></string></algorithm></vector></iostream>…
問題文 http://poj.org/problem?id=3468 蟻本でも紹介されている問題。 セグメント木を実装した。各節点は次の2つのデータをもつ。 whole[ ] その節点の区間全体に一様に加えられた値 part[ ] その節点の区間に一様でなく加えられた値 #include<iostream> #include<vector> #in</vector></iostream>…
問題文 http://poj.org/problem?id=3692 最大クリーク問題。 二部グラフになっているので補グラフの最大独立集合を求める。 最大クリーク=補グラフの最大独立集合 が成り立つ。また二部グラフなら、 最大独立集合=頂点数-最大マッチング が成り立つ。 #inclu…
