Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1860-79b5a991
この記事にトラックバックする(FC2ブログユーザー)

February 2011 Cook-Off 1問目 - Breaking Into Atoms (この記事を編集する[管理者用])

Source

codechef February 2011 Cook-Off 1問目
Problem Statement
codechef February 2011 Cook-Offの参加記録

問題概要

{1, 2, ..., n}の部分集合S[1], S[2], ..., S[m]が与えられる.(nは100以下,mは30以下)
1~nまでの数字を以下の条件を満たすようにk個のグループに分ける.
 任意のxに対して,各グループの要素はS[x]に全部含まれているか,S[x]には全部含まれていないかのどちらかでなければいけない
分けれるような最小のkを求める問題.

解法

AとBを同じグループにできて,BとCを同じグループにできるなら,AとCも同じグループにできる.
なので,同じグループにできるもの同士をgreedyにかためてあげれば良い.

C言語のスパゲッティなコード
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)

int main(){
  int i,j,k,l,m,n;
  int edge[120][120];
  int in[120][120];
  int ok[120], res;
  int size;

  scanf("%d",&size);
  while(size--){
    scanf("%d%d",&n,&m);
    rep(i,m) rep(j,n) in[i][j]=0;
    rep(i,m){
      scanf("%d",&k);
      while(k--){ scanf("%d",&j); in[i][j]=1; }
    }
    rep(i,n) rep(j,n) edge[i][j]=0;
    rep(i,n) rep(j,n){
      rep(k,m) if(in[k][i]!=in[k][j]) break;
      if(k==m) edge[i][j]=1;
    }
    rep(i,n) ok[i]=0; res=0;
    rep(i,n) if(!ok[i]){
      res++;
      rep(k,n) if(edge[i][k]) ok[k]=1;
    }
    printf("%d\n",res);
  }
  
  return 0;
}

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1860-79b5a991
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。