探索順序を上手に決めると、普通の DP になる系！！！
EDPC の Zubton なんかもそうやね！

問題概要

$N$ 個の正の整数 $A_{1}, \dots, A_{N}$ が与えられる。これらを並び替える。並び替えのスコアは以下のようにして決まる。

各 $x$ に対して、
$A_{x}$ の index が $y$ に移動するとき
$A_{x} \times |y - x|$ を加算する

スコアの最大値を求めよ。

制約

$2 \le N \le 2000$

考えたこと

順列を最適化する系の問題。そういうのって、

制約が小さければ bitDP
挿入 DP
箱根 DP
フロー
要素を適切に並び替えれば "原始的に" 処理できる系

とか色々ある。今回、第一感だと箱根 DP かな...と思ってしまうんだけど、それだと上手くいかないんだよね。。。なんで上手くいかないのかを感覚で言うのは難しいのだけど、「 $A_{1}, \dots, A_{N}$ がそれぞれ互いに異なるから上手くいかない」という感じ。

こればかりは試行錯誤するしかないのかな...今回は、要素を適切に並び替えれば原始的に処理できる系だった。

最大の要素に着目してみる

一般に問題の解き方として、「最大の要素をどう扱うべきか」について考えると道が開けることはメッチャ多い！！！

今回の問題も、その視点から考察してみる。そうすると、

$A_{i}$ が大きいやつは、なるべく大きく動かしたい！！！
$A_{i}$ が最大なやつは、左側へ動かすなら左端へ、右側へ動かすなら右端にすればいい！！！ (ここ重要)

といったことが見えて来る。もし仮に $A_{i}$ が最大なやつが左端または右端以外の場所にあるとしたら、それを左端または右端に寄せることでスコアが上がる (下がることはない) からだ。こういう「〜に寄せてもスコアは下がることがない、よって寄せたものだけ考えれば良い」という考え方は、ものすごい頻出。

さらに考察を進めると、二番目に大きいやつも、左詰め、または右詰めすればよいことがわかる。以上から、

$A_{i}$ が大きいものから順に、
左詰め、または、右詰めしていく

という風にすれば良いことがわかった！！！

原始的な DP へ

さて、問題の本質は、 $A_{i}$ を大きい順に並び替えた上で、

各要素のうち、どれを左詰めして、どれを右詰めしていくかの選択を順次行うこと

だとわかった。でも、こういう「二択を繰り返す」というシチュエーションは、かなりの高確率で "原始的な DP" で取り扱うことができる。ナップサック問題だってそうだ。あれも「各品物を選ぶか選ばないかの二択」を繰り返して行くという問題だ。

原始的な DP というのは

dp[ (何個まで見たか) ][ (どうなっているか) ] := その状態での最適解

という形式の DP のことを言っているんだと解釈している。実際、AtCoder で出題される DP の 8 割は、この形式になってると思う。今回も、

dp[ i ][ j ] := A が大きい順に i + j 個について、i 個を左詰めして、j 個を右詰めしたときのスコア

という感じに定義してみる。そうすると、i + j + 1 個目の要素 A[ i + j ] を左詰めするか、右詰めするかを考えて、

左詰するとき： chmax(dp[ i + 1 ][ j ], dp[ i ][ j ] + (その移動スコア))
右詰するとき： chmax(dp[ i ][ j + 1 ], dp[ i ][ j ] + (その移動スコア))

として求めることができる。

#include <bits/stdc++.h>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

using pll = pair<long long, long long>;
int main() {
    int N; cin >> N;
    vector<pll> A(N);
    for (int i = 0; i < N; ++i) cin >> A[i].first, A[i].second = i;
    sort(A.begin(), A.end(), greater<pll>());

    vector<vector<long long>> dp(N+1, vector<long long>(N+1, 0));
    for (int i = 0; i < N; ++i) {
        for (int j = 0; i + j < N; ++j) {
            // left
            chmax(dp[i+1][j], dp[i][j] + A[i+j].first * (A[i+j].second - i));

            // right
            chmax(dp[i][j+1], dp[i][j] + A[i+j].first * ((N-1-j) - A[i+j].second));
        }
    }
    long long res = 0;
    for (int i = 0; i <= N; ++i) chmax(res, dp[i][N-i]);
    cout << res << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 163 E - Active Infants (黄色, 500 点)

問題概要

制約

考えたこと

最大の要素に着目してみる

原始的な DP へ