COLOCON -Colopl programming contest 2018-D:すぬけそだて――トレーニング――
問題
https://beta.atcoder.jp/contests/colopl2018-qual/tasks/colopl2018_qual_d
考え方
dpを考えるのは自然である。
dp[i][k] := 個までの時刻のうち、 回起動しているときの知力の最大値
とする。ナイーブなDP遷移を考えると
dp[i][k] = (0 <= j < i) max(dp[j][k-1] + min(x, t[i] - t[j]))
となる。これは遷移に かかるので全体の計算量は になり間に合わない。
与えられた条件を考えると、
スタミナが満タンになる前に起動する場合・・・なるべく遅く起動する
スタミナが満タンになった後に起動する場合・・なるべく早く起動する
ことがよいとわかる。
よって t[j] <= t[i] + x なる最大の を考えると dp[i][k] からは
- dp[j][k+1] + min(x, t[j] - t[i])
- dp[j+1][k+1] + min(x, t[j+1] - t[i])
の 通りの遷移のみ考えればいいことがわかる。これは であるから全体の計算量が となるので解くことができた。
public void solve(int testNumber, InputReader in, PrintWriter out) { int n = in.nextInt(); int x = in.nextInt(); int[] t = in.nextIntArray(n); int[][] dp = new int[n+1][n+1]; for (int i = 0; i < n; i++) { // t[j] <= t[i] + x なる最大の j int j = 0; for (j = i; j + 1 < n && t[j+1] <= t[i] + x; j++); for (int k = 0; k < n; k++) { dp[j][k+1] = Math.max(dp[j][k+1], dp[i][k] + Math.min(t[j] - t[i], x)); if (j+1 < n) { dp[j+1][k+1] = Math.max(dp[j+1][k+1], dp[i][k] + Math.min(t[j+1] - t[i], x)); } } } for (int k = 0; k < n; k++) { int ans = 0; for (int i = 0; i < n+1; i++) { ans = Math.max(ans, dp[i][k]); } out.println(ans + x); } }
ポイント
- ナイーブなDPを考えてみると、どこが高速化できるか見えてくる
- 条件を満たす index の前後を調べる
類題
- D - Equal Cut (条件の直前・直後を調べるという意味で)
雑記
ちなみに dp の2次元配列を long で宣言するとMLEになります。