問題リンク : http://uva.onlinejudge.org/external/122/12294.html問題概要 : ゲームの主人公の初期の力はpであり、これからn個のステージを全て入力で与えられた順番でクリアしなければならない ( できない場合は"Impossible"と出力 ) 各ステージは p1, p2…

問題リンク : http://uva.onlinejudge.org/external/122/12295.html問題概要 : n * n のセルがあり、セルの中には1以上9以下の数字がかかれている 左上を(0,0), 右下を(n-1,n-1)としたとき、左上から右下へ移動する経路のうち、通ったセルの数字の和が最小と…

UVa演習 2014/7/14 (月) 問３問題リンク : http://uva.onlinejudge.org/external/103/10328.html問題概要： n回コインをなげたとき、2^nだけコインの状態がある そのうち連続でk回以上表がでているようなものはいくつあるか？解法: 動的計画法 dp[何桁までみ…

UVa演習 2014/6/17 (木) 問1問題リンク : http://uva.onlinejudge.org/external/12/1220.html問題概要： とある会社の社員達がパーリィを開くことにした Big Bossと呼ばれる社員以外はちょうど１人のボスをもつ(つまり、ツリー状のグラフになる) パーリィに…

UVa演習 2014/6/17 (火) 問１問題リンク : Scheduling Lectures問題概要： n個のジョブがあり、それぞれ処理にt[i]秒だけ時間がかかる ジョブは0から順番に番号付けられていて、0から順に処理されていかなければならない １つのプロセッサーで処理できるジョ…

UVa演習 : 2014/6/10 (火) 問8問題リンク : http://uva.onlinejudge.org/external/106/10690.html問題概要： N+M個の整数(-50以上50以下)が与えられる (x1+x2+...+xN)*(y1+y2+...+yM)の最大値と最小値を求めよ解法： 動的計画法 dp[i個の整数をつかった][そ…

UVa演習 : 2014/6/10 (火) 問７問題リンク : http://uva.onlinejudge.org/external/100/10069.html問題概要： ２つの文字列X,Zがあたえられる X中に部分列としていくつZが存在するか？数えよ解法: 動的計画法 dp[Z[0:i]][X[0:j]] := 総和 ただし答えは10^100…

UVa演習 2014/6/10 (火) 問６問題リンク : http://uva.onlinejudge.org/external/123/12324.html問題概要： スペースシップで旅をする 旅はn個のフェーズに分かれている 各フェーズはt[i]秒で終わる 各フェーズでb[i]個のスペースシップ加速素材を手に入れる…

UVa演習 2014/6/10 (火) 問３問題リンク:http://uva.onlinejudge.org/external/110/11088.html問題概要： n人の人がいて、それぞれが３０以下のパワーをもっている その中から3人チームを何組か作りたい チーム全体のパワーは２０以上でなければならない 最…

UVa演習 2014/6/10 (火) 問２問題リンク:http://uva.onlinejudge.org/external/108/10898.html問題概要： I種類の食べ物があり、それぞれの値段が与えられる C種類のセットがあり、その値段も同様に与えられる クエリーとして、I種類の食べ物をそれぞれ何個…

問題リンク:http://uva.onlinejudge.org/external/116/11611.html問題概要： H*Wのマスに図にあるようなピースを置いていく マスは3種類あり、 空のマスにはピースを置ける 壊れているマスにはピースを置けない 色の指定があるマスにはその色のピースしかお…

問題リンク:Connect | Aizu Online Judge問題概要: 略解法: １行覚えるタイプの動的計画法 dp[r][c][bit] := (c,r)までで使用する文字列の状態がbitの時の最大値 としてDPする bitの数を数えてその行の文字列よりも多く使用する場合などはcontinueする ２重…

問題リンク:Anipero | Aizu Online Judge問題概要: 略解法： 動的計画法 pre[使用した金額][選んだシークレットアーティストの数(0,1,2人のみ)] := この時得られる最大の満足度 pre2[使用した金額][選んだスタンダードアーティストの数] := この時得られる最…

問題リンク：Repeated Subsequences | Aizu Online Judge問題概要： 長さが300以下の文字列があたえられる この文字列を空でない２つの文字列に分ける こうしてできる２つの文字列のLCSの中で最も長いものを出力せよ 複数ある場合はどれを出力しても良い解法…

問題リンク : http://uva.onlinejudge.org/external/112/11240.html問題概要: n個の要素からなる配列が与えられる この部分列のなかで以下の条件を満たすもののうち最長のものの長さを求めよ A > B D 解法 : 貪欲に決めていく（考え方的にはDP？） n個の配列…

