AtCoder Beginner Contest 160 - エンジニア。

もう少し早くできた、、はず。

ワーシャルフロイドの本質をきちんと理解してなかったが故に実装に時間がかかった。当然、Nの制約からワーシャルフロイドを直接使ったO(N³)はできないが、それでも、ワーシャルフロイドの考え方がベースになっている。

ワーシャルフロイドは、「ある地点を経由したときに距離が更新されるか」を総当たりで試すもの。この更新はアルゴリズムイントロダクションでは「緩和(relax)」と表現されている。

本問では、まずX地点とY地点の接続を考えずに2点間の距離を計算した後 X地点とY地点の接続（距離を1）し、そこから緩和をすればよい。

フロイドワーシャルの一番外側のループ、「どこを経由するか」を、XとYだけに限定すれば、実質定数倍のため、O(N²）として計算することができる。

#include <bits/stdc++.h>

#define rep(i, a, b) for (long long int i = (a); i < (b); i++)

using namespace std;
using ll = long long int;
using ld = long double;

auto p = [](auto s) {
    cout << s << endl;
};

int main() {
    int N, X, Y;
    cin >> N >> X >> Y;
    vector<vector<int>> d(N, vector<int>(N));
    rep(i, 0, N) {
        rep(j, 0, N) {
            d[i][j] = abs(i - j);
        }
    }
    X--;
    Y--;

    d[X][Y] = 1;
    d[Y][X] = 1;
    rep(i, 0, N) {
        rep(j, 0, N) {
            d[i][j] = min(d[i][j], d[i][X] + d[X][j]);
        }
    }
    rep(i, 0, N) {
        rep(j, 0, N) {
            d[i][j] = min(d[i][j], d[i][Y] + d[Y][j]);
        }
    }
    vector<int> ans(N);
    rep(i, 0, N) {
        rep(j, 0, N) {
            ans[d[i][j]] += 1;
        }
    }

    rep(k, 1, N) {
        p(ans[k] / 2);
    }
    return 0;
}

atcoder.jp

代わってこっちは500点問題とは思えないぐらいの簡単さ。

これぐらいの問題で考えるのは特定の方法で貪欲的に行けるか、つまり局所解が最適解を導くかをとても気にする。これがうまくいかないならば動的計画法に切り替える必要があるが今回は貪欲的に行ける。

P、Qの配列の中で上位X個、Y個だけに注目し、この中でRの中と交換を行ったときに一番利益が多くなるリンゴを考えると、これは、P、Qの最小のものと、Rの中の最大のものを交換すればよいことになる。（もちろん交換する価値があれば）

その次はP、Qの2番目に小さいものと、Rの2番目に大きいもの、と順々に見て行って交換していけばよい。

その途中で、Rのリンゴが、PQよりも利益が小さくなった場合、Rの残ったリンゴの利益はすべて今調べているものより等しいか小さく、 PQの残ったリンゴも、等しいか大きい。つまりこれ以後チェックする価値はない。


def solve(X, Y, P, Q, R):
    P = sorted(P, reverse=True)[:X]
    Q = sorted(Q, reverse=True)[:Y]
    R.sort(reverse=True)
    PQ = sorted(P + Q)
    i = 0
    while i < len(R) and i < len(PQ) and R[i] > PQ[i]:
        PQ[i], R[i] = R[i], PQ[i]
        i += 1
    return sum(PQ)


if __name__ == "__main__":
    X, Y, A, B, C = tuple(map(int, input().split(" ")))
    P = list(map(int, input().split(" ")))
    Q = list(map(int, input().split(" ")))
    R = list(map(int, input().split(" ")))
    print(solve(X, Y, P, Q, R))

よく考えたら、上位X個、上位Y個とRすべてをソート、でもよいのか。 500点問題ってなんだったっけ、、、