Google Code Jam Round1C C: Fashion Police

問題

https://code.google.com/codejam/contest/4314486/dashboard#s=p1
J・P・S個（)ずつのジャケットとズボンとシャツを持っている人がいる。
彼の住んでいる世の中は恐ろしい所で、同じ服装をすると逮捕されるらしい（雑な理解）
更に、世知辛い世の中なので、ジャケット・ズボン・シャツのうちの２つが同じ服装もK回までしか許されない。
最大何日この人は警察に捕まらず生きていけるかを答えよ。またその時の服装も出力せよ

考えたこと(Small)

SmallはSが3以下らしいので、
3*3*3の最大27通りの服装から、採用する服装の集合2^27を列挙してみて、題意を満たすかどうかのチェックをしてあげると良い。
ケース数が100あるので、最大計算時間はだが…間に合うかな？
とおもいつつ、半信半疑で実装。
実際自分のマシン環境で２分位かけたら答えを返してくれたのでセーフだった。
(但しfirst tryでは出力値を0-indexingにしてしまうと言う痛恨のミスにより時間切れ)

コード(Small)

int bitCount( int mask ){
   int cnt=0;
   while( mask != 0 ){
      cnt++;
      mask &= mask-1;
   }
   return cnt;
}

int main(){
  int n_case;
  cin >> n_case;
  for( int loop = 0 ; loop < n_case ; loop++ ){
   int J,P,S,K;
   cin >> J >> P >> S >> K;
   vector<pair<int,pair<int,int> > > c;
   for( int i =0 ; i < J; i++ ){
      for( int j = 0 ; j <P; j++ ){
         for( int k = 0 ; k < S; k++ ){
            c.push_back( make_pair(i, make_pair(j, k)) );
         }
      }
   }
   int size = c.size();
   int ansMask = 0;
   for( int mask=0; mask < (1<<size); mask++){
      if( bitCount(ansMask) > bitCount( mask ) ) continue;
      bool ok = true;
      map<int,int> ab;
      map<int,int> bc;
      map<int,int> ac;
      for( int i = 0 ; i < size; i++){
         if( mask&(1<<i)){
            int A=c[i].first;
            int B=c[i].second.first;
            int C=c[i].second.second;
            ab[A*10+B]++;
            bc[B*10+C]++;
            ac[A*10+C]++;
            if( ab[A*10+B] > K || bc[B*10+C]> K || ac[A*10+C] > K ){
               ok=false;
               break;
            }
         }
      }
      if( ok ) ansMask=mask;
   }
   cout << "Case #" << loop+1 << ": " <<bitCount(ansMask)<< endl;
   for( int i = 0 ; i < size; i++ ){
      if( ansMask&(1<<i) ){
            int A=c[i].first;
            int B=c[i].second.first;
            int C=c[i].second.second;
            cout <<A+1 <<" " << B+1 <<" " << C+1 << endl;
      }
   }
  }
  return 0;
}

考えたこと(Large)

さて34 pointのlargeである。
とりあえず、J,P,Sの大小関係が決まっているので、小さい方をまず固定して考えよう。
j,pの各組み合わせをK回ずつ使う(K>Sの場合はK=Sとみなすとする)として、sの割当を題意を満たすように上手く調整できないかと考える。
直感的に、
(j=1,p=1)の時にあわせるsは1～K,
(j=1,p=2)の時に合わせるsは2～K+1,
(j=1,p=3)の時に合わせるsは3～K+2,
(中略)
(j=2,p=1)の時に合わせるsは2～K+1,
(j=2,p=2)の時に合わせるsは3～K+2,
…
という風にj,pの値に従いsの使用開始位置をずらすようなコードを書いてみた。 (もちろんsの値がSより大きくなった場合はmodをとって調整する)

どうもうまい具合に重複せずに出力できているようである。
時間も迫っているのでこの実装で題意を満たさない時にエラーを吐くようなエラーコード付きでトライ。
エラーも吐かなかったので提出してみた。結果通った。正直通るとは思っていなかったのでびっくりした。

コード(Large)

int main(){
  int n_case;
  cin >> n_case;
  for( int loop = 0 ; loop < n_case ; loop++ ){
   int J,P,S,K;
   cin >> J >> P >> S >> K;
   cout << "Case #" << loop+1 << ": " <<J*P*min(S,K)<< endl;
   map<int,int> ab;
   map<int,int> bc;
   map<int,int> ca;
   for( int j=1; j<=J; j++){
      for( int p=1; p<=P; p++ ){
         for( int s=1; s<=min(K,S); s++ ){
            int a=j;
            int b=p;
            int c=(s+p+j-3)%S+1;
            cout << a << " " << b << " " << c << endl;
            ab[a*100+b]++;
            bc[b*100+c]++;
            ca[c*100+a]++;
            if(ab[a*100+b]>K || bc[b*100+c]>K || ca[c*100+a]>K ){
               cerr<< "ERROR in case "<<loop+1<<endl;
               return 0;
            }
         }
      }
   }
  }
  return 0;
}

考察

…で、なんでこれで通るのよ？と言う話について、
jを1として固定した時について改めて確認する (pを1と固定した場合でも同様に確認できるし、固定する値が1でなくとも同様に確認できる)

SがKより小さい場合、
(j=1,p=1)の時にあわせるsは1～S,
(j=1,p=2)の時に合わせるsは2～S,1
(j=1,p=3)の時に合わせるsは3～S,1,2
(中略)
(j=1,p=P)の時に合わせるsはP～S,1,2,...,P-1
...と、結局j=1のジャケットに対して1～Sの各シャツがP回ずつ使われることになる。
しかし、であるから、この割当は題意を満たす。

SがK以上の場合、
case 1: (j=1,p=1)の時にあわせるsは1～K,
case 2: (j=1,p=2)の時に合わせるsは2～K+1
case 3: (j=1,p=3)の時に合わせるsは3～K+2
(中略)
case K: (j=1,p=K)の時に合わせるsはK～2K,
(中略)
case P: (j=1,p=P)の時に合わせるsはP～K+P
シャツKはcase 1～case Kで必ず利用されていることから、
この割り当て方でK+1回利用されているシャツが存在すると仮定するならば、シャツKが真っ先にK+1回使われているはずである。
ところで、case K+1以降でKが利用されるためには、一周回ってKに到達する必要がある(上手く表現できていない気がするが…)から、
少なくともcase P でのsの割当の最大値であるK+PはS+Kより大きく無くてはならない。
しかし、題意によりP<=Sであるから、これは矛盾である。
よって背理法により、K+1回利用されているシャツは存在しない。

というわけで、直感ではあったけれど、1ずつずらす方法によって上手くK+1回使用される組合せを排除できていることがわかる。