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種類目の分銅の左右に割り振る図を描くと見えてくる。