第１２回日本情報オリンピック予選（過去問)_D_ 暑い日々 (Hot days)

DPの問題.前日の情報をどうするか,そこがカギとなります.

atcoder.jp

問題の説明

温度条件が $T$ 度の下で $D$ 日服を選んだ場合の派手さの差の絶対値の合計の最大値を求めよ.

条件

$1≦D≦200$
$1≦T≦60$

考えた事

派手さの差の絶対値の合計を考える.つまり前の情報を遷移させる必然性を伺わせる事から,この問題の解法としてその場その場で最適な服を選び続けるGreedyかDPが思いつくだろう.

事実としてこの問題はGreedyに近い発想でも解く事が出来る*1.

keidaroo.hatenablog.com

この記事にあるように,温度条件を満たしている服の中で1日毎に派手さが最大と最小のものを取り,前の日に選んだ服との派手さの差が大きくなる方を順々に選び続ければいいとなる.

上の方法が成立する理由は,差の絶対値を足し続ける手法であるため,基本端っこと端っこ(最大と最小)を選び続ける方が差の絶対値が大きくなるからである.この場合の計算量は $O(D)$ であり,非常に高速である.

ただ,残念ながら自分はそれが思いつかなかった.ポンコツやね.ではどうするか.愚直にDPをしていこう.また手順に則ってやっていく.

ステップ1.全探索出来るかどうか

全探索する場合の計算量の見積もりをしよう.とりあえず服を全部選べると仮定した場合が都合がよい*2.

この場合, $N$ 枚の服から1枚を選ぶことを $D$ 日繰り返すため,計算量は $O(N^D)$ となる.

指数時間, $D$ の上限は $200$ ,当然全探索では間に合いません.

ステップ2.状態の遷移を考える

この問題の場合,前日に選んだ服と今日選んだ服の派手さの差の絶対値をそこまでの派手さの差の絶対値の合計に足し合わせる事で遷移するだろう.

ステップ3.変数を見つけ,配列の表を書く

遷移する変数は何になるだろうか.自分は最初,日数,前日に選んだ服,当日の服を変数にするといいと考えた.三次元DPである.この場合,服を選べない場合と同じ服しか選べない場合を差別化するために初期値は $-INF=-10^{18}$ で設定した.

注意したいのは1日目で,この時にはいずれにせよ派手さの差の絶対値の合計値ゼロである.しかし,温度条件を満たしている服と満たしていない服が存在するため,前者には $0$ ,後者はそのまま $-INF$ とした.

もちろんこの発想は間違っていない.ただ図に起こしてみるとどうであろうか.

これは入力例1を図に起こしたものである. $i$ が前日に選んだもの(存在しない場合は $0$ ), $j$ がその日に選んだものである.

見ての通り遷移がややこしい.なぜか. $j→i$ となるからである.ある日に選んだものが次の日に影響するため,このようにswapする.だからややこしいのである.

また, $dp_{2,3,2}$ のような後に生きない無駄なデータがある.そしてどのデータが無駄か必要か判別するのもややこしい.使うデータを判別するならば $dp_{2,2}$ 列の中の最大値を使えばよい(前々日に選んだ服はどうでもいいため).しかし毎回毎回それを調べるのも億劫である.

そして自分は何がしたかったのか0以上のデータを判別してからこれをやろうとしたため,ややこしすぎて実装出来なくなってしまった.さてどうしようか.

ステップ4.漸化式の作成

大事なのは変数である.上の中でいらない変数はなんであろうか.答えは昨日選んだ服である.なぜいらないか.理由は簡単である,もし服を選べない場合,そこは $-INF$ となっているため,昨日の服の選択の如何に関わらず,遷移する中での派手さの合計の最大値を求めさえすれば,問題は起きないという事だ.

何が言いたいかというと上の図の $i(0≦i≦4)$ を全て圧縮して以下の図のようにすればいい.

$i$ を全て圧縮して二次元DPとし, $dp_{2,2}$ には $dp_{1,j}$ に全て $abs(C_j-C_2)$ を足し,その最大値だけを記録していけばよいとなる.ポイントとなるのは初期値であり,初期値が $-INF$ であるからこそ,前日に選べた服と選べなかった服を差別化できる.一回の派手さの差の絶対値を足したとて, $-∞$ は $-∞$ のまま.一々「前の日に使えた服は何だっけ～、ううううう.」などと悩まなくてよいのだ.

したがって変数は2つでよい.一応もう少ししっかり書くと, $A_j≦T_d≦B_j$ の時,

$dp_{d,j}=max(dp_{d, j},dp_{d-1, i} + abs(C_i-C_j))$

となるだろう. $i$ については服の数だけループを回して全て調べあげればよい.

