nishiohirokazu https://blog.hatena.ne.jp/nishiohirokazu/ 西尾泰和のはてなダイアリー https://nishiohirokazu.hatenadiary.org/ TopCoder 都市の座標と条件が与えられ、条件を満たすなるべく多いペア(2つの都市の「姉妹都市」関係)を作れ、という典型的なグラフ問題。条件とは「都市がminDistance以上離れている」と「一つの都市は最大maxPartner個の都市と姉妹都市になれる」の2つ。「ペアの個数が最大になるいくつかのペアの作り方のうち、一番距離の合計が短いものを選べ」という条件もついている。都市の数は最大10個、maxPartnerは最大で3なので、ペアになりうる組み合わせは最大45個、ペアの個数の最大は15個。全探索しても枝刈りをうまくやれば大丈夫じゃないかな、と思って試してみた。 class TwinTowns { pu… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fnishiohirokazu.hatenadiary.org%2Fentry%2F20081221%2F1229805950" title=" Single Round Match 430 (Div1/500point) - 西尾泰和のはてなダイアリー" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2008-12-21 05:45:50 rich https://nishiohirokazu.hatenadiary.org/entry/20081221/1229805950 1.0 100%