Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

動的計画法

Codeforces 235B - Let's Play Osu!

問題文 : Let's Play Osu!概要$n$ 個のマスがある. マス $i$ は確率 $p_i$ で "○" になり, 確率 $1 - p_i$ で"×"になる. $n$ 個のマスのうち, "○"で繋がったそれぞれの連結成分の大きさを$S_i$ とすると, スコア $\displaystyle\sum_{i = 1}^{連結成分数}S_i…

AOJ 0597 - Xiao Long Bao

問題文 : 小籠包

Typical DP Contest L - 猫

問題文 : 猫

ARC 004D - 表現の自由

問題文 : 表現の自由

AOJ 2510 - Twin Book Report

問題文 : 双子の読書感想文

AOJ 1302 - Twenty Questions

問題文 : Twenty Questions概要 :長さ$m $ のビット列が$n$ 個ある. これらを一意に識別するために必要なビット数はいくらか? ただし, あるビットの情報を得た後に次の戦略を考えても良い.$1 \leqq m \leqq 11,\ 1 \leqq n \leqq 128$

AOJ 0275 - Railroad

問題文 : 鉄道路線

Codeforces 314C - Sereja and Subsequences

問題文 : Sereja and Subsequences概要 :数列${a_n}$ がある. ${a_n}$ の相異なる全ての非減少部分列${b_n}$ について, $b_1b_2\cdots b_n$ を求め, その和をmod $10^9+7$ で求めよ.$n \leqq 10^5$

AOJ 1056 - Ben Toh

問題 : Ben Toh

kyuridenamida さんの問題

問題 : -平-均-ものすごくJOI 本選に出そうな問題だった.部分点1 が$n \leqq 20$ 部分点2 が$n \leqq 50,\ a_i \leqq 100,\ T \leqq 100$ 満点が問題文の通り, みたいな感じ.

APIO 2010 - commando

問題文 : 奇襲部隊

Typical DP Contest J - ボール

問題文 : ボール

Typical DP Contest I - イウィ

問題文 : イウィ

Typical DP Contest H - ナップザック

問題文 : ナップザック

Typical DP Contest G - 辞書順

問題文 : 辞書順

Typical DP Contest F - 準急

問題文 : 準急

Typical DP Contest E - 数

問題文 : 数

Typical DP Contest D - サイコロ

問題文 : サイコロ

Typical DP Contest C - トーナメント

問題文 : トーナメント

Typical DP Contest B - ゲーム

問題文 : ゲーム

Typical DP Contest A - コンテスト

問題文 : コンテスト

IOI 2008 Day2 - Linear Garden

問題文 : 直線状の庭園 (pdf 注意)

AOJ 1176 - Planning Rolling Blackouts

問題文 : 輪番停電計画解法 :$dp[sy][sx][gy][gx] := sy \leqq y \leqq gy,\ sx \leqq x \leqq gx$ を満たす区間でのグループの数の最大値と, 供給力の最大値として, メモ化再帰を行うと楽. 列 or 行を降りていき, 分割が不可能な域に達したらimpossible を…

AOJ 2457 - Adhoc Translation

問題文 : Adhoc Translation解法 : これがA 問題ってやべえなあ... 辞書に登録されている単語とネットで見た単語の間に, それぞれ編集距離をコストとした辺を張る. ネットで見た単語の数 ≦ 辞書に登録されている単語の数で, かならずネットで見た単語の数の…

JOI Open 2013 - Watching

