第15回アルゴリズム実技検定 (PAST 015)

Mon, Apr 7, 2025

E - 合計得点

bit 全探索で良いが $N$ 個から $K$ 個選ぶ方法でも解ける

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, k;
    cin >> n >> k;
    vll a(n);
    rep(i, n) cin >> a[i];

    vint v;

    auto dfs = [&](auto dfs, int used) -> void {
        if (__builtin_popcount(used) == k) {
            v.push_back(used);
            return;
        }

        int id = -1;
        rep(i, n) {
            if ((used >> i) & 1)
                id = i;
        }
        rep2(i, id + 1, n) {
            dfs(dfs, used | (1 << i));
        }
    };

    dfs(dfs, 0);

    ll ans = 0;
    for (int used : v) {
        rep(i, n) {
            if ((used >> i) & 1)
                ans += a[i];
        }
    }
    cout << ans << endl;
}

F - 番号付け

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vint A(N);
    rep(i, N) cin >> A[i];

    map<int, vint> mp;
    rep(i, N) {
        mp[A[i]].push_back(i);
    }

    int cnt = 1;
    vint ans(N);
    for (auto it = mp.begin(); it != mp.end(); it++) {
        auto [_, ids] = *it;
        for (int id : ids) {
            ans[id] = cnt++;
        }
    }
    print(ans);
}

G - N-SAT

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, M;
    cin >> N >> M;
    vvint as(M), bs(M);
    rep(i, M) {
        int k;
        cin >> k;
        rep(j, k) {
            int a, b;
            cin >> a >> b;
            a--;
            as[i].push_back(a);
            bs[i].push_back(b);
        }
    }

    rep(t, 1 << N) {
        vint xs;
        rep(i, N) {
            xs.push_back((t >> i) & 1);
        }

        int cnt = 0;
        rep(i, M) {
            int ok = 0;
            int ki = as[i].size();
            rep(j, ki) {
                if (xs[as[i][j]] == bs[i][j])
                    ok = 1;
            }
            if (ok)
                cnt++;
        }

        if (cnt == M) {
            yesno(true);
            return;
        }
    }
    yesno(false);
}

H - 和で表現

解説 AC。愚直解で AC 取れてしまったが解説読んだら二分探索だった。

愚直解

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N;
    cin >> N;

    auto sum = [](ll n) -> ll {
        return n * (n + 1) / 2;
    };

    int i = 0;
    while (sum(i) <= N)
        i++;
    cout << i - 1 << endl;
}

二分探索

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N;
    cin >> N;

    auto sum = [](ll n) -> ll {
        return n * (n + 1) / 2;
    };

    ll ac = 0, wa = (ll)2e9 + 7;
    while (wa - ac > 1) {
        ll wj = (wa + ac) / 2;
        if (sum(wj) <= N)
            ac = wj;
        else
            wa = wj;
    }
    cout << ac << endl;
}

I - 最大公約数の最大値

$A_i$ の約数を列挙して、出現頻度が $K$ 以上のもののうち最大の数が答え

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    cin >> N >> K;
    vint A(N);
    rep(i, N) cin >> A[i];

    int mx = (int)1e6 + 5;
    vvint divs(mx);
    rep2(i, 1, mx) {
        for (int j = i; j < mx; j += i) {
            divs[j].push_back(i);
        }
    }

    vint v(mx);
    for (int a : A) {
        for (int d : divs[a]) {
            v[d]++;
        }
    }

    int ans = 1;
    rep(i, mx) {
        if (v[i] >= K)
            ans = i;
    }
    cout << ans << endl;
}

J - 忍者

最終的なダメージを最小にする問題。手裏剣を投げることによって1回あたりのダメージをどれだけ減らせるかを考える。

手裏剣を使わなかった場合、魔物 $i$ から攻撃される回数を $c_i$ とすると、

\begin{equation*} c_i = \begin{cases} b_i - 1 & (x_i = 0) \\ b_i & (x_i = 1) \end{cases} \end{equation*} である。

$x_i = 0$ の魔物に対して手裏剣を使っても単に攻撃されるか回数が手裏剣を投げた回数分減るだけだが、 $x_i = 1$ の魔物に対して手裏剣を1回使うと、手裏剣による体力減 1 と、地上に降りたことによって先制攻撃ができる分で2回分の攻撃を減らすことができる。これより、手裏剣を投げることによって減少するダメージ量が大きい魔物から優先的に手裏剣で攻撃する。

struct Point {
    // 攻撃力、攻撃される回数、空中にいるかどうか
    ll power, cnt, flag;
};

