山傘のプログラミング勉強日記

プログラミングに関する日記とどうでもよい雑記からなるブログです。

[yukicoder] No.378 名声値を稼ごう

数学よりな問題?

No.378 名声値を稼ごう - yukicoder

問題の肝は、スキルを使わないときの名声値の計算と、スキルを使うとき何回目にスキルを使うべきかです。

考え方

 i 回目の名声ポイントを  a_i とすると、 i の最大値  kは、

 k = \lfloor \log _{2} N \rfloor

これは、

 2^k \leq N \lt 2^{k + 1}

を満たす k N を2 で割り続けたときに、割った値が1以下にならない値となるからです。実際には、小数点以下切り捨てなので、ちゃんとした証明は僕には分かりません。

しかし、  k は目安となる値だと思います。

小数点以下を切り捨てないで名声ポイントを考えて見ます。

切り捨てを考えない場合

名声ポイントの合計を  S とします。

 S = N + \dfrac{N}{2} + \dfrac{N}{2^2} + \cdots + \dfrac{N}{2^k}

 S = N \left ( 2 - \dfrac{1}{2^k} \right)

となります。

1回目でスキルを使うときの名声ポイントの合計を  S_1 とすると、

 S_1 = N + N = 2N

となります。次に2回目は、

 S_2 = N + \dfrac{N}{2} + \dfrac{N}{2} = 2N

となります。したがって、切り捨てない場合はいつスキルを使っても変わらないことが分かります。

切り捨てを考える場合

切り捨てが起こる場合というのは、

 N = 2^k M

と表現したときに、 k の値が N 2 で割り続けるときに切り捨てが起こらない最大の値となります。

つまり、 k 以内にスキルを使う必要があるので、スキルを使うタイミングは1回目で良いことが分かります。

Javaで対数を求める

Javaで任意の底を持つ対数は、対数の底変換を行う必要があります。具体的には、

 \log _x  y = \dfrac{\log _{10} y }{\log _{10} x}

を利用します。 d.hatena.ne.jp

コード

import java.util.Scanner;

public class Exec0378 {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        long N = scan.nextLong();
        scan.close();
        int k = (int) (Math.log10(N) / Math.log10(2));
        long sum = N;
        for(int i = 0; i < k; i++) {
            long a = (long) Math.pow(2, (i + 1));
            sum += (long) (N / a);
        }
        //long ans = N + ((long) (N / 2)) * 2 - sum;
        long ans = 2 * N - sum;
        System.out.println(ans);
    }
}