GCJ Round 1C Problem C. Fashion Police
問題
Dashboard - Round 1C 2016 - Google Code Jam
A 枚のジャケット, B 枚のパンツ, C 枚のシャツがある。これらを適当に組み合わせて, (a, b, c) というようなペアにして服を着る。
ところでこの世界にはファッション警察がいて, (a, b, c) というペアの服装で 2 日以上出かけると逮捕される。また, (a, b) の組, (b, c) の組, (c, a) の組を K+1 日以上かぶらせても逮捕される。この世界で逮捕されないように外出できる最大日数を求め, その際の服の着方を示せ。
解法
A*B*C の直方体を考えます。問題で課せられている条件は,
- (a, b, c) をかぶらせてはいけない
- 直方体のセル (a, b, c) は 1 回しか選べない
- (a, b) のようなペアを K+1 回以上選んではいけない
- x = a, y = b となるような直線上では K 個以下のセルしか選べない
です。2 つ目の条件から, 解の上界は A*B*K であるとわかります。で, 実際に A*B*K の解が存在します。それはどうするかというと, 各セル(a, b) に対して K 個のセルを選ばないといけないですが, これを (a+b+k)%C で選びます(k は 0 以上 K 未満の整数)。
二次元で考えると, (a+k)%C は各高さ c で K 個以下のセルしか選ばれません。これを二次元にするなら両方向に足せば良いので (a+b+k)%C という式が出てきます。
struct ABC { int a, b, c; ABC(); ABC(int a, int b, int c) : a(a), b(b), c(c) {} }; void solve() { int A, B, C, K; cin >> A >> B >> C >> K; K = min(C, K); vector<ABC> ans; for (int a = 0; a < A; a++) for (int b = 0; b < B; b++) { for (int k = 0; k < K; k++) { ans.emplace_back(a, b, (a+b+k)%C); } } cout << ans.size() << endl; for (ABC el : ans) cout << el.a+1 << " " << el.b+1 << " " << el.c+1 << endl; } int main() { cin.tie(0); ios::sync_with_stdio(false); int T; cin >> T; for (int t = 1; t <= T; t++) { cout << "Case #" << t << ": " ; solve(); } return 0; }