Educational Codeforces Round 63 D. Beautiful Array

Beautiful Array

問題はこちら

自分が気づいたところ

まず最初に，xが負の時は最小区間和を選んできてそれをx倍する．xが正の時は最大区間和を選んできてそれをx倍する．とすれば最大値が求まると考えた．ここでセグ木とかをググり始める... だが，区間和を取ってきて，その区間和のindexも取ってくるのはどのようにして実装すればいいかわからなかった．

次に，累積和を尺取りのように持てば区間和の最大・最小を検出できるのではないかと考えたが，これもACにはならず．

解説を読んで

TwitterでDPだという文面を見たので，実装は見ないで自分で書いてみた．状態の遷移は以下の通りにできると考えた．

ここでは3の状態がポイントで，一回*xをする→そのまま足すという遷移をした場合は，もう一度*xをして足すことはできない（連続した区間にのみ*xできる）ためにそれを新たに状態として持つことにした．

dp[i+1][0] := i番目をそのまま足す
dp[i+1][1] := i番目を*xして足す
dp[i+1][2] := 使わない（0にリセット）
dp[i+1][3] := i番目までに*xをしたことがあり，i番目のものはそのまま足す

状態遷移はそれぞれを場合分けしてイテレーションを回していく．詳しくはコードを見ると早いと思う．

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)

const ll half_inf = ll(1e5);
ll dp[3 * half_inf + 10][4];

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

    const int plus = 0, multi = 1, no = 2, al_multi = 3;
    for (int i = 0; i < n; ++i) {
        dp[i + 1][al_multi] = max({dp[i][multi] + a[i], dp[i][al_multi] + a[i]});
        dp[i + 1][plus] = max({dp[i][plus] + a[i], dp[i][no] + a[i]});
        dp[i + 1][multi] = max({dp[i][multi] + x * a[i],
                                dp[i][no] + x * a[i],
                                dp[i][plus] + x * a[i]
                               });
        dp[i + 1][no] = 0;
    }
    ll ans = 0;
    for (int i = 0; i <= n; ++i) {
        for (int j = 0; j < 4; ++j) {
            ans = max(dp[i][j], ans);
        }
    }
    cout << ans << endl;
    return 0;
}

Submission #53197896 - Codeforces

こちらの解説を見るとどうやら状態数は3つでいいらしい？？（後ほど実装したい）

cinnamo-coder.hatenablog.com

こちらの解法が似ているらしいので後ほど解きたい．

atcoder.jp

自分の詰まったところ

そもそもDPという発想がコンテスト中に浮かんでこなかった．
遷移の歴史によって，次に行える遷移が違うがそれをどう実装するかについて．

学んだこと

遷移規則が複数あるが，列挙できる → DPという発想．
- 連続区間を使う/使わないなどはかなり典型例になるのでは？？
状態を増やすことによって遷移規則を表現できることがある．

ひらめの日常

日常のメモをつらつらと