kmjp's blog

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

Google Code Jam 2017 Round 2 : A. Fresh Chocolate

今年もなんとか突破できた。
https://code.google.com/codejam/contest/5314486/dashboard#s=p0

問題

N組の訪問者がおり、それぞれG[i]人からなる。

1パックPピース入りのチョコレートがある。
訪問者に1ピースずつ与えよう。
その際、一旦パックの封を切ると、その中身を配り切るまで次の封を開けられない。
また、ある組の訪問者にチョコレートをあげ始めるとその組全員にいきわたるまで他の組にチョコレートを上げられない。

チョコレートを与える組の順を任意にできるとき、組で最初にチョコレートをもらう人が、開封直後のピースをもらうケースを最大化したい。
最大何組その条件を満たせるか。

解法

G[i]の具体的な数字は関係なく、結局mod Pした人数のみ関係する。
以下 f(x) := (G[i]%Pがxであるような組の数) とする。
あとはDPでもよいし地道に条件分岐させてもよい。

基本的に、できるだけ少ない組を複数合わせてPの倍数にするのがアプローチとなる。

  • P=2の場合
    • f(0)となる組にチョコをあげれば、f(0)組条件を満たせる。
    • あとはf(1)となる組にチョコをあげていくと、その中で奇数番目の組が条件を満たす。
  • P=3の場合
    • f(0)となる組にチョコをあげれば、f(0)組条件を満たせる。
    • あとはG[i]%P=1の組と2の組をペアにしていくと、2組に1組は条件を満たせる。
    • 残るはG[i]%P=1の組と2の組いずれかの種類だけなので、3組に1組は条件を満たせる。
  • P=4の場合
    • f(0)となる組にチョコをあげれば、f(0)組条件を満たせる。
    • G[i]%P=1の組と3の組をペアにしていくと、2組に1組は条件を満たせる。
    • また、G[i]%P=2の組2つで1組は条件を満たせる。
    • 残るf(2)は0か1である。1の場合、G[i]%P==1またはG[i]%P==3の組を2つ合わせれば、3組で1組は条件を満たせる。
    • 残る組のG[i]%Pは1種類しかないのでそれら同士を組み合わせよう。
int N,P;
int G[101];


void solve(int _loop) {
	int f,i,j,k,l,x,y;
	int num[5]={};
	
	cin>>N>>P;
	FOR(i,N) {
		cin>>x;
		num[x%P]++;
	}
	
	int ret=num[0];
	
	if(P==2) {
		ret += (num[1]+1)/2;
	}
	else if(P==3) {
		x = min(num[1],num[2]);
		ret += x;
		num[1]-=x;
		num[2]-=x;
		ret += (num[1]+2)/3;
		ret += (num[2]+2)/3;
	}
	else {
		x = min(num[1],num[3]);
		ret += x;
		num[1]-=x;
		num[3]-=x;
		ret += num[2]/2;
		num[2] %= 2;
		
		if(num[2]>0 && num[1]>=2) {
			ret++;
			num[1]-=2;
			num[2]=0;
		}
		if(num[2]>0 && num[3]>=2) {
			ret++;
			num[3]-=2;
			num[2]=0;
		}
		if(num[2]) {
			ret++;
		}
		else {
			ret += (num[1]+3)/4;
			ret += (num[3]+3)/4;
		}
	}
	
	
	
	_P("Case #%d: %d\n",_loop,ret);
}

まとめ

むしろ本番DPが思いつかず愚直に場合わけしてしまった。