ARC043 D問題 引っ越し

これは難しい…難しすぎる…

1e6オーダーの家に1e3オーダーの家族(1~100人)を適当に入れて、住民の距離(任意の二人の組み合わせの距離の総和)をMAXにせよ、という問題。

スライドが神がかるほどわかりやすいのでこれだけ見ればおｋ
AtCoder Regular Contest 043 解説

考え方としては、まず任意の二人の組み合わせの距離とかいう巨大な計算量のものから、それらを家間の距離の総和と考えてみる。
家間の距離は、(辺の左の家の総人数)x(辺の右の家の総人数)で表されることがわかり、しかも左の家の総人数+右の家の総人数=constなので、つまり辺の左の家の総人数だけ考えればいいじゃん！ということになる。
次に、それら家族を並び替える方法を考える、これには定石として隣同士をswapしていく、という方法がありえる。バブルソートもそうだよね。するとなんと、a b cと家族が並んでいるとき、a < b > c ならばbをaかcどちらと交換しても最終的な結果が増大することがわかる。つまり、最適な並び替えにおいてa < b > cという並びはありえない！つまり a >= b <= cとなっている！そしてこのような並び替えの最適値を求めるには定石として、dp[i][x]を大きい方からi番目まで見た時ｍ左側の合計がxだったときの値の最大値、というようにしてdpをする方法がある！

なるほどなるほどー実装は確かに簡単だが、a >= b <= cまでの考察が地獄だ…

constexpr int MAXM = 1010;
constexpr int INF = 1e9;
int S[MAXM];
ll dp[2][MAXM*100];

int main()
{
    cin.tie(0);
    ios::sync_with_stdio(false);

    int N, M;
    ll sum = 0;
    cin >> N >> M;
    rep(i, M){
        cin >> S[i];
        sum += S[i];
    }
    sort(S, S+M);
    reverse(S, S+M);
    rep(i, 2) rep(j, MAXM*100) dp[i][j] = -INF;

    ll nowsum = 0;
    dp[0][0] = 0;
    for(int i=0; i<M; i++){
        int cur = i&1;
        int tar = cur^1;
        for(int j=0; j<=nowsum; j++){
            dp[tar][j] = max(dp[tar][j], dp[cur][j]+(nowsum-j)*(sum-(nowsum-j)));
            dp[tar][j+S[i]] = max(dp[tar][j+S[i]], dp[cur][j]+(ll)j*(sum-j));
        }
        nowsum += S[i];
    }

    ll res = 0;
    for(int i=0; i<=sum; i++){
        res = max(res, dp[M&1][i]+ll(N-M+1)*i*(sum-i));
    }
    cout << res << endl;
}