Mister雑記

競プロやります。

ARC096-D「Static Sushi」(500)

問題リンク:https://beta.atcoder.jp/contests/abc095/tasks/arc096_b

 

解説する問題に迷ったので、とりあえず新しい方から自力ACできたD問題を取り上げることにした。「Static Sushi」、直近のABC、ARCということで記憶に新しい人も多いのではなかろうか。私も本番で解いたので、そのとき何を考えていたのかをベースに解法をまとめようと思う。

問題概要

円形のテーブルの周上に寿司がいくつか置かれている。
寿司を食べれば特定のカロリーが得られる一方で、テーブルの周りを移動するのにカロリーを消費する。
どこでも行動を止められるものとしたとき、得られるカロリーの最大値を求めよ。

解説

解法

問題文を読み終わり、まずは軽く図を描いて思考を整理する。3分ほどして、直感的にこう考える。 「時計回りと反時計回り両方で、しらみ潰しに寿司食った場合だけ考えればいいのでは?」
つまり目についた寿司を順番にひたすら食べ続けて、カロリーが最大になるところで抜ければいい、ということである。 というのも、途中で寿司を飛ばすのは明らかなロスだし、かといって途中でわざわざバックして寿司のないエリアを移動するのはロスに違いない、と考えたためである。
そうして書いたコードが以下の通り。

    int main() {
    ll N, C;
    cin >> N >> C;

    vector<ll> x(N + 2), v(N + 2);
    for(ll i = 1, i <= N, i++) {
        cin >> x[i] >> v[i];
    }

    x[0] = 0;
    x[N + 1] = C;

    ll maxcal = 0;
    // 摂取しうる最大カロリー(答え)

    ll cal = 0;
    // 摂取した実質カロリー

    // まずは時計回りから
    for(ll i = 1, i <= N, i++) {
        cal -= x[i] - x[i - 1];
        // 移動した分だけカロリー減少
        cal += v[i];
        // 食事した分だけカロリー増加
        maxcal = max(maxcal, cal);
    }

    cal = 0;
    // 続いて反時計回り
    for(ll i = N, i > 0, i++) {
        cal -= x[i + 1] - x[i];
        cal += v[i];
        maxcal = max(maxcal, cal);
    }

    cout << maxcal << endl;
    return 0;
}

しかしこのコード、実行すれば分かるが2つ目のサンプルで落とされる。 そんなに500点問題は甘くない。
(ちなみに上のように、合ってるように思えて実際は的外れという解法を競プロ界隈では「嘘解法」と呼ばれていたりする。解法は極力証明を考えてから実装しよう。)

 

弾かれたサンプルの例を図に描いて更に5分ほど考えた結果、次の結論に至った:「途中で1回だけ逆走するケースが存在する」
つまり途中までひたすら寿司を食って、Uターンした後すでに寿司を食い尽くしたエリアを逆走し、 反対側の寿司を食った方が得をするケースがあるということだ。 実際この考え方は正しい。2回以上のUターンは明らかにロスだが、1回だけならロスにならないケースが存在するのである。サンプルケースに感謝。

実装

ここまで分かれば後は実装するだけ......かと思いきやそう簡単にはいかない。実際に愚直に実装した場合の計算量を確認してみよう。
まず「どこでUターンするか」のパターンは各方面でそれぞれN通りある。 その各パターンについて先と同様にして愚直にO(N)でカロリーを計算すると、全体の計算量がO(N^2)となる。 しかしこの問題の制約はN≦10^5なので、これではTLEとなってしまう。

ならどうすればいいか。私が真っ先に思いついた解決策は「累積和DP」だった。 「累積和」とは、その名の通りいくつか並んだ要素を途中まで全て足したもののことである。 それをメモしていって再利用するというのが累積和DPだ。 しかし今回の場合、メモするのは累積和自体ではないので累積和DPと呼ぶのは少し違うかもしれない。

f:id:misteer:20180604122830j:plain

上がDPのイメージ。各寿司まで辿り着いたときの、 それまでのカロリーの最大値 をメモしている。なぜその時点でのカロリーではなく最大値をメモするのかはこの後分かる。なおdp[0]に時計回り、dp[1]に反時計回りをメモしている点に注意されたい。

f:id:misteer:20180604122824j:plain

そして先程計算したメモによって、寿司iで逆走したときの最大カロリーは上のように求まる。
ここで先程何故カロリーの最大値をメモしたのかが分かる。もしもカロリー自体をメモしてしまうと、 ③の途中で抜けるケースを考慮するためにdpを順番に見ていかなければならなくなる。これにはO(N)かかるので、結局TLEになってしまう可能性が高い。

解答コード

そんなこんなで実装したコードが以下の通り。

    int main() {
    ll N, C;
    cin >> N >> C;

    vector<ll> x(N + 2), v(N + 2);
    for (ll i = 1; i <= N; i++) {
        cin >> x[i] >> v[i];
    }
    x[0] = 0;
    x[N + 1] = C;

    ll cal = 0;
    vector<vector<ll>> dp(2, vector<ll>(100010, 0));

    for (ll i = 1; i <= N; i++) {
        cal -= x[i] - x[i - 1];
        cal += v[i];
        dp[0][i] = max(dp[0][i - 1], cal);
        // ここでそれまでのカロリーの最大値をメモ
    }

    cal = 0;
    for (ll i = N; i >= 1; i--) {
        cal -= x[i + 1] - x[i];
        cal += v[i];
        dp[1][i] = max(dp[1][i + 1], cal);
    }

    ll maxcal = 0;
    for (ll i = 0; i <= N; i++) {
        // 時計回り
        cal = dp[0][i] + dp[1][i + 1] - x[i];
        maxcal = max(maxcal, cal);

        // 反時計回り
        cal = dp[0][i] + dp[1][i + 1] - C + x[i + 1];
        maxcal = max(maxcal, cal);
    }

    cout << maxcal << endl;

    return 0;
}

これを提出すれば無事ACとなる。お疲れ様でした。 ちなみに本番の私はこれを解くのに30分弱かかってしまった。まだまだ未熟である。

感想

500点も頷けるが、400点で出てもおかしくはないかもしれないというレベルである。累積和の練習として良問と言えるだろうか。 累積和はAtCoderもとい競プロ全体でも相当出ているので、しっかり習得しておきたいところである。
累積和と言うと「史上最難の200点問題」こと AGC023-A「Zero-Sum Ranges」 が思い出されるが......この話はまたの機会に。

補足

無論本番に出したのはこれほどまとまったコードではないし、マクロも大量に使っている。 私が本番に出したコードを見たい物好きな方は こちらをどうぞ。