naoya_t@hatenablog

いわゆるチラシノウラであります

2019新年初埋め : Tough Journey (600)

2019新年初埋め。

問題 (Tough Journey) は未埋めの中からタイトルで選んだ。(去年のCODE FESTIVAL 2018 Finalより)
Tough Journeyをものともせず瞬殺できる年になりますように。

CODE FESTIVAL 2018 Final (Parallel)

E - Tough Journey (600)

ん?
移動には水が1必要で、その1の水をどこで買うか(その場で買うのもありだしK-1個前までならOK)最安を選べばいいだけじゃないのかな
最安をどう保持する?dequeとか使うやつ?(O(N)で解けるんだよね。なんて言うんだっけ?)
考えるの面倒くさいからO(N\log N)だけどpriority_queueで書いた

ll solve_pq(int N, int K, vi& a) {
    priority_queue<ii> pq;
    pq.emplace(-a[0], 0);
    ll ans = 0;
    for (int i=1; i<=N; ++i) {
        ll top;
        while (pq.top().second < i-K) {
            pq.pop();
        }
        top = -pq.top().first;
        ans += top;
        if (i == N) break;
        pq.emplace(-a[i], i);
    }
    return ans;
}

手際がいまいち良くなかったけれど余裕の自力AC
→AC 17:20
https://atcoder.jp/contests/code-festival-2018-final-open/submissions/3908612
14ms

解説読んだ

自分の解法は想定解Bだった
そうそう「スライド最小値」。蟻本に載ってる。>なんて言うんだっけ

折角なのでスライド最小値で書き直してみる。
要点は

  • dequeには値ではなくインデックスを入れる
    • dequeの中のインデックスは昇順
    • インデックスが指している(元の配列の)値は最後に入れたやつとそれより小さいもののみ
  • i-K以前の記憶は(先頭から)捨てていく
ll solve(int N, int K, vi& a) {
    ll ans = 0;
    deque<int> dq;
    for (int i=0; i<N; ++i) {
        while (!dq.empty() && a[dq.back()] >= a[i]) dq.pop_back();
        dq.push_back(i);
        if (i >= K-1) {
            while (!dq.empty() && dq.front() <= i-K) dq.pop_front();
        }
        ans += a[dq.front()];
    }
    return ans;
}

→AC
https://atcoder.jp/contests/code-festival-2018-final-open/submissions/3908654
こっちは7ms