Kyo_s_s Homepage

ABC328 参加記

競技プログラミング

ABC

96:30で7完、初の全完です！！ 196位で2324パフォでした。カンストパフォは逃してしまいましたがうれしい！ result

うれしかったので久しぶりに参加記を書きます。

E Modulo MST

問題: Modulo MST

$N$ 頂点 $M$ 辺の重み付き無向グラフと正整数 $K$ が与えられます。このグラフの全域木 $T$ に対して、コストを使った辺の重みの総和を $K$ で割ったあまりとします。全域木コストの最小値はいくつですか？

$2 \le N \le 8$
$N - 1 \le M \le \frac{N(N-1)}{2}$
$1 \le K \le 10^{15}$

あんまりよくわかりませんでした。今選んでいる頂点の集合をbitで管理し、選んでいない頂点への辺を採用していくDPを書いて無理やり通しました。

コンテスト終了後選ぶ辺を ${}_MC_{N-1}$ 個列挙する方法を知りました、なるほどです。冷静に考えると間に合いますね。また、 $M - N + 1$ 個の $0$ と $N - 1$ 個の $1$ を next_permutation に突っ込むテクも知りました。賢いです。

F Good Set Query

問題: Good Set Query

重み付きUnionFindを知っていますか？と問題文に書いてあるので窃盗しました。いずれライブラリにしたいです。

G Cut and Reorder

問題: Cut and Reorder

長さ $N$ の数列 $A, B$ があり、次の操作を好きな回数好きな順序で行うことで $A$ を $B$ に一致させたいです。

操作1: $A$ を分割し、好きな順に入れ替える。分割した個数を $X$ として、 $(X-1)C$ のコストがかかる。
操作2: 好きな $A$ の要素を $1$ つ選び、選んだ要素に好きな値 $k$ を足す。コストが $|k|$ かかる。

$A$ を $B$ に一致させるのに必要なコストの合計の最小値はいくつですか？

$1 \le N \le 22$
$1 \le C \le 10^{15}$

最初フローっぽい！と言いながら虚無の考察をしてしまいました。

まず、操作2は最後にそれぞれやればよいです。操作1について考えるのですが、この操作をするのは高々 $1$ 回でよいという大胆予想をします。この大胆予想により、 $\textrm{dp}[i][S] = A_1, \ldots, A_i$ を移動させ、移動後の集合が $S$ となるような移動にかかるコストの最小値というDPをしたくなります。遷移は配るDPで、いくつかをまとめて移動できるなら移動して更新のようにすればよいです。

ここで、 $i$ の情報は $S$ の立っているbitの個数と同じなので、この情報は持たなくてよいです。コンテスト中は特に意識せずこれをしたのですが、これをしないとMLEになるらしいです。

あとは操作1にかかるコストについてなのですが、これはDPの初期値を $(N - 1)C$ とし、まとめて $k$ 個の要素を移動したときにコストを $-(k-1)C$ すれば良いです。これを急いで実装し、ACすることができました！

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using vll = vector<ll>;
template<class T> bool chmin(T &a, const T &b) {if(b<a){ a=b; return 1;} return 0;}
#define INF (1LL << 60)
#define rep(i, n) for (ll i = 0; i < (n); i++)

int main() {

    ll N, C; cin >> N >> C;
    vll A(N), B(N);
    for (auto &a : A) cin >> a;
    for (auto &b : B) cin >> b;

    vll dp(1 << N, INF);
    dp[0] = (N - 1) * C;

    rep(msk, (1 << N)) {
        ll cost = dp[msk];
        ll i = __builtin_popcountll(msk);
        vll mov;
        for (ll w = 1; w + i <= N; w++) {
            mov.push_back(A[i + w - 1]);
            ll wmsk = (1 << w) - 1;
            for (ll j = 0; j + w <= N; j++) {
                if ((msk | (wmsk << j)) == (msk + (wmsk << j))) {
                    ll nmsk = msk | (wmsk << j);
                    ll ncost = cost;
                    for (int k = 0; k < w; k++) {
                        ncost += abs(mov[k] - B[j + k]);
                    }
                    ncost -= (w - 1) * C;
                    chmin(dp[nmsk], ncost);
                }
            }
        }
    }

    cout << dp[(1 << N) - 1] << endl;
}

おわりに

最近レートが大幅にマイナスになる回が多くて悲しかったのですが、挽回できてよかったです。このままレートを上げて黄色になりたいです！