Codeforces Round #511 (Div. 2)

ABC早解きで123位でした。DはHack中にミスに気づいて厳しい気持ちになってました

Div. 1との同時開催だったので普段より強い(早い?)人が少なくて、A, Bを解き終えた時点でほぼトップだったのでびっくりしてました

C - Enlarge GCD

まず制限時間1秒を見て驚く。さすがに、 O(n\log^2 n)より速くなる気がしないので、愚直に実装することにする。

アルゴリズム自体はすぐに思いついた。すべてのgcdで各項を割った状態で考える。 このとき、各素数2, 3, 5, ...について、その倍数がいくつあるかをカウントする。一番倍数の数が多かった素数の倍数を残すように残りの数を削除する。

最悪ケースを考えると、どうせ各素数について調べる必要がありそうだから、事前に1.5e7以下の素数を列挙して、それらすべてについて調べるというので良さそう。

念のためcin.tie(0); ios::sync_with_stdio(0);しておきましたが、実行時間を見るに本当にしておいてよかった気がします。

以下コード。エラトステネスの篩部分(つまりis_primeprimesの構築)は省略してます。

constexpr int MAX_A = 15000000;
int is_prime[MAX_A];
vi primes;
int a[MAX_A + 1];

i64 gcd(i64 a, i64 b) {
    return b ? gcd(b, a % b) : a;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(0);
    int n;
    cin >> n;
    vi as(n);
    i64 g;
    for (int i = 0; i < n; i++) {
        cin >> as[i];
        if (i == 0) {
            g = as[i];
        } else {
            g = gcd(g, as[i]);
        }
    }
    
    for (int i = 0; i < n; i++) {
        as[i] /= g;
    }
    
    int max_c = -1;
    for (int i: as) {
        a[i]++;
    }
    for (int i = 0; i < primes.size(); i++) {
        int p = primes[i];
        int c = 0;
        for (int j = 1; p * j <= MAX_A; j++) {
            if (a[p * j]) {
                c += a[p * j];
            }
        }
        max_c = max(max_c, c);
    }
    int ans = n - max_c;
    cout << (ans == n ? -1 : ans) << endl;
}

D - Little C Loves 3 II

Cを解き終えた時点で正解者が1人だったので、最悪解けなくてもいいかなぁ〜と思っていたのですが、WAを生成しているうちに100人とかまで増えてきてすごく焦りました。

まず最初、3xmを手で試しました。このとき、頭がついていなくて、3x4のときに敷き詰められないと結論づけてしまったことがすごくあとに響きました。 二部グラフの最大マッチングのライブラリでも使って検証するべきでした、、、

n, mが4以上の偶数のときに敷き詰められることはわりと序盤で気づけたのですが、問題は奇数x偶数のときでした。2x5が敷き詰められることや3x4が敷き詰められることに気づいた頃には終了10分前ぐらいになっていて、pretestを通すことはできましたが、細かいミスで落ちてしまいました、、、

証明

と、まあコンテスト中の試行錯誤はともかく、記事的に重要なのはおそらく証明だと思うので、証明を載せておきます。

以下、 n \le mとします。

 n = 1のとき

貪欲に敷き詰めるしかないです。すなわち、abcabcdefdef...のように敷き詰めます。空きマスは 1,2,3,2,1,0,1,2,3,2,1,0,1,\ldotsのように変化していきます。

 nまたは mが6の倍数のとき

1x6をabcabcのように敷き詰められるため空きマスを0にすることができます。

 n = 2のとき

 m \le 2のときは何も置けません。

 m = 3のとき、試すと空きマスを2つまで少なくすることができることがわかります。

 m = 4のとき

abcd
cdab

のように置くことで、空きマスを0にすることができます。

 m = 5のとき

abceb
deadc

のように置くことで、空きマスを0にすることができます。

 m = 6のとき6の倍数なので空きマスをなくせます。

 m = 7のとき、これが無理になることは手でめっちゃ試すとわかります。雑ですみません。

 m \ge 8のとき、8以上の整数は、これまでに空きマスを0にすることができるような mをいくつか選んで足すと作れるため、空きマスを0にすることができます。

以下は n \ge 3の場合です

 n, mがどちらも偶数の場合

2x(4以上の偶数)が可能だったことにより空きマスを0にすることができます。

 nが奇数、 mが偶数の場合

いま n \ge 3より m \ge 4です。3x4を以下のように構成できることがこの場合の証明ですごく重要です。2x4が構成できることより、nx4がすべて構成できることがわかります。さらに、nx6が構成可能なことと、8以上の偶数が4の倍数と6の倍数を足し合わせて作れることから、nxmすべてが可能なことがわかります。

acdb
ebaf
cfed

 nが偶数、 mが奇数の場合

 n = 2の場合は調べたので、 n \ge 4です。そうすると m \ge 5です。これは nが奇数、 mが偶数の場合の結果を使うと、同様にすべて可能であることがわかります。

 nが奇数、 mが奇数の場合

いよいよ最後です。 これは正直あまりきれいな証明が思いつきませんでした。

 n = 3の場合に

abd
d c
cab
***bc
*a* a
***cb
*****bc
***a* a
*****cb

のように空きマスを1にするように構成していけることがわかります(図では、それまでに敷き詰められた部分を*で表しています)。

 n \ge 5のとき、2xmで敷き詰められるようなm対して、nxmは、3xmと(n - 3)xmを組み合わせることで、空きマスを1にできることがわかります。

さて、これを満たさないmは今の条件下では m = 7だけです。しかし、4xnが構成可能であることは証明済みですから、nx7をnx4とnx3に分解することで、空きマスを1にすることが証明できます。

さて、これですべての場合が証明できました。いや〜つかれた。

以下実装

int main() {
    i64 n, m;
    cin >> n >> m;
    if (n > m) {
        swap(n, m);
    }
    
    i64 ans;
    if (n == 1) {
        int rem[] = {1,2,3,2,1,0};
        ans = n * m - rem[(m - 1) % 6];
    } else if (n == 2) {
        if (m <= 2) {
            ans = 0;
        } else if (m == 3 || m == 7) {
            ans = n * m - 2;
        } else {
            ans = n * m;
        }
    } else if (n % 2 && m % 2) {
        ans = n * m - 1;
    } else {
        ans = n * m;
    }
    cout << ans << endl;
}

感想

小さいケースは手でやるより最大マッチングのライブラリを使うべきですね、、、、、、、、ほんとに