Google Code Jam 2016 Round 1C Fashion Police

問題概要
あなたはJ枚のジャケット、P枚のパンツ、S枚のシャツを持っている。（J <= P <= S）

以下の条件を満たすように、毎日服装を選ばなければならない。
同じ{ジャケット、パンツ、シャツ}の組み合わせを2回以上着ることはできない。
同じ{ジャケット、パンツ}の組み合わせをK回以上着ることはできない。
同じ{パンツ、シャツ}の組み合わせをK回以上着ることはできない。

同じ{シャツ、ジャケット}の組み合わせをK回以上着ることはできない。

最大で何日間上記の条件を満たしながら服装を選ぶことができるか？

日数と服装の選び方を出力せよ。

解法
K >= Sの場合は、J*P*Sのすべてのパターンを1回ずつ着ることができる。
以下では、K < Sの場合を考える。

鳩ノ巣原理により、求める日数をxとすると、
x <= J * P * K
x <= P * S * K

x <= S * J * K

が成り立つ。さらに、J <= P <= Sの条件から、

x <= J * P * K

となる。

もし、x = J * P * Kとなるような選び方ができれば、それが解となる。

ジャケットをi, パンツをjに固定したとき、シャツkを以下のように選んでみる。

k = (i + j + d) % S, 0 <= d < K.

K < Sより、上のkはすべて異なっている。

このとき、固定した{ジャケット、パンツ}ごとにK通りのパターンがあるので、全体でJ * P * Kパターンの選び方ができていることに注意。

この選び方が{ジャケット、シャツ}および{パンツ、シャツ}を固定したときにも制約に違反していないことが確認できれば、これが解となる。

ジャケットをi, シャツをkに固定した場合を考えてみる。

(i, j, k)が解に含まれるとき、

k = (i + j + d) % S, 0 <= d < K.

となるようなdが存在する。このとき

j = (k - i - d) % S.

となる。dはKパターンしかないため、同じ{ジャケット、シャツ}のパターンがK回以上着られることはない。

{パンツ、シャツ}を固定した場合も同様にK回以上着られることはない。

よってこれが解となる。

実装

using namespace std;

#define ALL(x) (x).begin(), (x).end()
#define EACH(itr,c) for(__typeof((c).begin()) itr=(c).begin(); itr!=(c).end(); itr++)  
#define FOR(i,b,e) for (int i=(int)(b); i<(int)(e); i++)
#define MP(x,y) make_pair(x,y)
#define REP(i,n) for(int i=0; i<(int)(n); i++)

int J,P,S,K;

void solve() {
  cin >> J >> P >> S >> K;

  if (K >= S) {
    cout << J*P*S << endl;
    REP (x, J) REP (y, P) REP (z, S) {
      cout << x+1 << " " << y+1 << " " << z+1 << endl;
    }
  } else {
    cout << J*P*K << endl;
    REP (x, J) REP (y, P) REP (z, K) {
      cout << x+1 << " " << y+1 << " " << (x+y+z)%S+1 << endl;
    }
  }
}

int main() {
    ios_base::sync_with_stdio(0);
    int T;
    cin >> T;
    REP (i, T) {
        cerr << "Case #" << i+1 << ": " << endl;
        cout << "Case #" << i+1 << ": ";
        solve();
    }
    return 0;
}