読者です 読者をやめる 読者になる 読者になる

裏紙

ほぼ競プロ、たまに日記

GCJ 2016 Round 1C C - Fashion Police

問題

Dashboard - Round 1C 2016 - Google Code Jam

問題概要

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

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

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

  •  1 \le J \le P \le S \le 10
  •  1 \le K \le 10

イデア

outfitの組み合わせとして考えられるのはO = J * P * S通りある.これらをすべて試すには2^O通りあるので,とてもじゃないが厳しい.まず,気づくべき点としてS \le Kの時には全ての組み合わせを着ることが可能であるということだ.以下,そうでない場合について考えていこう.

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

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

実は,警察に捕まらないようなJ * P * K通りのoutfitを貪欲に生成することができる.まず,ジャケットとパンツの組はそれぞれK回ずつしか採用できないので,とりあえずそれでJ * P * K個の候補を作れる.これらにどのようにシャツを組み合わせていけばよいかという視点で考えていこう.ジャケットjとパンツpの組に対して,(j+p+d) \% S (0 \le d \le K-1)番目のシャツを割り当てるという方法である.

これがどうしてうまくいくのかを確認しておこう.(j,p)に対して,いまs=(j+p+d) \% Ssを選んだ.j,p,sには上限J,P,Sに大小関係があるので,j \% S = jp \% S = ps \% S = sが成り立つ.これより,p = (s-j-d) \% Sと表すことが出来る.さて,ここでd0 \le d \le K-1であり,このK個のdによってpは1対1に対応している.これにより,(j,s)の組に対して,K回以上の選択が行われることはないことがわかったので,(j,s)の組に対しても正当である.(p,s)の組に対しても同じことが言える.

実装(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;
}