mayoko’s diary

プロコンとかいろいろ。

8VC Venture Cup 2016 - Final Round C. Package Delivery

これはいろいろ難しい問題でした… 良い問題だと思います。

解法

まず方針です。なんとなく貪欲な気がしますが, 気づくのが難しいです。
next[i] = (x[i] から n 以内で進める場所にあって, p[i] よりもコストが小さい, 最もx[i] に近い座標) を求めます。next[i] は存在しない可能性もあります。その時は next[i] = -1 にしておきましょう。この時,

  • next[i] が存在する場合
    • next[i] にいける最低限の燃料だけ補充し, next[i] に向かう
  • next[i] が存在しない場合
    • x[i] で燃料を満タンにして先に進む

という戦略が最適です。まぁ言われればアタリマエですね。

で, あと問題になるのは, next[i] を高速で求める方法です。これには stack が使えます。下の問題に似た感じです(n 回目)。
mayokoex.hatenablog.com

const int MAXM = 200200;
const int INF = 1e9+7;
pii P[MAXM];

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int d, n, m;
    cin >> d >> n >> m;
    P[0] = pii(0, INF);
    P[m+1] = pii(d, 0);
    for (int i = 1; i <= m; i++) cin >> P[i].first >> P[i].second;
    m += 2;
    sort(P, P+m);
    vector<int> next(m, -1);
    stack<int> st;
    for (int i = 0; i < m; i++) {
        while (!st.empty()) {
            int index = st.top();
            if (P[index].second <= P[i].second || P[index].first+n < P[i].first) break;
            next[index] = i;
            st.pop();
        }
        st.push(i);
    }
    ll ans = 0;
    int now = n;
    for (int i = 0; i < m-1; i++) {
        if (P[i+1].first - P[i].first > n) {
            cout << -1 << endl;
            return 0;
        }
        if (next[i] == -1) {
            ans += (ll)(n-now) * P[i].second;
            now = n;
        } else {
            int need = P[next[i]].first-P[i].first;
            if (now < need) {
                ans += (ll)(need-now) * P[i].second;
                now = need;
            }
        }
        now -= P[i+1].first-P[i].first;
    }
    cout << ans << endl;
    return 0;
}