GCJ 2016 Round 1C C - Fashion Police

問題

Dashboard - Round 1C 2016 - Google Code Jam

問題概要

個のジャケットと個のパンツと個のシャツを持っている．これらの関係としてが成り立つ．

１日ごとに，その中から1つずつジャケットとパンツとシャツと選び，outfitとして着る．その日の夜に選択をするので，次の日もそれらの服を着ることは可能である．しかしながら，ファッション警察がいるので，また別の日に同じoutfitを着て出かけると，ファッション警察に捕まってしまう．また，2つの服の組(ジャケットとパンツ，パンツとシャツ，シャツとジャケット)をtwo-garment combinationと呼び，これらも回までしか同じ組を着ることは許されない．つまり，例としてその日のoutfitが(J1, P2, S3)だった時には(J1,P2),(P2,S3),(S3,J1)の組が1回カウントされるということである．

このような状況の時に，最大で何日過ごすことが出来るかを答え，更にその時の1日ごとのoutfitを答えよ(順番は問わない)．

• 
• 

アイデア

outfitの組み合わせとして考えられるのは通りある．これらをすべて試すには通りあるので，とてもじゃないが厳しい．まず，気づくべき点としての時には全ての組み合わせを着ることが可能であるということだ．以下，そうでない場合について考えていこう．

鳩の巣原理を頭の片隅において考えてみると，最大でもすごすことが出来る日数は2つずつの組み合わせの限界として，，のうちの最小値ということになる．そして，制約にある大小関係によって日であることがわかる．

さて，注意しておくべきことはoutfitの選び方次第ではもうこれ以上服装を追加できないけどそれが最大値にはならない場合が存在するということだ．つまり，ランダムに服を選ぶことを試しても局所的に良い点にたどり着いてしまい，本当の最大値を見つけることができないかもしれない．

実は，警察に捕まらないような通りのoutfitを貪欲に生成することができる．まず，ジャケットとパンツの組はそれぞれ回ずつしか採用できないので，とりあえずそれで個の候補を作れる．これらにどのようにシャツを組み合わせていけばよいかという視点で考えていこう．ジャケットとパンツの組に対して，番目のシャツを割り当てるという方法である．

これがどうしてうまくいくのかを確認しておこう．に対して，いまとを選んだ．には上限に大小関係があるので，，，が成り立つ．これより，と表すことが出来る．さて，ここではであり，この個のによっては1対1に対応している．これにより，の組に対して，回以上の選択が行われることはないことがわかったので，の組に対しても正当である．の組に対しても同じことが言える．

実装(C++)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
#define each(itr,c) for(__typeof(c.begin()) itr=c.begin(); itr!=c.end(); ++itr)
#define all(x) (x).begin(),(x).end()
#define mp make_pair
#define pb push_back
#define fi first
#define se second

int main()
{
    int T;
    cin >>T;
    rep(t,T)
    {
        int J,P,S,K;
        cin >>J >>P >>S >>K;

        if(S<=K)
        {
            printf("Case #%d: %d\n", t+1, J*P*S);
            rep(i,J)rep(j,P)rep(k,S) printf("%d %d %d\n", i+1, j+1, k+1);
        }
        else
        {
            int ans=J*P*K;
            printf("Case #%d: %d\n", t+1, ans);
            rep(i,J)rep(j,P)rep(k,K) printf("%d %d %d\n", i+1, j+1, (i+j+k)%S+1);
        }
    }
    return 0;
}