naoya_t@hatenablog

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

Codeforces: Manthan, Codefest 17

出てないけど

agwたんから聞いた問題

B. Marvolo Gaunt's Ring

http://codeforces.com/contest/855/problem/B

真ん中の値を固定(1〜N)して左右をO(log N)でどうにかするのかなあと一瞬思ったんだけど
サンプルケースを見ながら、ああ同じ数字を3回使ってもいいのか、もしかしてこれDPで解けるんじゃないかと思って dp[N][3] みたいな配列を作り、

  • p·ai + q·aj + r·ak の(1〜kまででの)最大値は p·ai + q·aj のそこまでの最大値と r·ak の和だし
  • p·ai + q·aj の(1〜jまででの)最大値は p·ai のそこまでの最大値と q·aj の和だし
  • p·ai の(1〜iまででの)最大値は普通に最大値だし

って
左からDPで、前のi←i←j←kだけ参照できればいいからdp[3]で良くて

ll solve(int n,  ll p, ll q, ll r, vector<int>& a) {
    vector<ll> dp(3);

    ll a0 = (ll)a[0];
    dp[0] = a0 * p;
    dp[1] = a0 * (p+q);
    dp[2] = a0 * (p+q+r);

    for (int i=1; i<n; ++i) {
        ll ai = (ll)a[i];
        dp[0] = max(dp[0], p*ai);
        dp[1] = max(dp[1], dp[0]+q*ai);
        dp[2] = max(dp[2], dp[1]+r*ai);
    }

    return dp[2];
}

int main() {
    vector<int> a(100000);
    loadvec(a, 4);
    int n=a[0],p=a[1],q=a[2],r=a[3];
    loadvec(a, n);
    ll ans = solve(n,p,q,r,a);
    cout << ans << endl;
    return 0;
}

あと、値の範囲は±3e18までだしlong longで行けるし
→WA食らった
http://codeforces.com/contest/855/submission/30692320
なんでだろう?
n=1の場合とか?いや問題ないよね

ちょっと書き換えてもう一度。

ll solve(int n, ll p, ll q, ll r, vector<int>& a) {
    vector<ll> dp(3, 0x8000000000000000LL);
    rep(i, n) {
        ll ai = (ll)a[i];
        dp[0] = max(dp[0], p*ai);
        dp[1] = max(dp[1], dp[0]+q*ai);
        dp[2] = max(dp[2], dp[1]+r*ai);
    }
    return dp[2];
}

int main() {
    vector<int> a(100000);
    loadvec(a, 4);
    int n=a[0],p=a[1],q=a[2],r=a[3];
    loadvec(a, n);
    ll ans = solve(n,p,q,r,a);
    cout << ans << endl;
    return 0;
}

→またWA食らった
http://codeforces.com/contest/855/submission/30692406
どゆこと?

テストケース見たら、-1000000000 だけから成る入力で0が出てる。

デバッグプリントして気がついた。vector<int>の読み込み部分(自作)でバグってる。
確保しているスペースと読み込み最大長がINT_MINを想定していない。
そこを直して(INTSPACE=11を12に変えただけだが)
→AC
http://codeforces.com/contest/855/submission/30692462