問題
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; }
