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

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

AtCoder ABC 163 E - Active Infants (500 点)

探索順序を上手に決めると、普通の 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;
}