masuTomo’s blog

競技プログラミングの勉強メモです.主にPythonを使用します.数学の記事も書くかもしれません.

yukicoder No.897 compαctree

一問ずつ記事をかくのはどうなのか?という思いもある。

問題

No.897 compαctree - yukicoder

少し図を書いて考察すればすぐに規則がわかる。 N = 41, K = 3として考えてみる。
深さを最小にしたいので,各頂点に対する子の数はK個とするのが最良である。 f:id:masuTomo:20200102233221p:plain

図からわかるように,
深さ0のとき,頂点数は1個
深さ1のとき,頂点数は3個
深さ2のとき,頂点数は9個
深さ3のとき,頂点数は27個 であり,K倍ずつになっている。これの和がNを初めて超える深さを求めればよい。 Kのべき乗で増えていく,つまりどんどん増えるので単純にKのべき乗の和を計算して,Nを超えたときの深さを素直に出力すればOK。
K=1のときだけ少し注意。

Q = int(input())
for i in range(Q):
    N,K = map(int,input().split())
    if K == 1:
        print(N-1)
    else:
        ans = 1
        i = 1
        while ans < N:
            ans += K**i
            if ans >= N:
                print(i)
                break
            i += 1
おまけ

高校数学の知識を覚えている人がいれば,以下のように考えても問題を言い換えてもよい。 初項1,公比K等比数列の第n項までの和 \frac{K ^n -1}{K-1} \gt N を満たす最小のnを求める。 不等式を変形して  n \gt \log _K (N(K-1)+1) を満たす最小のnを求めればよいことになるので,
pythonのmathモジュールmath --- 数学関数 — Python 3.8.1 ドキュメント
が使える環境であれば以下のようにしてもよい。

import math
Q = int(input())
for i in range(Q):
    N,K = map(int,input().split())
    if K == 1:
        print(N-1)
    else:
        print(int(math.log(N*(K-1)+1,K)))