COLOCON -Colopl programming contest 2018-D：すぬけそだて――トレーニング――

問題

https://beta.atcoder.jp/contests/colopl2018-qual/tasks/colopl2018_qual_d

考え方

dpを考えるのは自然である。

dp[i][k] := i 個までの時刻のうち、k 回起動しているときの知力の最大値

とする。ナイーブなDP遷移を考えると

dp[i][k] = (0 <= j < i) max(dp[j][k-1] + min(x, t[i] - t[j]))

となる。これは遷移に O(N) かかるので全体の計算量は O(N^3) になり間に合わない。

与えられた条件を考えると、
スタミナが満タンになる前に起動する場合・・・なるべく遅く起動する
スタミナが満タンになった後に起動する場合・・なるべく早く起動する
ことがよいとわかる。

よって t[j] <= t[i] + x なる最大の j を考えると 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])

の 2 通りの遷移のみ考えればいいことがわかる。これは O(1) であるから全体の計算量が O(N^2) となるので解くことができた。

       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 の２次元配列を long で宣言するとMLEになります。