bool operator<(const Point& a, const Point& b) {
    ll aw = a.power, bw = b.power;
    if (a.flag == 1 && a.cnt > 1) {
        aw *= 2;
    }
    if (b.flag == 1 && b.cnt > 1) {
        bw *= 2;
    }

    return aw < bw;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N, M;
    cin >> N >> M;
    vll a(N), b(N), x(N);
    rep(i, N) {
        cin >> a[i] >> b[i] >> x[i];
    }

    priority_queue<Point> pq;
    rep(i, N) {
        if (x[i] == 1)
            pq.push({a[i], b[i], x[i]});
        else if (b[i] - 1 > 0)
            pq.push({a[i], b[i] - 1, x[i]});
    }

    while (pq.size() && M) {
        auto [p, h, f] = pq.top();
        pq.pop();
        if (f == 1) {
            M--;
            f = 0;
            h -= 2;
            if (h > 0)
                pq.push({p, h, f});
        } else {
            ll m = min(M, h);
            h -= m;
            M -= m;
            if (h > 0)
                pq.push({p, h, f});
        }
    }

    ll ans = 0;
    while (pq.size()) {
        auto [p, h, _] = pq.top();
        pq.pop();
        ans += p * h;
    }
    cout << ans << endl;
}

K - 入れ替えてソート

大きい数から右端に移動させることが最適だと思ったが別にそのような制約はないっぽい。

これから移動させる数より右側にその数よりも小さい数が何個あるかということと、それらの和を高速で求められれば良い。

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N;
    cin >> N;
    vll P(N);
    rep(i, N) {
        cin >> P[i];
    }

    fenwick_tree<ll> cnts(N + 1), fw(N + 1);
    vint ids(N + 1);
    rep(i, N) {
        cnts.add(i + 1, 1);
        fw.add(i + 1, P[i]);
        ids[P[i]] = i + 1;
    }

    ll ans = 0;
    for (ll i = N; i >= 1; i--) {
        ll cnt = cnts.sum(ids[i] + 1, N + 1);
        cnts.add(ids[i], -1);
        fw.add(ids[i], -i);
        if (cnt == 0)
            continue;
        ans += cnt * i;
        ans += fw.sum(ids[i] + 1, N + 1);
    }
    cout << ans << endl;
}

L - ビット行列

列に対して操作を複数回行う必要はない。なぜならそれらの操作で選んだ全ての数字の XOR を1回作用させるのと同じだから。行についても同様。

$i$ 行目に $X_i$ を作用させ、 $j$ 列目に $Y_j$ を作用させるとする。

矛盾がないとき $B_{ij} = A_{ij} \oplus X_i \oplus Y_j$ となっている。

これより全ての $i,j,k$ に対して以下の等式が矛盾なければ良い \begin{align*} Y_i \oplus Y_j = A_{ki} \oplus A_{kj} \oplus B_{ki} \oplus B_{kj} \end{align*}

ここで $B_{ij} = -1$ のときは判定をスキップする

計算量は $O(\max(H,W)^3)$

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll H, W;
    cin >> H >> W;
    vvll A(H, vll(W)), B(H, vll(W));
    rep(i, H) rep(j, W) cin >> A[i][j];
    rep(i, H) rep(j, W) cin >> B[i][j];

    vvll X(H, vll(H, -1)), Y(W, vll(W, -1));
    rep(k, H) {
        rep(i, W) {
            rep2(j, i + 1, W) {
                if (B[k][i] == -1 || B[k][j] == -1)
                    continue;
                ll tmp = A[k][i] ^ A[k][j] ^ B[k][i] ^ B[k][j];
                if (Y[i][j] != -1 && Y[i][j] != tmp) {
                    yesno(false);
                    return;
                }
                Y[i][j] = A[k][i] ^ A[k][j] ^ B[k][i] ^ B[k][j];
            }
        }
    }
    yesno(true);
}

M - 点の距離

partition problem の問題である。

この PAST が開催されたときの環境では $O(N^2 \max(d_i))$ の計算量だと TLE したのかもしれないが、今の環境では普通にこれでも通った。

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vll D(N - 1);
    rep(i, N - 1) cin >> D[i];

    // d を2つのグループに分けて、それぞれのグループの和の差を最小化したい
    ll sum = accumulate(all(D), 0ll);
    ll half = sum / 2;

    vll dp(half + 1);
    dp[0] = 1;
    for (ll d : D) {
        vll tmp = dp;
        rep(i, half + 1) {
            if (dp[i] && i + d <= half)
                tmp[i + d] = 1;
        }
        swap(tmp, dp);
    }

    ll ans = sum;
    rep(i, half + 1) {
        if (dp[i]) {
            chmin(ans, abs(sum - i * 2));
        }
    }
    cout << ans << endl;
}

効率的なアルゴリズムがあるわけではなく bitset を使って定数倍高速化しましょうという問題だったらしい。

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int N;
    cin >> N;
    vll D(N - 1);
    rep(i, N - 1) cin >> D[i];

    // d を2つのグループに分けて、それぞれのグループの和の差を最小化したい
    bitset<4000005> bs;
    int offset = 2000001;
    bs.set(offset);

    for (ll d : D) {
        bs = (bs << d) | (bs >> d);
    }

    ll ans = INF;
    rep(i, 4000005) {
        if (bs.test(i))
            chmin(ans, abs(i - offset));
    }
    cout << ans << endl;
}

第15回 アルゴリズム実技検定 (PAST 015)

Table of Contents