頭にやさしいABC285-E - zawatinはてなブログ

前置き

必死に考えてやっとの思いで解けたのにパフォが1500くらいしかでなくてひっくりかえっちゃった。

間違いを書いていたらごめんなさい。間違いを発見した場合は https://twitter.com/zawakasu に報告くださると幸いです。

問題概要

atcoder.jp

一週間が $N$ 日の世界で次の条件を満たすように平日と休日を割り当てる。

少なくとも週一回休日を設ける
毎週同じ割り当て方をする

数列 $A$ を与える。ある日の得点を以下に定める。

休日なら0
最後の休日からその日までの日数を $x$ 、その日から次の休日までの日数を $y$ とした時、 $A_{\min(x, y)}$

適切に休日と平日を割り当てた時の得点の最大値を求めよ。

制約

$1\ \leq\ N\ \leq\ 5000$

$1\ \leq\ A_i\ \leq 10^{9}$

観察

休日は週一で必要なのでとりあえず一個休日を置きます。ぐるぐる周期するので、一週間を円環で表現し、真上から時計回りに1日目, 2日目, 3日目, ....とします

どこに置いても回転したら一緒なのでとりあえず真上に置きます。
実装の時に頭を壊さないように $A$ を0-indexedに直して考えます。

(赤が休日）

もう一個休日をおいてみます。

まだよくわからないのでとりあえずもう一つ休日をおいてみます。えいや

今回は左側に休日をおきましたが、右側にある平日の得点が全く変わってないことがわかります。

これは得点の定義より明らかで、右側の平日にとって最後の休日と次の休日は最初に置いた休日と二番目に置いた休日のことなので今回の休日で右側の平日の得点は変化しません。

もちろん、右側に休日を置いたとしても同じことが言えます。（左側の平日の得点が変化しません）

つまり、休日で区切られた区間について独立に得点を最大化できたら、その総和を求めることで解を得ることができます。

ある区間 $[l, r)$ で得点を最大化する問題を解く時、 $i$ 日目 $(l \leq i \lt r)$ に休日を置くと、よりサイズの小さい２つの区間 $[l, i)$ と $[i + 1, r)$ に分かれ、それぞれ得点の最大化問題を解くことになります。対象の問題を複数の部分問題に分割して解く・・・・・これは動的計画法ですね。

解法

上の観察をそのまま $\text{dp}$ の定義に落としてみます。

$\text{dp}_{l,\ r}\ :=$ 休日に挟まれた連続する平日の区間 $[l,\ r)$ について、間に0個以上の平日を置いた時の最大得点

$\text{dp}_{l, r}$ を式で表すと

となります。言葉で説明すると

上・・・区間の長さが0なら得点の最大値ももちろん0(平日が存在しないので）

下の左・・・・休日を置かなかったときの得点、得点の定義をそのまま式にした

下の右・・・・ $i$ 日目に休日を割り当てた時の遷移、２つの区間に分かれている

という感じになります。

問題の解は $\text{dp}_{1, N}$ です。(0は１つ目の休日を置いているので省くことに注意）

区間が合計 $\frac{N \times (N - 1)}{2}$ 個、各区間に対して区間の長さ分ループが回るので、時間計算量 $O(N^{3})$ でこの問題を解くことができました。これはACするのに十分低速です。TLEします。

観察2

画像でもう一回遊びます。最初の休日を下に置いてみます。

最初の方でもちらっと言いましたが、これは180度回転することで上に休日を置いた状況と一致します。（実際に $A_0, A_1, A_2, A_3$ の数を数えると2, 2, 2, 1個で得点が一致する上にその並びかたも一生であることがわかります）

↓の画像の２つの区間はまた、上であげた２つ休日を置いた画像の区間とそれぞれ一致することがわかります。

このように一致している区間を観察すると、「区間の長さが一緒なら最大化した時の得点も一致する」が成り立つことがわかります。

得点は区間の場所に依存しないんですね

よって $\text{dp}$ を区間の長さのみの情報を持つように言い換えることができます

解法

$\text{dp}_{\text{len}}\ :=$ 長さが $\text{len}$ の休日に挟まれた区間に0個以上の休日を割り当てたときの得点の最大値

式で表すと

となります。

解は $\text{dp}_{N - 1}$ です。

区間の長さの種類は $N$ 個、 $\text{dp}_{text{len}}$ を求めるのに $\text{len}$ までループが回るので、 $O(N^{2})$ に改善できました。これは通ります。

実装例(C++)

メモ化再帰

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N; cin >> N;
    vector<int> A(N, 0);
    for (auto& a : A) {
        cin >> a;
    }

    vector<long long> dp(N, -1LL);
    auto rec = [&](auto rec, int len) -> long long {
        long long& res = dp[len];
        if (~res) {
            return res;
        }
        res = 0LL;
        if (len == 0) {
            return res = 0LL;
        }
        for (int i = 0 ; i < len ; i++) {
            res += A[min(i, len - i - 1)];
        }
        for (int i = 0 ; i < len ; i++) {
            res = max(res, rec(rec, i) + rec(rec, len - i - 1));
        }
        return res;
    };

    cout << rec(rec, N - 1) << endl;
}

非再帰

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N; cin >> N;
    vector<int> A(N, 0);
    for (auto& a : A) {
        cin >> a;
    }

    vector<long long> dp(N, 0LL);
    for (int len = 1 ; len < N ; len++) {
        for (int i = 0 ; i < len ; i++) {
            dp[len] += A[min(i, len - i - 1)];
        }
        for (int i = 0 ; i < len ; i++) {
            dp[len] = max(dp[len], dp[i] + dp[len - i - 1]);
        }
    }
    cout << dp[N - 1] << endl;
}

この解法のおいしいところ(主観）

累積和弱者に優しい
- もちろん累積和を使ってもよい。休日を置かなかったパートでループを回さなくなるだけ。
dpの遷移が得点の定義を追うだけ＆休日を一個置いて両隣を見るだけなので、添字を壊しづらい

あとがき

文章が拙くて申し訳ないです。