土下座しながら探索中

主に競技プログラミング

動的計画法

UVa 12295 : Optimal Symmetric Paths

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

UVa 10328 : Coin Toss

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

UVa 1220 : 3794 - Party at Hali-Bula

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

UVa 607 : Scheduling Lectures

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

UVa 10690 : Expression Again

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 10069 : Distinct Subsequences

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

UVa 12324 : Philip J. Fry Problem

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

UVa 11088 : End up with More Teams

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

UVa 10898 : D: Combo Deal

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

UVa 11611 : Colored Tiles

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

AOJ : 2449

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

AOJ 2285 : Anipero

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

AOJ 2090 : Repeated Subsequences

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

UVa 11240 : Antimonotonicity

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

UVa 526 : String Distance and Transform Process

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

UVa 10616 : Divisible Group Sums

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

AOJ 1291 : Search of Concatenated Strings

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

AOJ 2366 : Elevator

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

AOJ 2510 : Twin book report

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

AOJ 1287 : Stopped Watches

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

AOJ 1086 : Live Schedule

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

AOJ 0537 : Bingo

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

UVa 108 : Maximum Sum

問題リンク: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…

UVa 103 : Stacking Boxes

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

AOJ 2517 : Hotel

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

AOJ 2106 : Enegy Transporter

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

UVa 437 : The Tower of Babylon

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

AOJ 1222 : Telescope

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

AOJ 1269 : Sum of Different Primes

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

AOJ 1277 : Minimal Backgammon

問題リンク:Minimal Backgammon | Aizu Online Judge解法: 動的計画法で確率を計算した double dp[T][N] := ターンTにマスNにいる確率 とした 初期ではdp[0][0] = 1 とする疑似コード for t 0..T for n 0..N for i 1..6 dp[next_T][next_N] += dp[t][n]*(1…