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

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

AtCoder AGC 008 C - Tetromino Tiling (600 点)

ペアリングを頑張る問題として高難易度なすごく楽しい問題。
結構注意力がいる。割とやばいケースがある。

問題へのリンク

問題概要

下記のテトロミノの個数がそれぞれあたえられる。これらを回転は OK で反転は NG で組み合わせて  2 \times 2K の長方形を作りたい。作れる最大の  K を求めよ。

f:id:drken1215:20190516015538p:plain

考えたこと

まず上図の「黄色」「紫」「ピンク」は使ってはいけなそう。ちゃんと示すなら例えば

  • 黄色を使ったとき、長方形の中で黄色の左右の領域をそれぞれ埋めないといけないが、左右の領域はそれぞれ奇数マスなので無理

ということが言える。同じことは紫、ピンクにも言える。また、オレンジのやつは長方形の左右どちらかに寄せておけば、他に影響を与えない。よって

  • 赤 (1 × 4)

のやつをどう使うかだけが問題になる。少し考えると、(赤個数, 緑個数, 青個数) という表記を用いて、

  • (1, 1, 1) で 2 × 6 が作れる
  • (2, 0, 0) で 2 × 4 が作れる
  • (0, 2, 0) で 2 × 4 が作れる
  • (0, 0, 2) で 2 × 4 が作れる

ということがわかる。これらを上手く組合せて、なるべく余りが少なくなるようにしたい。

ヤバいコーナーケースと最適方法

ここで最初、( a, b, c) に対して

  •  m = \min(a, b, c) として
  •  (1, 1, 1) m 個作って
  • 残ったやつは単独で 2 個ずつペアにする

という素朴な方法でよいのではと思ってしまった。が、それだとダメなケースとして (3, 4, 4) がある。このケースでそれをやると

  • (1, 1, 1) × 3

を作って終わりになって 2 枚残ってしまうが

  • (1, 1, 1) × 2
  • (0, 2, 0) × 1
  • (0, 0, 2) × 1

とすれば 1 枚余らすだけで済む。でも、 (1, 1, 1) m 組作る方法に対して、 (1, 1, 1) m-2 組だけにしても意味がない。なぜなら「赤」「緑」「青」の残り数のパリティが変わらないので、結局余る枚数が同じになる。よって

  •  m = \min(a, b, c)
  •  m = \min(a, b, c) - 1 (それが負になる場合は不要)

の両方を試して良い方をとれば OK。

#include <iostream>
using namespace std;

int main() {
    long long a, b, c, d, e, f, g;
    while (cin >> a >> b >> c >> d >> e >> f >> g) {
        long long res = 0;
        long long m = min(a, min(d, e));
        for (long long i = max(m-2, 0LL); i <= m; ++i) {
            long long tmp = i * 3;
            long long na = a - i, nd = d - i, ne = e - i;
            tmp += na/2 * 2;
            tmp += nd/2 * 2;
            tmp += ne/2 * 2;
            res = max(res, tmp);
        }
        cout << res + b << endl;
    }
}