きままにものづくり

日々の気付いたことなんかを書いてます。

SRM612Div1Easy

問題

目標の数字Sが与えられる。初めは1からスタートし、以下の操作を行い目標の値にする。

  • 現在の値をコピー
  • 以前コピーした値を現在の値に加算
  • 現在の値から1を引く

Sとするのに必要となる最小の操作回数を求めよ。

解法1

1を引く操作ができないと仮定すると、現在の値とコピーした値で全探索をすることができる。
この時の計算量を計算する。
 N+N/2 + N/4 + ... + N/2^{logN}
 =N*2^{log N}(1+2+4+...+2^{log N})
 =(1+2+4+...+2^{log N})
 =(2^{log N} - 1)
 =N
このあとに、1を引いた方が少ない回数となる箇所を探索する。1が引けなくなるまで以上の操作を繰り返すことで答えが求まる。Nを上回ることはないのでO(N)とするが、実際はかなり小さい回数で停止する。

計算量1

時間計算量: O(N^2)
空間計算量: O(N)

コード1


解法2

現在の値とコピーした値をメモ化し動的計画法で解く。sを現在の値、cをコピーした値とし、状態を(s, c)で表す。はじめ、(1, 0)からスタートしBFSで最小の操作回数を求める。

計算量2

時間計算量: O(N^2)
空間計算量: O(N^2)

コード2