おはようございます。進捗ダメすぎて死にました。この文章は私の思考をトレースしたAIが書いています。
このブログには一応、「プログラミング未経験者がプログラミングをゼロから勉強していく過程を残そう！」みたいな健気な理念があった気がするんですが、なんかどこかへ行きました。不思議ですね。
いや記事を書くより勉強するスピードの方が早いので仕方ないですね（笑）（嘘です、私の名前は怠慢です）
動的計画法の記事とか書いた覚えがあるんだけどどこにやったか、さては下書きに残ってるな、ワロタ。（ワロタじゃありません）
今回はUnion-Findの利用が重要な問題を二つまとめて今後の参考に残したいと思います。
この間の京大プログラミングコンテストのB問題です。sabaくんが京大まで行って出場していたっぽいですね、ずるい。ばーかばーか。
名前の通りナップサック問題です……が、普通と様子が違います。このままじゃ解けない。
頭が悪いので次のように思考を展開しました。
ナップサックに帰着できるorできない。前者を仮定。
「aが使われる時はbも使われないといけない」というような荷物をひとまとめにすれば普通のナップサック問題に帰着出来る。つまり動的計画法でO(n^2)で解ける。
ではどうやってひとまとめにするか？→Union-findで番号の繋がりを管理すればよい。
数学の問題を解くときとかはこんな感じで深さ優先探索のように解法を考えるんですが、他の人がどうなのか聞いたことがありません。もしよかったらTwitterとかで教えてください。
と言うわけでコードです。
#include<bits/stdc++.h> using namespace std; typedef long long ll; #define rep(i,n) for(int i = 0; i < int(n); ++i) ll dp[101][1000005]; int main(){ int n, m, W; cin >> n >> m >> W; int w[n], v[n]; rep(i,n) cin >> w[i] >> v[i]; union_find u(n); //ひとまとめにする int a, b; rep(i,m){ cin >> a >> b; a--; b--; if(a > b) swap(a, b); u.unite(a,b); } //子の要素を親へ集中させる rep(i,n){ if(i != u.root(i)){ w[u.root(i)] += w[i]; v[u.root(i)] += v[i]; w[i] = 0; v[i] = 0; } } //ナップサック問題に帰着 rep(i,n){ rep(j,W+1){ if(j < w[i]) dp[i+1][j] = dp[i][j]; else dp[i+1][j] = max(dp[i][j-w[i]] + v[i], dp[i][j]); } } cout << dp[n][W] << endl; }
相変わらず読みやすいコードですね。うっとり。
Union-Findの実装は省略しています。分からない部分があったら以前の記事（
自作の関数の保存というのをやってみました - Re:ゼロから始めるプログラミング生活
）か、GitHubを参照してください。
（記事との変更点はクラスにしてコンストラクタを入れたことぐらいなので大丈夫だと思います。）
今回の問題の教訓ですが、次の二つが気になりました。
・グループの要素数が減らない場合、つまり連結しか行われない場合は対象に番号を割り振ることで、Union-Findでグループ分けが出来る。
・ナップサック問題で荷物の重量と価値を0にしておけば、その荷物はないものとして、荷物の数を変えないまま実装出来る。（要検証）
2つ目は他で使うのか？って感じなので放っておきます。
1つ目は、連結判定が本質的にグループ分けになっているという話です。考えたら当たり前のような気がしますが、Union-Findでグループ分けを手軽に行えるようになるのは大きいと思います。
次の問題です。
これDifficulty低くないですか、みんな当たり前のように全探索出来たりUnionFind使えるのなんなんでしょう。
sabaとか水色なのにUnion-findわからーん！とか言ってた時期があった（僕がプログラミングを始めた当初の話です）し、chokudaiさんの言うように各色の平均的な実力が上がっているのかも。つまりぼくはえらい。
さて、この問題ではまず実質的にA_xi+A_yiの偶奇が与えられているところから始まります。
A_xiとA_yiのどちらか一方の偶奇がわかればもう片方の偶奇も分かるということになります。
そこで、これらをグラフの要素とみて、繋いでおきます。
こうして繋いで行くと、グラフの繋がった頂点の集合では、どれか一つの偶奇がわかれば他の偶奇も分かることになります。
結局、頂点がグループになっていて、このグループ数を求めたいわけです。明らかにUnion-Findの出番です。
int main(){ int n,m; cin >> n >> m; union_find graph(n+1); int x,y,z; int ans = 0; rep(i,m){ cin >> x >> y >> z; graph.unite(x,y); } rep(i,n) if(graph.root(i+1) == i+1) ans++; cout << ans << endl; }
このように解けます。
Union-Findの利用例はもっとありますが、体力が切れたのでここまでにします。
今回当たり前のようにナップサック問題を解いていましたが、結局動的計画法の勉強記録を載せていないので流れとして不自然な気がしますね。気がするだけなので諦めることにします。
ではおやすみなさい。
