https://beta.atcoder.jp/contests/agc022/tasks/agc022_c

問題概要

N要素の数列A, Bがある。以下の操作を繰り返してAをBに一致させることができるかを判定せよ。可能ならば操作の最小コストも求めよ。

操作: 正整数kをひとつ選び、Aの各要素に対してそれぞれその要素をkで割った余りに変えるかそのままにするかを選ぶ。この一連の操作のコストは2^k。

N <= 50 0 <= A, Bの各要素 <= 50

解法

まず重要な観察として、kに選ぶ数字は大きい数から降順で選んでいくと仮定してよい。例えば a < b として a, b の順で kを選んだ場合、aで余りを取った数は当然b未満になるため、bで余りをとることによる影響を及ぼせない。逆にb, aの順でkを選んだ場合には、bで余りを取った数はaで割ることによってさらに変化させられる可能性がある。ゆえにaを先に取る意味はない。さらにこのことからkで同じ数を2回以上選ぶ意味もないということがわかる。

以上より解の候補は 1～50 の数の集合として表すことができる。そのような集合のうち条件を満たすものの中で最小のコストを持つものが解となる。ある集合が条件を満たすかどうかはグラフの到達可能性問題として表すことができる。すなわち0～50のノードを持ったグラフに対して、「その集合に数xが含まれる場合ノードn → ノード(n%x) に辺を張る」というルールでグラフを構築すれば、ai -> biに到達可能かどうかで条件を満たすかどうかを判定できる。

またここでコストの計算方法より、x未満の数すべての集合で条件を満たすことができる場合、xを使うのは非最適である(2¹ + 2² + ... + 2^x-1 < 2^x)。ゆえに解の構築方法は以下のようになる。初め1～50のすべてを含む集合を持っておき、それを降順に見ていく。数xを見るときにはまずxを集合から外したうえで、その集合が条件を満たすかチェックする。仮にxを外しても条件を満たすのであれば上の事実よりxを使う必要はないので外したままにする。逆にxを外すと条件を満たさなくなる場合、xは必須であるので集合に戻す。これを繰り返して最終的に得られた集合が解である。

計算量はグラフの到達可能性の計算でO(N³), ひとつひとつの数を外してもいいかを見るとことでO(N)となりあわせてO(N⁴).

感想

最初がわからなかったから何をやってもだめ

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;

void main() {
    immutable int M = 51;
    auto N = readln.chomp.to!int;
    auto A = readln.split.map!(to!int);
    auto B = readln.split.map!(to!int);
    auto S = iota(1, M).array;

    bool ok() {
        auto D = new int[][](M, M);
        foreach (i; 0..M) foreach (j; 0..M) D[i][j] = i == j ? 1 : 1 << 29;
        foreach (i; 0..M) foreach (j; S) D[i][i%j] = 1;
        foreach (i; 0..M) foreach (j; 0..M) foreach (k; 0..M) D[j][k] = min(D[j][k], D[j][i] + D[i][k]);
        return N.iota.map!(i => D[A[i]][B[i]] < 1 << 29).all;
    }

    if (!ok) {
        writeln(-1);
        return;
    }
    
    ulong ans = 0;
    foreach (i; iota(50, 0, -1)) {
        S = S.remove!(a => a == i);
        if (!ok) {
            S ~= i;
            ans += 1UL << i;
        }
    }

    ans.writeln;
}

nebukuro09の日記

AtCoder Grand Contest 022: C - Remainder Game

問題概要

解法

感想

コード (D言語)