komiyam https://blog.hatena.ne.jp/komiyam/ komiyamの日記 https://komiyam.hatenadiary.org/ その他のコンテスト 問題概要 原点を含まない円がN( 考えたこと 幾何は問題じゃなく、極座標で考えると区間の被覆する区間を最大化する問題に落ちることが分かる。 フローのF？でもノード数多いしそもそもフローだとしたらdoubleな時点で自分には解けない。 残るは貪欲かDPか。入力サイズ的にDPだろうなあ。 状態を(何番目まで見たか、今までいくつ選んだか、直前に選んだ区間は何か)としたら状態数O(N^2*K)で解けない。 本番中はここまで考えて、計算量が落とせなかったので別の問題に移った。 解法を人から教えてもらって再挑戦。 幾何パートはEPSとか使わずに処理する。doubleだからいつでもEPSを使う、というのは危… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fkomiyam.hatenadiary.org%2Fentry%2F20110815%2F1313334256" title="KUPC 2011 F: ボ〜ル - komiyamの日記" 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 2011-08-15 00:04:16 rich https://komiyam.hatenadiary.org/entry/20110815/1313334256 1.0 100%