はまやんはまやんはまやん

hamayanhamayan's blog

PolandBall and Gifts [Codeforces 8VC Venture Cup 2017 - Elimination Round : F]

問題

http://codeforces.com/contest/755/problem/F

N人がプレゼントを持っていて、iさんがP[i]さんに渡す。
このうち、K人がプレゼントを忘れてくる。
忘れてくる任意の組合せのうち、以下のルールによりプレゼントが貰えない人数の最大・最小を答えよ。

以下の2つのいずれかを満たすと、プレゼントがもらえない

  • プレゼントを忘れた
  • プレゼントをくれるはずの人がプレゼントを忘れた

2 <= N <= 10^6
0 <= K <= N
P[i]は1~Nの順列

参考

これは色んな所を参考にして、やっと理解した。
後続者のためにどういう思考の流れか、メモしておく。
http://kenkoooo.hatenablog.com/entry/2017/01/16/053254
http://codeforces.com/contest/755/submission/23854346
http://codeforces.com/blog/entry/49793

解法

1. プレゼント先をグラフで考えると、鎖状のグラフが幾つかある状態になる
2. なので、cnt[i]を長さiの鎖状のグラフの個数と置き、これを何らかの方法で求めておく -> pre()

3. 次に公式Editorialにもあるが、最大は貪欲に考えて行けばよい
4. 自分の解法では、1つのプレゼント忘れでなるべく2人もらえないようにして、それが全部終わったら、1つのプレゼント忘れで1人もらえないようにしている -> solve_max()

5. 問題は最小である
6. Twitterや解説では「ナップサック問題」であると言われているが、これはどういうことだろう

7. まず「最小はKかK+1のどちらかである」ということ
8. 最小にするなら1つのプレゼント忘れでなるべく1人もらえないようにしたい
9. 最適に選択していくと1つのプレゼント忘れで2人もらえないことは高々1回しか起きないようにできる
(任意の2箇所で1つのプレゼント忘れで2人もらえない状況があれば、1つのプレゼント忘れで1人もらえない状況と1つのプレゼント忘れで2人もらえない状況に置き換えられる)
10. 全ての状況で1つのプレゼント忘れで1人もらえないのは、「全ての鎖状のグラフに対して、そのグラフの中の全ての人がプレゼントを忘れている、か、全ての人がプレゼントを忘れていない」ときである

11. 7.~10.をまとめると「鎖状のグラフを任意個選んで、人数の総和を取った時にそれがKであれば最小はKであり、そうでなければK+1である」
12. ナップサック

13. 実際に解く場合はナップサックでおなじみのDPを使う
14. dp[i] = 鎖状のグラフを任意個選んで人数の総和をiにできるか

15. 愚直に書くと以下のようになる

int dp[1010101];
int solve_min() {
	dp[0] = 1;
	rep(i, 2, N + 1) {
		rep(j, 1, cnt[i] + 1) {
			rep(k, 0, K) {
				int idx = k + i * j;
				if (idx < 1010101) dp[idx] = 1;
			}
		}
	}

	if (dp[K])
		return K;
	else
		return K + 1;
}

16. これだと余裕でTLE
17. ここでよくあるbitsetによるdpの高速化を行う

bitset<1010101> dp;
int solve_min() {
	dp[0] = 1;
	bitset<1010101> b;
	rep(i, 2, N + 1) {
		b = dp;
		rep(j, 1, cnt[i] + 1) {
			dp |= b << (i * j);
		}
	}

	if (dp[K])
		return K;
	else
		return K + 1;
}

18. これでもTLEした(bitsetの演算のせい?)
19. 更新にO(cnt[i])かかっているが、以下のようにやるとO(log(cnt[i]))にできる

bitset<1010101> dp;
int solve_min() {
	dp[0] = 1;
	bitset<1010101> b;
	rep(i, 2, N + 1) {
		int j = 1;
		while (0 < cnt[i]) {
			j = min(j, cnt[i]);
			dp |= dp << (i * j);
			cnt[i] -= j;
			j *= 2;
		}
	}

	if (dp[K])
		return K;
	else
		return K + 1;
}

20. 理解が難しいかと思うが、bit的には以下の様なことをやっている

例) cnt[2] = 3, dp = 00000001
<j = 1>
dp |= dp << 2
= 00000101
<j = 2>
dp |= dp << 4
= 00010101
<j = min(4,3) = 3>
dp |= dp << 6
= 01010101

21. 説明しづらいが1->2->4->8->16みたいにシフト演算を伝搬させている
22. ここまでやって、やっとAC

解答

#define rrep(i,a,b) for(int i=a;i>=b;i--)
int N, K;
int P[1010101];
//-----------------------------------------------------------------
int cnt[1010101];
int v[1010101];
void pre() {
	rep(i, 0, N) if (!v[i]) {
		int c = 0;
		int j = i;
		while (!v[j]) {
			c++;
			v[j] = 1;
			j = P[j];
		}
		cnt[c]++;
	}
}
//-----------------------------------------------------------------
int solve_max() {
	int kk = K;
	int ret = 0;
	int cc = 0;
	rrep(i, N, 2) {
		int d = i / 2;
		if (kk <= d * cnt[i]) {
			return ret + kk * 2;
		}

		kk -= d * cnt[i];
		if (i % 2) cc += cnt[i];
		ret += d * cnt[i] * 2;
	}

	ret += min(kk, cc);

	return ret;
}
//-----------------------------------------------------------------
bitset<1010101> dp;
int solve_min() {
	dp[0] = 1;
	bitset<1010101> b;
	rep(i, 2, N + 1) {
		int j = 1;
		while (0 < cnt[i]) {
			j = min(j, cnt[i]);
			dp |= dp << (i * j);
			cnt[i] -= j;
			j *= 2;
		}
	}

	if (dp[K])
		return K;
	else
		return K + 1;
}
//-----------------------------------------------------------------
int main() {
	cin >> N >> K;
	rep(i, 0, N) scanf("%d", &P[i]), P[i]--;

	pre();
	int ma = solve_max();
	int mi = solve_min();

	cout << mi << " " << ma << endl;
}