kmjp's blog

競技プログラミング参加記です

Google Code Jam 2016 Round1C : C. Fashion Police

Editorialがわかりやすくてよい。コードもすこぶる短いね。
https://code.google.com/codejam/contest/4314486/dashboard#s=p2&a=0

問題

J個のジャケットとP個のズボンとS個のシャツがある。(J≦P≦S)
毎日ジャケット・ズボン・シャツを1つずつ着る。
その際以下の条件を満たすように組み合わせを考えなければならない。

  • (ジャケット, ズボン, シャツ)のトリオで同じものを2度着てはいけない。
  • (ジャケット, ズボン) (ジャケット, シャツ) (ズボン, シャツ)それぞれの対に対し、同じ対をK回を超えて着てはいけない。

最長何日分の着回しができるか、着回しの例を示せ。

解法

同じ対を着ないよう、ジャケットを1周分着るごとに、対応するズボン・シャツを少しずつずらしていくのが基本戦略となる。
問題文の条件より、最長着回し数はmin(J*P*S,J*P*K)であることは明らかである。
以下、うまくJ*P*K通りの着こなしを考えよう。

Editorialの図がわかりやすかったので紹介。
1番のジャケットを固定した場合、ズボン・シャツは最大K回までしか着られないので、縦軸をズボン番号、横軸をシャツ番号として、以下のように組み合わせを表せる。
(P=3,S=4,K=2の場合で、*が着る組み合わせを示す)

**..
.**.
..**

各行ではK個の*が並び、行ごとに1つ*の始まりが右にずれる。

ジャケット番号が増えた場合、同様に各行の*の始まりがずれると考える。
あとは各ジャケット番号に対し、*がついたズボン・シャツの番号を答えればよい。

int A,B,C,K;
int mat[11][11];
void solve(int _loop) {
	int f,i,j,k,l,x,y,z;
	
	cin>>A>>B>>C>>K;
	ZERO(mat);
	int ret=0;
	FOR(y,B) {
		FOR(x,K) mat[y][(y+x)%C]=1;
		ret += count(mat[y],mat[y]+C,1);
	}
	
	
	_P("Case #%d: %d\n",_loop,ret*A);
	FOR(z,A) FOR(y,B) FOR(x,C) if(mat[y][x]) _P("%d %d %d\n",z+1,y+1,(x+z)%C+1);
}

まとめ

50着とか100着とか言わないあたり、コーダー勢の服装に対する現実に即している…?

広告を非表示にする