AtCoder ARC #106 : E - Medals

これは賢いな。
https://atcoder.jp/contests/arc106/tasks/arc106_e

問題

N人の従業員がいる。
各人、A[i]日間働いた後、A[i]日間休む、という周期で働く。
毎日、働いている人のうち（存在するなら）任意の1人にメダルを1枚渡すとする。
全員がメダルK枚以上獲得するのに必要な最小日数を求めよ。

解法

日数Dを二分探索することを考える。
すると、出社可能性のある人のパターン毎に、そのパターンを取る日数がO(D)で得られる。
ホールの結婚定理を考えると、あるm人が全員K枚のメダルを獲得するには、m人の誰かが出社している日がmK日以上あればよい。
あるパターンの出社日数がわかっているので、高速ゼータ変換を使うと、逆に「m人の誰も出社してない日」がわかり、それをDから引けば「m人の誰かが出社している日」がわかる。

Dを探索するごとに、パターン毎の日数の数え上げがO(D)、高速ゼータ変換がO(N*2^N)で済む。
同じくホールの結婚定理を考えると、日数の上限は高々2NKなので、全体でO*1で済む。

int N,K;
int A[101010];
int mask[4000001];
int sum[1<<18];

int ok(int v) {
	if(v<=0) return 0;
	ZERO(sum);
	int i,x;
	FOR(i,v) sum[mask[i]]++;
	FOR(i,N) FOR(x,1<<N) if(x&(1<<i)) sum[x^(1<<i)]+=sum[x];
	FOR(i,1<<N) {
		int need=(N-__builtin_popcount(i))*K;
		if(v-sum[i^((1<<N)-1)]<need) return 0;
	}
	return 1;
	
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	cin>>N>>K;
	FOR(i,N) {
		cin>>A[i];
		FOR(j,4000000) if(j%(2*A[i])>=A[i]) mask[j]|=1<<i;
	}
	
	ll ret=2*N*K;
	for(i=30;i>=0;i--) if(ok(ret-(1<<i))) ret-=1<<i;
	cout<<ret<<endl;
	
}

まとめ

ホールの結婚定理、自信を持って使うの難しい。

*1:NK+N*2^N)*log(NK