もちろん条件を満たしていない場合, $dp_{d,j}=dp_{d, j}$ となるため,一々書く必要もない.

今回の場合,「最高気温が天気予報に従ったときに着るのに適した服が, $D$ 日間のどの日に対しても $1$ つ以上存在することが保証されている.」とあるため,必ず1つは条件を満たす. $d$ 行全てが $-INF$ で終わる事はあり得ない事が保証されているため,このようにして考えていい.まとめると,

$dp_{d,j}=max(dp_{d, j},dp_{d-1, i} + abs(C_i-C_j))(A_j≦T_d≦B_j)$

$dp_{d,j}=dp_{d,j}=-INF(otherwise)$

となる.初期条件としては

$dp_{1,j}=0(A_j≦T_0≦B_j)$

$dp_{1,j}=-INF(otherwise)$

とするとよいだろう.

ステップ5.漸化式を元に配列を埋める

ここまで書けば実装は難しくない.

vvll dp(D + 1, vll(N, -INF));

としてDP配列を作る.とりあえず $-INF$ で置いて置き,

rep(i, N) {
        if (A.at(i) <= T.at(0) && B.at(i) >= T.at(0)) {
            dp.at(1).at(i) = 0;
        }
    }

として $0$ を埋めればよい.

後は3重ループを回し,配列を埋めればよい.

reps(i, 2, D + 1) {
        rep(j, N) {
            if (A.at(j) <= T.at(i - 1) && B.at(j) >= T.at(i - 1)) {
                rep(k, N) {
                    CHMAX(dp.at(i).at(j),
                          dp.at(i - 1).at(k) + abs(C.at(j) - C.at(k)));
                }
            }
        }
    }

漸化式の部分はこのようになる.計算量は $O(D×N×N)=O(D×N^2)$ となり,高々 $O(10^6)$ となるため,十分間に合う.

ステップ6.求めたい配列の値を見て答えを導く

$dp_{D,j}$ を $j$ を動かして,最大値を出力すればよい.遷移がややこしくタフな問題であった.お疲れ様でした.

プログラム

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using ld = long double;
using P = pair<int, int>;
using Graph = vector<vector<int>>;
using vi = vector<int>;
using vl = vector<long>;
using vll = vector<long long>;
using vvi = vector<vi>;
using vvl = vector<vl>;
using vvll = vector<vll>;
using vvvll = vector<vvll>;
using vs = vector<string>;
using pii = pair<long long, long long>;
using mint = modint1000000007;
const long double EPS = 1e-10;
const long long INF = 1e18;
const long double PI = acos(-1.0L);
#define reps(i, a, n) for (ll i = (a); i < (ll)(n); i++)
#define rep(i, n) for (ll i = (0); i < (ll)(n); i++)
#define rrep(i, n) for (ll i = (1); i < (ll)(n + 1); i++)
#define repd(i, n) for (ll i = n - 1; i >= 0; i--)
#define rrepd(i, n) for (ll i = n; i >= 1; i--)
#define ALL(n) begin(n), end(n)
#define IN(a, x, b) (a <= x && x < b)
#define INIT                          \
    std::ios::sync_with_stdio(false); \
    std::cin.tie(0);
template <class T>
inline T CHMAX(T& a, const T b) {
    return a = (a < b) ? b : a;
}
template <class T>
inline T CHMIN(T& a, const T b) {
    return a = (a > b) ? b : a;
}

int main() {
    ll D, N;
    cin >> D >> N;
    vll T(D);
    rep(i, D) { cin >> T.at(i); }
    vll A(N);
    vll B(N);
    vll C(N);
    rep(i, N) { cin >> A.at(i) >> B.at(i) >> C.at(i); }
    vvll dp(D + 1, vll(N, -INF));
    rep(i, N) {
        if (A.at(i) <= T.at(0) && B.at(i) >= T.at(0)) {
            dp.at(1).at(i) = 0;
        }
    }

    reps(i, 2, D + 1) {
        rep(j, N) {
            if (A.at(j) <= T.at(i - 1) && B.at(j) >= T.at(i - 1)) {
                rep(k, N) {
                    CHMAX(dp.at(i).at(j),
                          dp.at(i - 1).at(k) + abs(C.at(j) - C.at(k)));
                }
            }
        }
    }
    ll max = -INF;
    rep(i, N) { CHMAX(max, dp.at(D).at(i)); }
    cout << max << endl;
}

*1:後述するがこれでも前の情報を記録する必要があり,厳密にはDPである.ただ,計算の工夫によって大きく変わる事から紹介する.

*2:こういう場合,どのようなパターンが入力されるか分からないので計算量的に最悪を考えておくといい

garakutagoya

興味、関心のあったこと、そして私の気持ちなどを残していきたい