問題リンク；String Distance and Transform Process問題概要： ２つの文字列が与えられる 最初の文字列に以下の３つの動作だけを使用して目的の文字列に変更するためにかかる 動作の最小の使用回数とその動作を出力せよ １：文字列の任意の場所にアルファベ…

問題リンク：http://uva.onlinejudge.org/external/106/10616.html問題概要： n個の要素からなる配列A[i](0 配列A[i]からM個の要素を選んだ時、その和がDで割りきれるような選び方は何通り存在するかクエリーは以下の形式からなる D M D,Mは上の説明に登場す…

問題リンク：Search of Concatenated Strings | Aizu Online Judge問題概要： n個(1 n個の文字列を任意の順で全てつなげた文字列がtのなかにどのくらい存在するか？ ただし、n個の文字列をつなげた際に同じものが複数できた場合はそれらを１つとみなす解法：…

問題概要：Elevator | Aizu Online Judge問題概要： 日本語なので略解法： 動的計画法を行う 荷物があるフロアの中で最も上にあるフロアから１フロアずつ全ての荷物をもっていきながらおりていく そのフロアにある荷物を全て１つ下のフロアに持っていくため…

問題リンク：Twin book report | Aizu Online Judge問題概要： 日本語なので略・自分が読み落としていた文 > 加えて，本の返却期限が近いため，まずはなるべく早くすべての本を読み終えるようにしてもらう事にした つまり、読める本があるなら感想文よりもそ…

問題リンク：Stopped Watches | Aizu Online Judge問題概要： n個の時計の情報が与えられる ただ、どれが秒針でどれが分針、時針なのかはわからないし どこを基準に数えているのかも分からない 全ての時計がとりうる時間の間隔のうちもっとも短いものを出力…

問題リンク：Live Schedule | Aizu Online Judge解法： 動的計画法dp[何日目か][負担][連続してライブをした日数] := 最大利益 とする遷移の状態としては、 ・何もしない ・その場所だけでライブ ・連続してライブ の３つがあるEが0の時はそこでライブを行え…

問題リンク：Bingo | Aizu Online Judge解法： 動的計画法を行う 問題の制約より、N*Nのマスを全て異なる数で総和がSになるような状態の数を求めれば良い亊がわかるコード： #define REP(i,s,n) for(int i=s;i

問題リンク：Maximum Sum問題概要： N*Nの2次元配列が与えられる この中から作れる長方形のうちその要素の和が最大のものをみつけよ解法： よくあるDP memo[y][x] := memo[y-1][x] + memo[y][x-1] - memo[y+1][x+1] + array[y][x]という配列を用意する array…

問題リンク：Stacking Boxes問題概要： n個のk次元の箱がある 以下の条件を満たす時、箱aを箱bに入れることができる ・箱aの各辺の長さが箱bの対応する辺の長さ未満であるような順列が存在する （例: 5次元とする 箱 a : 5 1 3 7 6 箱 b : 4 2 7 8 6分かりに…

問題リンク : Hotel | Aizu Online Judge解法： 動的計画法を行う D日間にかかるホテルの費用の最小は各日にちでもっとも安いホテルを選んだときの費用の和だが、 移動回数の最小化や複数あったときに辞書順で最小のものを選びたいのでDPする配列は dp[何日…

問題リンク : Enegy Transporter | Aizu Online Judge問題概要： n個のノードが一直線上につながれている ノードはそれぞれ値を持つ 両端のノードと値が０のノード以外のノードは自分の値をマイナス１することで 右のノードの値に左のノードの値を加えること…

問題リンク：The Tower of Babylon問題概要： x*y*zの長方形がn個（nは30以下）与えられる 以下の条件を満たすとき長方形を別の長方形に載せることができる 条件：長方形の上にのせる長方形の横と縦の長さは下の長方形の横と縦の長さ未満でないといけないこ…

問題リンク : Telescope | Aizu Online Judge問題概要： n個の点が円上に存在する その内m個を選んだ時にできる多角形の面積の最大値を求めよ解法： 動的計画法で解いた dp[始点となる点][最後に使った点][点を選んだ回数]:=その時の最大面積 とした for sp …

問題リンク : Sum of Different Primes | Aizu Online Judge解法： 動的計画法を用いてあらかじめ結果をdp配列に入れておく dp[n][k] := nをk個の異なる素数でつくる時の数 dp[0][0] = 1 (０を０個の異なる素数で作る方法は一通りしかない)疑似コード: for i…