nishiohirokazu https://blog.hatena.ne.jp/nishiohirokazu/ 西尾泰和のはてなダイアリー https://nishiohirokazu.hatenadiary.org/ TopCoder 久しぶりに時間が十分余ったので1000点問題にも挑戦。「1からスタートして与えられた整数nまで何回の操作でたどり着けるかこたえなさい。やっていい操作は 1増やす 1減らす(元の値が1より大きい場合のみ) 累乗する(たとえば元の値が2なら4とか8とか16に変える) の3つ」 単純に計算すると当然3の累乗で可能性が膨らんで行って発散するので「すでに出た数字は探索しない(最短ではないから)」「ゴールを超えた数字はdecrementで戻ってくるしかないので、powerはギリギリ超えるところまで」「ゴールを超えている数はインクリメントしない」という枝刈りを入れたのだけど、それでもまだ枝刈りが足りなくて、… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Fnishiohirokazu.hatenadiary.org%2Fentry%2F20090324%2F1237915884" title=" Single Round Match 437 (Div2/1000point) - 西尾泰和のはてなダイアリー" 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 2009-03-24 02:31:24 rich https://nishiohirokazu.hatenadiary.org/entry/20090324/1237915884 1.0 100%