問題文 : ウォッチング解法 (ただし人と違う解き方をしているらしい) : 50 点分の解法は, dp[i][j][k] : 位置i までを小カメラj 個, 大カメラk 個で覆うときの距離の最小値, として, O(N^4) で計算できる. (二分探索とは概念)これを高速化するために, dp[i][…

JOI 春合宿 2008-day4 Ruins

問題文 : 最古の遺跡2解法 :dp[i][j] : 辺ij を最後に使った時の頂点数の最大値, とする. このとき, 以下のような図を考える.ここで, 現在赤の辺から水色の辺に遷移しようと考えていたとすると, 赤の辺と水色の辺のなす角θが180 度以下であれば, dp[水色の辺…

Codeforces 258D - Little Elephants and Broken Sorting

問題文 : Little Elephants and Broken Sorting解法 :dp[i][j] : 場所i, j の数をA[i], A[j] として, A[i] > A[j] となる確率, とすると,この配列の初期値はA[i] > A[j] なら 1, A[i] k 回目において,1 / 2 の確率でa[k] 番めの数とb[k] 番目の数が交換され…

JOI春合宿 2011-day4 orienteering

問題文 : オリエンテーリング解法 : 同じ高さの点が無いので, 前もって標高順で, チェックポイントについてトポロジカルソートを行う. その後は全点対の最短経路をO(N^2logN)程度で求め, dp[i][j] : 1人目がチェックポイントi, 2人目がチェックポイントj に…

JAG 2012 模擬地区予選E - Stack Maze

問題文 : Stack Maze解法 :dp[y1][x1][y2][x2] : 区間D : x ∈ [x1, x2], y ∈ [y1, y2] で宝石を置ける個数の最大値とすると, マス(y1, x1) から(y2, x2)に到達可能であれば, D' : x ∈ (x1, x2], y ∈ [y1, y2] などの, Dより小さい区間の最大値からこの値を計…

JOI春合宿 2009-day4 Chopsticks

問題文 : 塗り箸解法 : dp[i][j] : 区間[i, j]を塗るためのコストの最小値, とするとdp[i][i] = 1, dp[i][j] = for(k = i...j - 1) min(dp[i][k] + dp[k + 1][j]) - (t[i] == t[j])となる. これは, 区間の幅を小さいものから計算すれば実現できる.コード : #…

JOI春合宿 2010-day4 lake

問題文 : 湖解法 :まず,dp[l][r] = 区間[l, r]での運行数の最大値, とすると dp[l][r] = max(dp[l][r], dp[l][s[i] - 1] + dp[s[i] + 1][t[i] - 1] + dp[t[i] + 1][r]);となる. ただし, s[i], t[i]はそれぞれ船の来航する地点の座標で, s[i] これは, t[i]に…

準急さんの問題

問題:k<=100, N<=10^18, M<=1,000,000,007のとき、1^k+2^k+…+N^k mod M を1秒で求めるプログラムを作成せよ— 編集の都合上省略さん (@semiexp) 12月 19, 2011昔semiexpさんがこんな問題をつぶやいていたので、解いてみました. 結論から言うと, 僕の環境だ…

JOI春合宿 2011-day3 deciphering

問題文 : 解読解法 : dp[i][j], i番目の文字まで, jで終わる暗号の総数, とするとdp[i][i番目の文字] = Σ[j = 'A'...'Z' + ' ', j + i番目の文字は禁止されていない] dp[i - 1][j]となります. 答えは Σ[i = 'A'...'Z'] dp[L][i] です. dp[0][' '] = 1として…

PKU 3735 : Trailing little cats

問題文 : Trailing little cats解法 : a_{ij} = i回目のセットでj番目のネコが持っているピーナッツの数, とすると, a_{ij}は以下の2つのいずれかとなる :・a_{i-1σ(j)} + a_{i-1j} ・a_{i-1j}ここで, f(i)を ベクトルa_{i-1}からベクトルa_iを作る操作とす…

PKU 3616 - Milking Time

問題文 : Milking Time解法 : dp[N] : 時間Nまでに得られるミルクの最大量, とすると,dp[N] = max(i = 1 ... M, e[i] ≦ N | dp[s[i]] + v[i] where s[i] = i番目の仕事が始まる時間, e[i] = i番目の仕事が終わる時間)となる. ここで, 区間の端以外の時間はい…

PKU 3378 - Crazy Thairs

問題文 : Crazy Thairs解法 : dp[i][j] = j番目を終点とする長さi + 1のLISの総数, とするとすべてのjについてdp[0][j] = 1,dp[i + 1][j] = Σ[k = 1...j - 1 | a[k] となります. Σの部分の計算をBITを使うと, O(nlogn)時間でこの問題を解くことができます.あ…

JOI春合宿 2010-day2 DNA synthesizer

問題文 : DNAの合成解法 : dp[M] = M番目の文字までを構成するのに必要なDNA素数の最小値, とすると, M + 1 ~ M + kまでの部分文字列s_kがあるとするとdp[M + i] (1 ≦ i ≦ k) = min(dp[M + i], dp[M] + 1) となる. DNA素を全て確かめるとO(strlen(合成したい…

Matrix-chain multiplication problem

問題文 : n個の行列の連鎖 が与えられたとき、スカラー乗算の回数が最小になるように積A1A2A3...Anを完全に括弧付ける問題を連鎖行列積問題(matrix-chain multiplication problem)という。n個の行列について、行列Aiの次元が与えられたとき、積A1A2...Anの計…

AOJ 2333 - My friends are small

問題文 : ぼくの友達は小さい解法 : 友達を重さでソートし, "使わない友達"を決めると, いくつまでの重量の組み合わせをいれるかを決めることが出来る. この組み合わせを求める部分は, 典型的なナップサック問題を解くDPで求めることが出来る. よって、O(NW)…

Codeforces #79 Div.1 B - Buses

問題文 : Buses解法 : 各バスの出発する地点をs[i], 到着する地点をt[i]とすると バスをt[i]について昇順にソートし、その順に番号をつけます.i番目のバスで乗れる地点は, s[i] ≦ x このjたちは明らかに連続しているので、これらの範囲を満たすjたちを二分探…

Codeforces 75D - Big Maximum Sum

問題文 : Big Maximum Sum解法 : 各配列について ・配列を横断した時の総和 ・配列の左から項をとっていったときの最大値 ・配列の右から項をとっていったときの最大値 ・配列中の要素の最大値を求めると、求めるべき答えは部分列の連続する項を求める問題(A…

AOJ 2312 - Magical Girl Sayaka-chan

問題文 : 魔法少女さやかちゃん解法 : 問題文で示されている円環が直線だと考えると, ある音符とある音符の間は、昇順になっていることが望ましい. そこで、始点を音程のうちもっとも小さいもの, 終点を音程のうちもっとも大きいものとし, 始点->終点 にいく…

JOI春合宿 2012-day4 Bookshelf

問題文 : 本棚解法 : にかいどうさんの言うとおり, 昨日解いた「House Moving」と同じ問題でした.(重さがそれぞれ違いますが, あまり関係ない) ということで, 解説は昨日のもの参照です. BITでも解けるみたいなので, あとでBITで実装してみます.コード : #in…

AOJ 2431 - House Moving

問題文 : 引越し解法 : 荷物を動かすために使う体力を最小化する、ということは 動かさない荷物の重量を最大化する、ということと等しい. ゆえに, 増加する部分列のうち, 重さが最大のものを総重量から引いたものが答えとなる.荷物の重さをkとし, dp[k] -> …

PKU 3171 - Cleaning Shifts

問題文 : Cleaning Shifts解法 : dp[Ei] -> Ei秒まで掃除するのに必要な時間, とし, 牛iが時間Si秒からEi秒まで掃除でき, 雇うのに給料がMiかかるとすると dp[Ei] = min(dp[Ei], min(dp[Si] ~ dp[Ei]) + Mi) となる. dpテーブルはINFなどで初期化しておく. …

AOJ 0145 - Cards

問題文 : カード解法 :dp(l, r) -> 区間(l, r)のカードを併合するために必要な最小コストとすると, l番目のカードが最も上に, r番目のカードが最も下になるのは明らかなのでdp(l, r) = min(dp(l, r), dp(l, i) + dp(i+1, r) + a[l] * b[i] * a[i+1] * b[r]) …

AOJ 0234 - Aizu Buried Treasure

問題文 : 会津の埋蔵金解法 : f(ny, nx, l, r, oxygen) -> 現在場所(nx, ny)にいて, 深さny[m]のうちl ~ rまでの距離は移動済みで, oxygenだけ酸素をもっている, という状態をもった動的計画法を行う. 状態空間が5*10^4になるため, 楽にメモ化再帰ができる. …

AOJ 0232 - Life Game

問題文 : 人生ゲーム解法 : dp(i, j) -> 場所iにいてj円を持っている確率, とし動的計画法を行う. int型にキャストして表示することに注意.コード : #include <cstdio> #include <cstring> #include <algorithm> typedef struct { int dx; int money; } State; using namespace std; int </algorithm></cstring></cstdio>…

AOJ 0215 - Pachimon Creature

問題文 : パチモンクリーチャー解法 : 最初に選ぶパチクリを決めると, 次に選ぶパチクリが決まっていく. このパチクリ同士の関係を線で結んでいくと, 必然的にグラフになっている. ゆえに, この問題はグラフの最短経路を求める問題に帰着できる. ここでは, …

AOJ 0246 - Bara-Bara Manju

問題文 : ばらばら饅頭解法 : まず, 2個の饅頭で作る組み合わせが最適である(らしい) ので, 2個で作れる饅頭の個数を貪欲法で求める. (証明できなかった).その後は, ナップサック問題を解く要領でメモ化再帰を行う. このように, 配列に値を持たせて行うDPをm…