D 問題「たのしい運動会(School Sports is Fun)」解説

部分点（1 点）解法

以下の説明は， 重み付き区間 $(A,B,F)$ を右端の値 $B$ で全ての区間をソートしておき，それらに対して $i=1,2,..N$ と番号付けしておくことを前提とする．また，選ばれた区間の番号の集合を $G$ として説明する．

$1$ 点分の部分点では $N \leqq 1000$ が成立する.

以下のように $dp[i]$ を定義し，動的計画法を行うことを考える．

$dp[i] := (最も右端の区間がi番目であるような集合 $G$ でのスコアの最大値)$

すると，それは以下の方法で求まる．

for (int i = 1; i <= N; i++){
    dp[i] = F[i]-(B[i]-A[i]) * C; // 空集合に区間iを追加する遷移
    for (int j = 1; j < i; j++){
        //(集合の右端)≦(区間iの左端)であるような集合に区間iを追加する遷移
        if (A[i] >= B[j]) dp[i] = max(dp[i], dp[j]+F[i]-(B[i]-B[j])*C); 
    }
}

これらの方法によって構築された動的計画法テーブルを用いれば最大値が求まる．最大値が負の数の場合は $0$ を出力すること(空集合が許されるため)．

この動的計画法は，集合 $G$ に対する特別な重み $C*(R-L)$ については，$G$ の構築途中で細かく刻んで足し合わせても問題ないという考え方に基づく．

この解法において，全体の時間計算量は $O(N^2)$ となる．

満点解法

区間の集合 $G$を構築するのではなく，区間を伸ばしながら，直接 $[L,R]$ を構築することを考える． そのために，区間の番号ではなく，時間軸をキーに取り，以下のように $dp[R]$ を定義し，動的計画法を行うことを考える．

$dp[R] := (右端が$R$ のときのスコアの最大値)$

すると，それは以下の方法で求まる．

for (int R = 1; R < MAXT; ++R) {
    dp[R] = 0;  // 新たに[R,R]という長さ0の区間を作る遷移
    dp[R] = max(dp[R], dp[R - 1] - C); // [?,R-1] -> [?,R] と伸ばす遷移
    for ( int id : S[R]) {
        // [?,A[id]] -> [?,R] と伸ばす遷移(重みFつき)
        dp[R] = max(dp[R], dp[A[id]] + F[id] - C*(R-A[id])); 
    }
}

時間は座標圧縮をすることで高々 $O(N)$ となる(今回は座標が取りうる値の数が $10$ 万通り程度なので行わなくて良い)ので，全体の計算量は $O(N)$ である． こちらの解法の方が部分点解法よりも直接的で簡潔であると感じる．