bouzuya.hatenablog.com

ぼうずやのにっき

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

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

問題: https://atcoder.jp/contests/past202109-open/tasks/past202109_i

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

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

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

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

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

解説: https://atcoder.jp/contests/past202109-open/editorial/2726 提出: https://atcoder.jp/contests/past202109-open/submissions/28641509


今日のコミット。