SRM617 Div1 Medium "PieOrDolphin"
問題
まだ
(なぜ追加されない・・)
訳
はるか遠い国、そこには50人のプログラマーが一緒のオフィスで働いていた。プログラマー達には0~49の番号が振られている。イワンは町の有名人である。プログラマーはイワンの事を尊敬していたため、彼を自分達のオフィスに招待した。そのことを嬉しく思ったイワンは、これからN日間、毎日訪れることに決めた。(順番に0~N-1日目と呼ぶことにする)
毎日イワンは1つはイルカの形でもう1つはパイの形をした2つのおもちゃを持っていくことにした。それぞれの日で、プログラマー達は最も生産的な話し合いができるような、2人のプログラマーを選出し、イワンと合うようにした。1人はイワンからイルカのおもちゃをもらい、もう1人はパイのおもちゃをもらっていた。(イワンがどちらのおもちゃをどちらのプログラマーに渡すかを決めていた)
イワンがオフィスを訪れる最後の日。最後のイルカとパイのおもちゃを彼が渡した後、プログラマーは彼をお別れ会のディナーに招待した。そのディナーの中で、それぞれのプログラマーが、受け取ったイルカのおもちゃの数と、パイのおもちゃの数の差の絶対値を計算した。それから、彼らはその合計値を計算した。驚いたことに、その値は最小値となっている事が判明した。プログラマー達はイワンのスキルに非常に驚き、どのようにやったかを尋ねたが、彼は幸運だったと控えめに答えただけだった。
あなたは2つのN個の要素を持つint[] choice1, choice2が与えられる。choice1[i], choice2はそれぞれi日目に何番目のプログラマーがイワンと会い、おもちゃを受け取っていたかを表す。上記の最小値を満たすためには、どのようにおもちゃを渡せばよいかを示して欲しい。N個の要素を持つvector
制約
1 <= choice1.size() <= 1000
choice1.size() == choice2.size()
0 <= choice1[i], choice2[i] <= 49
choice1[i] != choice2[i]
考えたこと
プログラマーを頂点としたグラフに置き換えて考えてみる。
それぞれの日に2人のプログラマーがイワンと会っているが、こいつらを辺で結ぶ。その時、イルカをもらったほうをfrom、パイをもらったほうをtoとして、有向な辺にしておく。
そう考えると、各頂点の入次数と出次数の差をなるべく少なくしたい。閉路にできる辺はコスト0となるので、どう閉路を作っていけばよいかが問題になりそう。
・・・だがしかし・・・
なんかどう閉路を作っても、問題なく最小値を作れるみたいだ・・。
なので、適当に閉路を作って、後は次数が1になってる辺を見つけて適当にパスを辿るのみ。
もっといい考え方
どこぞの赤コーダーさんのブログに書いてあったんですが、次数が奇数の頂点がコスト1(入次数・出次数の差が1)、次数が偶数の頂点がコスト0(入次数・出次数が同じ)となるのが最善で、こうなるように辺の向きを決めていけばよい。という考え方があるようで、断然こっちの方がいいな~と思いました。
なんかあと、オイラー路なるものと関連があるらしい・・
ソースコード
int n; vector <int> c1, c2; bool used[1050]; bool vis[55]; int cnt[55]; vector <int> ans; bool isEnd; class PieOrDolphin { public: vector <int> Distribute(vector <int> choice1, vector <int> choice2) { n = choice1.size(); c1 = choice1; c2 = choice2; ans.resize(n); memset(used, false, sizeof(used)); memset(vis, false, sizeof(vis)); // 閉路を見つけて使った辺を記録する for (int i = 0; i < 50; ) { isEnd = false; memset(vis, false, sizeof(vis)); int r = dfs1(i); if (r == -1) i++; } // 各頂点の次数を数える memset(cnt, 0, sizeof(cnt)); for (int i = 0; i < n; i++) { if (used[i]) continue; cnt[c1[i]]++; cnt[c2[i]]++; } // 次数が1となってる頂点を見つけ、パスを辿り、 // 使った辺を記録する while (true) { bool end = true; for (int i = 0; i < 50; i++) { if (cnt[i] == 1) { dfs2(i); end = false; } } if (end) break; } return ans; } // 頂点sからdfsして閉路を見つける int dfs1(int s) { vis[s] = true; for (int i = 0; i < n; i++) { if (used[i]) continue; if (c1[i] != s && c2[i] != s) continue; int t; if (c1[i] == s) { t = c2[i]; ans[i] = 1; } else{ t = c1[i]; ans[i] = 2; } used[i] = true; if (vis[t]) return t; int r = dfs1(t); if (r == -1) { used[i] = false; } else { if (isEnd) used[i] = false; if (s == r) isEnd = true; return r; } } vis[s] = false; return -1; } // 頂点sからdfsしてパスを辿る void dfs2(int s) { int t = -1; for (int i = 0; i < n; i++) { if (used[i]) continue; if (c1[i] != s && c2[i] != s) continue; if (c1[i] == s) { ans[i] = 1; t = c2[i]; } else{ ans[i] = 2; t = c1[i]; } used[i] = true; cnt[c1[i]]--; cnt[c2[i]]--; break; } if (t != -1) dfs2(t); } };