2022-01-20 第八回アルゴリズム実技検定 (PAST) I - /2 and *3 を解いた

第八回アルゴリズム実技検定 (PAST) I - /2 and *3 を解いた。

2 で割って 3 を掛ける操作を繰り返す。少なくとも対象を同一にすれば単純に 3/2 倍で損はない。つまり操作は最大回数まで繰り返すのが良い。

操作の最大回数 C は各項の 2 で割れる回数の総和になる。はじめにすべての項を 2 で割れるだけ割ってその回数の総和と割った後の数列 B を得る。この処理における最悪ケースが 10^5 個の 10^9 のときだ。各要素はたかだか 30 回程度のはずなので C <= 3 * 10^6 になる。

あとは数列 B の最小値に対して 3 倍する操作を C 回繰り返す。

操作後の新たな最小値を求めるために数列 B 全体を走査すると O(CN) となって間に合わない。そこで優先度付きキュー (Rust なら BinaryHeap) を使う。最小値をデキューして 3 倍してエンキューする。これで O(ClogN) になるので間に合う。

操作を C 回繰り返して 64 bit 型の数値におさまるのかについてはおそらく大丈夫で、操作対象は数列全体におおむね均等になるはずで、さきほどの最悪ケースで考えても各要素 30 回程度になるはず。 3^32 でも 2^64 よりは小さい。不安なら u128 で殴ればなんとかなるはず。

今日のコミット。