ペアリングを頑張る問題として高難易度なすごく楽しい問題。
結構注意力がいる。割とやばいケースがある。
問題概要
下記のテトロミノの個数がそれぞれあたえられる。これらを回転は OK で反転は NG で組み合わせて の長方形を作りたい。作れる最大の を求めよ。
考えたこと
まず上図の「黄色」「紫」「ピンク」は使ってはいけなそう。ちゃんと示すなら例えば
- 黄色を使ったとき、長方形の中で黄色の左右の領域をそれぞれ埋めないといけないが、左右の領域はそれぞれ奇数マスなので無理
ということが言える。同じことは紫、ピンクにも言える。また、オレンジのやつは長方形の左右どちらかに寄せておけば、他に影響を与えない。よって
- 赤 (1 × 4)
- 緑
- 青
のやつをどう使うかだけが問題になる。少し考えると、(赤個数, 緑個数, 青個数) という表記を用いて、
- (1, 1, 1) で 2 × 6 が作れる
- (2, 0, 0) で 2 × 4 が作れる
- (0, 2, 0) で 2 × 4 が作れる
- (0, 0, 2) で 2 × 4 が作れる
ということがわかる。これらを上手く組合せて、なるべく余りが少なくなるようにしたい。
ヤバいコーナーケースと最適方法
ここで最初、() に対して
- として
- を 個作って
- 残ったやつは単独で 2 個ずつペアにする
という素朴な方法でよいのではと思ってしまった。が、それだとダメなケースとして (3, 4, 4) がある。このケースでそれをやると
- (1, 1, 1) × 3
を作って終わりになって 2 枚残ってしまうが
- (1, 1, 1) × 2
- (0, 2, 0) × 1
- (0, 0, 2) × 1
とすれば 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; } }