hamayanhamayan https://blog.hatena.ne.jp/hamayanhamayan/ はまやんはまやんはまやん https://blog.hamayanhamayan.com/ 競技プログラミング https://codeforces.com/contest/1305/problem/F 前提知識 乱択アルゴリズム 解説 https://codeforces.com/contest/1305/submission/72492279 手の付け所の1つとして最適方針を考えるというのがある。 この仮定で重要なものを得ることができる。 全部のgcdを取った結果を2にしたいと考えると、奇数の要素を+1すれば達成できるので、 答えがNを超えることはない。 ここから得られるものが何かというと、ある最適解が存在して、各要素に必要な操作回数が割り当たっているとする。 その要素のうち1つをランダムで選んだ時… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fblog.hamayanhamayan.com%2Fentry%2F2020%2F03%2F06%2F130746" title="Kuroni and the Punishment [Ozon Tech Challenge 2020 (Div.1 + Div.2, Rated, T-shirts + prizes!) F] - はまやんはまやんはまやん" 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 2020-03-06 13:07:46 rich https://blog.hamayanhamayan.com/entry/2020/03/06/130746 1.0 100%