これは勉強になった。
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で登場回数が多い要素に対するナップサックテク、今後も使えるかもしれないから覚えておこう。