なんとか解けてよかった

問題概要

$m$ × $n$ の二次元グリッド盤面が与えられる。

空いているマスを 2 つ選んで、その 2 つに駒を置く。ただしその 2 マス間のマンハッタン距離が 3 でなければならない

という操作を繰り返し行う。こうして出来上がる盤面に置かれた駒数の最大数を求めよ。

制約

$1 \le m, n \le 10^{9}$

考えたこと

サンプル弱い。かなり怖い。
少し実験してみる。

1 × n と 2 × n は別個に検討する必要がありそうだが、(3 以上) × (3 以上) の場合をまず示してしまうことにする。

4 以上の偶数 × 4 以上の偶数はすべてできそう
3 以上の奇数 × 3 以上の奇数はすべて 1 マスだけ空けて埋められそう

この直感をちゃんと証明したい。実は 3 以上 × 3 以上の盤面にはナイトツアーが存在するので、それをぶった切ることで示せることを後に satanic さんに教わった。

----- 以後はコンテスト中に考えたこと -----

1 マス除いて覆えることを「実質覆い尽くせる」と呼ぶことにする。自分が考えたのは

3 × 4 の盤面は覆い尽くせる
3 × 6 の盤面は覆い尽くせる

これらのことから、3 × (4 以上の偶数) は覆い尽くせることがわかる (例えば 3 × 10 は、3 × 4 と 3 × 6 をそれぞれ覆う)

これに加えて

3 × 3 の盤面は実質覆い尽くせる

これらのことから、3 × (3 以上の奇数) は実質覆い尽くせることがわかる (3 × 3 を残して残りは全部覆う、3 × 5 は別途構成した)。

同様にして、

4 × (3 以上) はすべて覆い尽くせることもわかる (4 × 3、4 × 4、4 × 5 が OK のため)。
6 × (3 以上) はすべて覆い尽くせることもわかる (4 × 3、4 × 4、4 × 5 が OK のため)。

このことから

(4 以上の偶数) × (3 以上) はすべて覆い尽くすことができる

これで $m, n \ge 3$ については、 $m, n$ のどちらかが偶数ならすべて覆い尽くせることに決着が着いた。

残るは (3 以上の奇数) × (3 以上の奇数) の場合。 $m \ge 7$ の場合には、(4 以上の偶数) × (3 以上) がすべて覆い尽くせることから、「3 × (3 以上の奇数)」の場合に帰着して、実質覆い尽くせることがわかる。さらに 5 × (3 以上の奇数) についても個別にちゃんと示せる。

以上のことから

$m, n \ge 3$ の場合には

$m, n$ のどちらかが偶数ならすべて覆い尽くせる
$m, n$ のどちらも奇数なら、1 マスを除いてすべて覆い尽くせる

ということがわかった。

残りは、1 × n、2 × n である。1 × n は丁寧にやる。2 × n が少し難しい。

2 × (4 以上の偶数) はできる
2 × 5 はできる

これらのことから、2 × (8 以上) はすべてできることがわかる。怖いのが

2 × 7

のケースで、できそうもなかったが確信が持てなかったので、二部マッチングして確かめた (グリッドを市松模様に塗ると、駒をどう置いても「片方が白でもう片方が黒」という風にしか置けないため、二部マッチングで解ける)

が、てんぷらさんが賢く示していた:

2*7がダメなことは、(1,1)(2,2)(6,2)(7,1)から行けるマスが合わせて3個しかないことからわかる
— てんぷら (@tempura_cpp) 2018年9月21日

#include <iostream>
using namespace std;

long long solve(long long m, long long n) {
    if (m > n) swap(m, n);
    if (m == 1) {
        if (n <= 3) return 0;
        if (n % 6 == 0) return m*n;
        else if (n % 6 == 1) return m*n-1;
        else if (n % 6 == 2) return m*n-2;
        else if (n % 6 == 3) return m*n-3;
        else if (n % 6 == 4) return m*n-2;
        else return m*n-1;
    }
    else if (m == 2) {
        if (n <= 2) return 0;
        else if (n <= 3) return m*n-2;
        else if (n <= 6) return m*n;
        else if (n <= 7) return m*n-2;
        else return m*n;
    }
    else {
        if (m % 2 == 1 && n % 2 == 1) return m*n-1;
        else return m*n;
    }
    return 0;
}

int main() {
    long long m, n; cin >> m >> n;
    cout << solve(m, n) << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

Codeforces Round #511 (Div. 1) B. Little C Loves 3 II (R2200)

問題概要

制約

考えたこと