7K12 blog

猫でも分かるアルゴリズム解説

Kyoto University Programming Contest 2019 C - てんびんばかり

f:id:tkr987:20200527153008p:plain

https://atcoder.jp/contests/kupc2019/submissions/13635953

  • K=1のときは有名で以下が答えになる
  • 天秤の片方にしか分銅を載せられないなら 2^n
  • 天秤の左右に載せられるなら 3^n

f:id:tkr987:20200527205531p:plain
K=1のときは有名で「バシェの分銅問題」という名前が付いているらしい。

ただし、今回は分銅の個数Kが 10^5個まで増えるので考察が必要。

そもそも、K=1でも個人的に難しい。大抵のアルゴリズムでは 2^N \log Nが最善なのに、天秤だと 3^Nが最善になると気づくのは凡人には厳しいと思う(^^; 最善が 3^nになる理由…というより 2^nにならない理由は分銅を左右に載せられるからであり、それぞれ加算と減算に対応する。n-1種類目の分銅で測れる範囲をn種類目の分銅の左右に割り振る図を描くと見えてくる。

同様に、K=2以降について考えてみる。n種類目の分銅が2個あることに注意して同様の図を描くと以下の式が見えてくる。

limit[i] = limit[i-1] + ( limit[i-1] * 2 + 1) * K;

ただし、limit[i] := i種類の分銅を使って測れる範囲とする。