2021年 7月 1日

まえがき

やっほ〜 7月になってから初めての投稿だよ。

今日は7月ってことで、ジュライジュライした記事を心がけていきたいとおもっていま〜す。

ﾁｭﾄﾞｰﾝｯ！！！

まちがええた、これは地雷だ（うん)

健康管理

何した

ありが今日も働いているから俺も働いている。

具体的に

今日解いた問題

ABC095 D- Static Sushi

[寿司,全探索,累積]

まぁ、寿司を食った瞬間,もしくは一歩も動かずに店を出る。っていうのは分かると思う。
つまり、店を出る位置は0,x1,x2,x3,...,xnのいずれかということ。

解法 1. 時計回りに i 個食べた後、0の位置に戻ってから何個逆時計周りに食べるか(n-i個まで食べれる)を決める。(一番良いのは何個かっていうのは前処理で求められる) 2. その逆もやる。

食べる道順的なのは実は少なくて… 1. 時計回りに何個か食べた後退店 2. 反時計回りに何個か食べた後退店 3. 時計回りに何個か食べた後、0 の位置に戻って反時計回りに何個か食べて退店 4. 反時計回りに何個か食べた後,0 の位置に戻って時計回りに何個か食べて退店
(0の位置に戻って、というのはわかりやすさのためにそうしています。)
時計回りに1個食べた後反時計回りに歩いて1個、その後時計回りに歩いて食べる。
というのは無駄です。

累積で、時計回りにi個まで食べれるとき、+になるカロリーの値の最大値をO(1)で取れるようにしました。

int main()
{
    ll n, c;
    cin >> n >> c;
    vector<ll> x(n), v(n);
    rep(i,n) cin >> x[i] >> v[i];

    // 左回りに取っていった時の累積
    vector<ll> left(n+1);
    ll pos = 0;
    left[0] = 0;
    rep(i,n){
        left[i+1] = left[i] + v[i] - (x[i] - pos);
        pos = x[i];
    }
    vector<ll> right(n+1);
    right[0] = 0;
    pos = c;
    rep(i,n){
        right[i+1] = right[i] + v[n-i-1] - abs(x[n-i-1] - pos);
        pos = x[n-i-1];
    }

    // 左から i 個取れるときの最大
    vector<ll> max_left(n+1);
    rep(i,n+1){
        max_left[i] = left[i];
        if(i != 0) chmax(max_left[i], max_left[i-1]);
    }
    vector<ll> max_right(n+1);
    rep(i,n+1){
        max_right[i] = right[i];
        if(i != 0) chmax(max_right[i], max_right[i-1]);
    }

    ll ans = 0;
    rep(i,n+1){
        // 左からi個食べる
        ll tmp = left[i];
        chmax(ans,tmp);
        if(i == n) // 全部食った
        {
            continue;
        }
        else
        {
            // 右から n - i 個食える
            if(i != 0){
                // 0 まで戻ってくる
                tmp -= x[i-1];
            }
            tmp += max_right[n-i];
            chmax(ans,tmp);
        }
    }
    rep(i,n+1){
        // rightからi個食べる
        ll tmp = right[i];
        chmax(ans,tmp);
        if(i == n) // 全部食った
        {
            continue;
        }
        else
        {
            // 右から n - i 個食える
            if(i != 0){
                // i = 1 なら x[n-1];
                tmp -= (c-x[n-i]);
            }
            tmp += max_left[n-i];
            chmax(ans,tmp);
        }
    }
    cout << ans << endl;
}

あとがき

以下は毎回記事に貼っているテンプレート

基本的に読書はTwitterで絡みのある人だけだと思いますが、僕のブログだけ見てるって人もいるかもしれないので、一応自己紹介っぽいことをしている記事を貼っておきます - 瑞々しぃにぼしの自己紹介(自己紹介の記事です)

草体にぼ日記

だらだらと

2020年7月1日　日記