第三回アルゴリズム実技検定 O 問題: 輪投げ

問題概要

原文はこちら

atcoder.jp

棒が $N$ 本ある。これらのうち異なる $M$ 本に輪を投げ入れることを $3$ 回行う。投げ入れ方によって以下のように得点が定められる。

$i$ 回目に $j$ 番目の棒に輪を投げ入れたとき、 $A_{j} \left( B_j \right)^{i} \bmod R_{i}$ 点を得る。これらの合計を $X$ とする。
$j$ 番目の棒について、全 3 回のうち $i$ 回その棒に輪を投げ入れたとき、 $A_{j} \left( B_j \right)^{i}$ 点を失う。これらの合計を $Y$ とする。
総得点は $X - Y$ 点である。

得られる得点を最大化せよ。最大化した得点が負になることもある。

制約

$1 \leq M \leq N \leq 500$
$2 \leq A_{i}, B_{i} \leq 1000$
$2 \leq R_{i} \leq 10^{5}$

解説

おそらくどう考えても動的計画法のアプローチでは無理だと思います。他のアプローチを考えましょう。満たすべき制約がそれなりに多いので、フローを考えてみることにします。必要そうな頂点や辺を順に考えていきます。

それぞれの回において、ある $M$ 本を選んでそこに投げなければならないので、流量 $M$ だけ通過できるような頂点が $3$ つ欲しい
ある棒に関しては一度に複数回投げられないので、1. で用意した各頂点から流量 $1$ ずつ、棒を表す全頂点に張りたい
失点を表現できるように頂点を作りたい (後述)

符号を反転させて最小化問題として捉え、最小費用流で考えてみると、途中までは以下のようにグラフを作ると良くなります。辺に書いてある $(a, b)$ とは、流量が $a$ でコストが $b$ であることを表します。

※図における $A_i$ はすべて $A_j$ に置き換えて読んでください

f:id:tsutaj:20200606180236j:plain

さて、実際には失点を表現できるようにグラフを作らなければならないですが、後半のグラフはどう作ればよいでしょうか？ここで超重要なのが、 $B_{i} \geq 2$ であるので 失点は指数的に増える ということです。より具体的に言うと、 $x \lt y$ ならば $\left( B^{x} - B^{x-1} \right) \lt \left( B^{y} - B^{y-1} \right)$ であることが重要です。

$B$ の差分がどんどん広がっていくわけですので、以下のように辺を張ると、上の頂点から貪欲にいくつか使用したもののみが最小費用流の解となりえることがわかるので、このように張ると良いです。

f:id:tsutaj:20200606180249j:plain

ソースコード

// フロー 略

int main() {
    int N, M; cin >> N >> M;
    vector<ll> A(N), B(N);
    for(int i=0; i<N; i++) cin >> A[i];
    for(int i=0; i<N; i++) cin >> B[i];
    vector<ll> R(3);
    for(int i=0; i<3; i++) cin >> R[i];

    Flow<ll, ll> fl(2 + 3 + N + 3*N, LONGINF, LONGINF, LONGINF);
    int source = 3 + N + 3*N, sink = source + 1;
    for(int i=0; i<3; i++) {
        fl.add_edge(source, i, M, 0);
    }
    for(int r=0; r<3; r++) {
        for(int i=0; i<N; i++) {
            ll val = A[i];
            for(int j=0; j<=r; j++) (val *= B[i]) %= R[r];
            fl.add_edge(r, 3+i, 1, -val);
        }
    }
    for(int i=0; i<N; i++) {
        ll acc = 0;
        for(int r=0; r<3; r++) {
            ll val = A[i];
            for(int j=0; j<=r; j++) (val *= B[i]);
            fl.add_edge(3+i, 3+N+(3*i+r), 1, val - acc);
            acc += val - acc;
        }
    }
    for(int i=0; i<N; i++) {
        for(int r=0; r<3; r++) {
            fl.add_edge(3+N+(3*i+r), sink, 1, 0);
        }
    }

    ll ans = fl.mincost_flow(source, sink, 3*M);
    assert(ans != LONGINF);
    printf("%lld\n", -ans);
    return 0;
}