まず、あり得ない $X,Y$ を考える。
移動回数がわかれば、$A:(x+1,y+2),B:(x+2,y+1)$ それぞれを採用した回数は鶴亀算の要領でわかる。仮に $d$ 回全てAを使ったら $X=d$ になるはずだが、そこからBに置き換えていったら、1回ごとに $x$ 座標は1ずつ増えるので、結局Aで移動したのは $X-d$、Bは $Y-d$ 回となる。
あとは ${}_dC_{X-d}$ を求めればよい。
よくある、格子上の道路を上か右にのみ移動する経路の個数を求める問題の、それぞれの移動に+1しただけとも考えられる。
def prepare(n, MOD): f = 1 for m in range(1, n + 1): f = f * m % MOD fn = f inv = pow(f, MOD - 2, MOD) invs = [1] * (n + 1) invs[n] = inv for m in range(n, 1, -1): inv = inv * m % MOD invs[m - 1] = inv return fn, invs def solve(x, y): d, m = divmod(x + y, 3) if m != 0 or x < d or y < d: return 0 c = abs(d - x) MOD = 10 ** 9 + 7 f, invs = prepare(d, MOD) return f * invs[c] * invs[d - c] % MOD x, y = map(int, input().split()) print(solve(x, y))
DPの典型であるナップサック問題だが、1個だけなら溢れてもいい、というところがポイント。
ざっくり考えると、時間がかかる料理を最後に1つだけとっておき、それ以外で $T$ 未満ぎりぎりまで食べ、最後に取っておいた料理を注文、という流れがよさそう。 実際、食べる料理の集合が決まっているとすると、一番時間のかかる料理を最後に注文するとして問題ない。
通常のナップサックなら、$i$ 番目の料理を考慮中、それを食べれば時間切れになる遷移はスキップするが、 それをスキップせず、最後に注文したとして満足度の最大値を更新すればよい。
$dp[i][j] = i$ 番目の料理まで考慮して、時間 $j$ かけることで得られる満足度の最大値
擬似コード ans = 0 for i番目の料理の所要時間a, 満足度b in 料理リスト: for 時間t, 満足度s in dp[i]: if i番目の料理を食べたら時間切れ: ans = max(ans, s + b) else: dp[i+1][t+a] = max(dp[i+1][t+a], s + b)
その際、時間のかかる料理を先に処理してしまうと、タイムリミットまでに他の料理をさらに食べられるのに、最適化されないまま満足度を確定させてしまう。 これを避けるには時間の短い料理から順に処理すればよい。
N=3 T=10 Ai Bi 1 3 10 2 10 50 3 5 30 1→2→3の順に処理すると、料理2でオーバーしてしまうため、 10+50=60が暫定解となってしまい、以降更新されない 1→3→2の順に処理すると、料理2の処理時点では既に1,3が考慮されているので 10+30+50=90が暫定解となり、これは正しい
import sys import numpy as np n, t = map(int, input().split()) knapsack = np.zeros(t, dtype=np.int64) cuisines = [tuple(map(int, line.split())) for line in sys.stdin] cuisines.sort() tmp_ans = 0 for a, b in cuisines: tmp_ans = max(tmp_ans, knapsack.max() + b) knapsack[a:] = np.maximum(knapsack[a:], knapsack[:-a] + b) print(max(tmp_ans, knapsack.max()))
DP。問題EもDPだったから連想しやすかった。
横には1行ずつしか塗れないので、最終的な $H$ の最大値の回数は最低限必要。1つだけ高くても全体が高くても回数は変わらないが、谷があるとそこで分断されるため回数がかさむ。
□□■□□ ■■■■■ ■■□■■ □□■□□ ■■■■■ ■■□■■ □□■□□ ■■■■■ ■■□■■ □□■□□ ■■■■■ ■■□■■ ■■■■■ ■■■■■ ■■■■■ 5回 5回 9回
よって、山を削る、谷を埋める、というのが塗る回数を減らすのに効果的。
山はどこまで削ればよいかというと、中途半端に削るより一気に削った方がいいし、削りすぎて谷になってしまっても逆効果。なるべく左右隣と合わせるのがよい。 左右の高さが違う場合、その間の高さなら塗る回数に影響は及ぼさない。ので、左に合わせると決め打っても問題ない。
だが、左と揃えればよいとはいえ、並んだ2列以上を同時に変更する場合もあることを考えると、1列単独では決められない。
もし左列を変更していたとしたら、さらにその左列(も変更していた場合はさらに……)と同じ高さに揃えているはずなので、 最後に変更しなかった列の高ささえわかれば、その高さに揃えればよい。
よって、以下のDPが構成できる。
$dp[i][j][k]=i$ 列目まで見て、変更回数が $j$ 回、最後に変更しなかった列の高さが $k$ である場合の、最小塗る回数
塗る回数は、塗りを新たに開始する行(左端)でカウントしておけば、終わる時(右端)では特にカウントなど考慮する必要は無い。
計算量は……詳しくは分からないが、まぁ $i,j,k$ ともに300が上限で $300^3$、これに状態の被りで何分の1かになって、まぁ大丈夫だろ~くらい。 実際、それまでに $j$ 回変更していて $i$ 列目は変更しないと決めたら、どこを変更していたかに依らず遷移は $dp[i][j][H_i]$ に集約される。
遷移には直前の列の情報しか不要なので、以降、$i$ は省略して、現在考慮中のを $dp[j][k]$、前の列の結果を $dp_p[j][k]$ とする。
初期状態は $dp_p[0][0]=0$
遷移は、左列の高さ $k$ と自身の高さ $H_i$ を比較する。
(※“←”は、現在の値があればそれと比較して小さければ更新、という代入を表す)
実際の実装では、$H_i$ は $10^9$ まで取り得るので、indexで持つ、座標圧縮、辞書で持つなどする必要がある。
以下の実装は、$(j, k)$ ごとタプルをキーにした辞書で管理している。 実装は楽だが、速度はどうしても遅くなり、いくつかのケースでTLEになる。 タプルをキーにしているのが遅いので、bitshiftして2変数を1つの整数にまとめると通った。 可読性が下がるが、アルゴリズム自体に手は入れないのでコンテスト中にあともうちょっとを詰めるには有効。
from collections import defaultdict n, k = map(int, input().split()) hhh = list(map(int, input().split())) INF = 10 ** 18 dp = defaultdict(lambda: INF) dp[0, 0] = 0 for h in hhh: ndp = defaultdict(lambda: INF) for (changed, prev_h), operate in dp.items(): if h == prev_h: ndp[changed, h] = min(ndp[changed, h], operate) elif h > prev_h: ndp[changed, h] = min(ndp[changed, h], operate + h - prev_h) if changed < k: ndp[changed + 1, prev_h] = min(ndp[changed + 1, prev_h], operate) else: ndp[changed, h] = min(ndp[changed, h], operate) if changed < k: ndp[changed + 1, prev_h] = min(ndp[changed + 1, prev_h], operate) dp = ndp print(min(dp.values()))
NumPyを使っても書ける。遷移を2次元で整理する。
$k$ を、最後に変更していない列の高さではなく列のindexとし、便宜上、$H_0=0$ を追加する。
初期状態 j 0 1 2 k 0 0 - - 1 - - - 2 - - - 3 - - -
$i=3$ 列目を処理中とする。
i-1までのDP状態 iのDP状態 j j k Hk 0 1 2 0 1 2 0 1 2 0 0 - - 0 ==> - - - ---> - - - 1 8 - 8 - (1) - - 8 統合 - - 8 2 1 8 1 - - 8 1 - 8 1 3 6 - - - - - - ,-> 13 6 - | ↓(2) 差分を加算 | | k Hk 差 0 1 2 0 1 2 | 0 0 +6 - - 0 ==> - - - | 1 8 0 - 8 - (2) - - - | 2 1 +5 13 6 - 縦方向 - - - | 3 6 - - - 最小値 13 6 - -'
import numpy as np n, k = map(int, input().split()) hhh = list(map(int, input().split())) hhh = np.array([0] + hhh, dtype=np.int64) INF = 10 ** 18 dp = np.full((n + 1, k + 1), fill_value=INF, dtype=np.int64) dp[0, 0] = 0 for i, h in enumerate(hhh[1:], start=1): ndp = np.full((n + 1, k + 1), fill_value=INF, dtype=np.int64) ndp[:i, 1:] = dp[:i, :-1] ndp[i] = (dp + np.maximum(0, h - hhh)[:, np.newaxis]).min(axis=0) dp = ndp print(dp.min())