kmjp's blog

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

8VC Venture Cup 2017 - Elimination Round : F. PolandBall and Gifts

これは勉強になった。
http://codeforces.com/contest/755/problem/F

問題

N人の人がプレゼント交換会を行い。
i番の人はP[i]の人にプレゼントを渡すことになっている。

以下の条件を満たす場合、i番の人はプレゼントを受け取れる。

  • 自分自身はプレゼントを持ってきている。
  • 自分に渡すはずの人x(P[x]=i)がプレゼントを持ってきている。

N人中K人がプレゼントを持ってきていない場合、プレゼントを受け取れない人の最大値最小値を求めよ。

解法

i→P[i]の関係をグラフ(無向でも有向でも以後の処理にはほとんど関係ない)であらわすと、N頂点はいくつかの閉路に分割される。

まず受け取れない人の最大値を求めよう。
条件より、閉路内において1人飛ばしで忘れた人を選択すると、1人がプレゼントを忘れるのに対し2人プレゼントを受け取れない。
ただし閉路長が奇数の場合は、最後だけ1人プレゼントを忘れても1人しか受け取れない人が増えない。
よって可能な限りプレゼント忘れ1つで2人プレゼントを受け取れなくなるように忘れた人を選択し、余ったプレゼント忘れがあればそこだけ1人だけ受け取れない人が増える手を取ろう。

次に最小値を求める。
N頂点を分割した閉路長のmultiset Sを考える。Sの部分集合の総和でKとなるものがあれば、そのような閉路の人全員がプレゼントを忘れることで、受け取れない人がK人となる。
そうでない場合、1人余分に受け取れない人が生じて(K+1)人となる。
あとは、Sの部分集合でKとなるものがあるかどうかを求める。

愚直にDPするとO(NK)となる。このDPは真偽値を問うものなのでbitsetで高速化できるが、それでも間に合わずもう一工夫がいる。
そこで以下のテクを使う。
i人からなる閉路の数が少ない(たとえば100以下)の場合、bitsetで愚直に行おう。
上記条件では少ない人数で構成される閉路の数が絞られるため、結果的に閉路の数は減りbitsetで処理する回数が減る。

逆にi人からなる閉路の数n(i)が多い場合を考える。
i人未満の閉路に関してDPを行い、以下が求められていたとする。
V[x] := i人未満の閉路をいくつか選択し、合計頂点数がxであるかどうか

ここから以下を求める。
W[x] := i人以下の閉路をいくつか選択し、合計頂点数がxにできるかどうか。また、できるときi人の閉路をあといくつ選択できるか。

この時以下のように処理を行えば、n(i)個分のDPをO(N)で終わらせることができる。

  • V[x]=trueのときW[x] = n(i)
  • V[x]=falseのときW[x] = W[x-i] (W[x]が0未満の場合、条件を満たす組み合わせはない)
int N,K;
int P[1010101];
int vis[1010101];
int cnt[1010101];

int getmin() {
	bitset<1010100> b;
	static int lef[1010101];
	b[0]=1;
	int j;
	for(int i=1;i<=1000000;i++) {
		if(cnt[i]<100) {
			FOR(j,cnt[i]) b |= b<<i;
		}
		else {
			bitset<1010100> c;
			MINUS(lef);
			for(j=0;j<N;j++) {
				if(b[j]) lef[j]=cnt[i];
				if(lef[j]>=0) c[j]=1;
				if(j+i<N) lef[j+i]=lef[j]-1;
			}
			b=c;
		}
	}
	
	return (b[K]?K:(K+1));
}

int getmax() {
	int left=0;
	int ret=0;
	int k=K;
	for(int i=1;i<=1000000;i++) {
		for(int j=0;j<cnt[i];j++) {
			if(k*2<=i) {
				ret+=k*2;
				k=0;
			}
			else {
				ret+=i/2*2;
				k-=i/2;
				left+=i%2;
			}
		}
	}
	if(k) ret += min(k,left);
	return ret;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	scanf("%d%d",&N,&K);
	FOR(i,N) scanf("%d",&P[i]), P[i]--;
	
	FOR(i,N) if(vis[i]==0) {
		x = 0;
		y = i;
		while(vis[y]==0) {
			x++;
			vis[y]=1;
			y=P[y];
		}
		cnt[x]++;
	}
	
	cout<<getmin()<<" "<<getmax()<<endl;
}

まとめ

multisetで登場回数が多い要素に対するナップサックテク、今後も使えるかもしれないから覚えておこう。