搁鲍笔颁2017:贰解説
- 1. E: Tangled Cables 原案?解説: 胡桃沢（蔼耻办耻办耻09）
- 2. 問題概要 ? n頂点m辺の連結なグラフが与えられる ? 辺にはciとdiの二つのパラメータがある ? いくつかの辺を取り除いて全域木をつくる ? 全域木：グラフ上の任意の2頂点が連結な木 ? 取り除く辺の di/ ciの最小値は？
- 3. 考察 ? 取り除かない辺について考えてみる ? 最小全域木のアルゴリズムが使えそう ? di/ciの大きい順に辺を使っていけばよいか？ ? これはいいえ
- 4. 考察 ? 今、取り除く辺の di/ ci=2000/1000 ? (ci,di)=(10,7)の辺eと(ci,di)=(100,75)の辺fのう ち、どちらか一方だけ取り除ける ? di/ciが大きいほう（辺f）を全域木に使う？ ? 辺eを取り除くと di/ ci=2007/1010=1.98712… ★ 辺fを取り除くと di/ ci=2075/1100=1.8863…
- 5. 解説 ? 求める答えをtとすると、 ? di / ci t → (di - t*ci) 0 ? di-t*ciは辺ごとに独立して考えられる
- 6. 解説 ? di/ci t（di-t*ci 0）であるような辺 ? もし全部取り除いても di/ ci t ? di/ci>t（di-t*ci>0）であるような辺 ? できるだけ取り除かない ? 全域木に使う
- 7. 解説 ? 答え t を二分探索 ＋ Kruskal法 ? 辺はdi-t*cで降順ソート ? 全域木に使わなかった辺の di/ ci tならOK！ ? 最小比全域木問題（赤線部が逆）
- 8. ジャッジ解 ? arrows（C++）: 130 lines ? haji（C++）: 76 lines ? uku（C++）: 107 lines
- 9. 結果 ? First Submission ? Online: toy18 102 min ? First Accepted ? On-site: toy18 107 min ? Success Rate: 21.74 % (10/46)