Sen_comp https://blog.hatena.ne.jp/Sen_comp/ Senの競技プログラミング備忘録 https://sen-comp.hatenablog.com/ Codeforces 数学 3個 二分探索 良問 証明 要反省 以上以下 codeforces.com 概要 n_a, n_b, n_cと長さがn_aのa, n_bのb, n_cのcが与えられる。 aの中の1つの要素をx, bの中の1つの要素をy, cの中の1つの要素をzとする。を最小化せよ。制約： 1 ACするまで 1. 何か裏がありそうな式ではあるが、なんやかんやうまく全探索でやるしかなさそう。 2. 全探索をするのならば、制約的に何かしらを固定して、そこで二分探索ぐらいなら計算量が間に合う限界。 3. 3つのものの最適化なので、真ん中を固定して考えてみる。 4. 直感的な式が出てくるけど、これを証明することで正しいことが分かる。->AC 考察 数学としてみるの… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fsen-comp.hatenablog.com%2Fentry%2F2020%2F04%2F26%2F012905" title="Codeforces Round #635 (Div. 2) - D. Xenia and Colorful Gems - Senの競技プログラミング備忘録" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> https://chart.apis.google.com/chart?cht=tx&chl=%20%28x-y%29%5E2%2B%28y-z%29%5E2%2B%28z-x%29%5E2 Hatena Blog https://hatena.blog 2020-04-26 01:29:05 rich https://sen-comp.hatenablog.com/entry/2020/04/26/012905 1.0 100%