aacord https://blog.hatena.ne.jp/aacord/ aacord’s memo https://aacord.hatenablog.com/ abc メモ化再帰 逆から考える 青diff 気づくこと 一回でも x を操作する途中で２倍した後は、二回連続で +1, -1 を使わない。 理由 p 回 +1 した後に、２倍して q 回 +1 すると、 (x + p)*2 + q = 2x + 2*p + q q ≧ 2 のとき 2x + 2*p + q = 2x + 2*p + 2*s + t(s ≧１, t は 0 or 1) となり p + s 回 +1 してから２倍して 0 または 1 回 +1 した方が p + s + t そこで Y から X を作ることを考える。そうすると考察から、 Y から X を作る時の最適な操作は、 X : 偶数 X → X/2 (x' とする) X… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Faacord.hatenablog.com%2Fentry%2F2021%2F02%2F11%2F004627" title="abc 188 F - +1-1x2 (python) - aacord’s memo" 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 2021-02-11 00:46:27 rich https://aacord.hatenablog.com/entry/2021/02/11/004627 1.0 100%