駒 (Pieces) [大手前プロコン 2019 B]

https://atcoder.jp/contests/otemae2019/tasks/otemae2019_b

解説

https://atcoder.jp/contests/otemae2019/submissions/6930836

変数が多く、何か手を付けていいかわからないかもしれない。
こういう時は何かを固定するのがいい。
最も効果的な決め所を探すと、どこに駒を集めるかで全探索してみよう。
これはM通りあり、操作によって、そこに移せるかどうかをO(K+N)で試せばいいので、O(MK)で間に合う。

int M, N, K, X[2010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> M >> N >> K;
    rep(i, 0, N) cin >> X[i];

    int ans = 0;
    rep(m, 1, M + 1) {
        vector<int> cnt(M + 1);
        rep(i, 0, N) cnt[abs(m - X[i])]++;
        int tot = cnt[0];
        rep(k, 1, K + 1) if (cnt[k]) tot++;
        chmax(ans, tot);
    }
    cout << ans << endl;
}