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

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

[AtCoder] SoundHound Programming Contest 2018 Masters Tournament 本戦 の感想

問題

Tasks - SoundHound Programming Contest 2018 Masters Tournament 本戦 (Open) | AtCoder

A問題だけ解くことができました。

A - Feel the Beat

配点が300ということでもう撤退しようか迷ったんですが、頑張って考えて見ました。

 a_n = 140 \cdot 2^{n-1}

 b_n = 170 \cdot 2^{n-1}

区間  [ C, D)区間  [a, b] が重なるものを n の値を増加させて調べます。

 a_n \leq C かつ  C \leq b_n \leq D のとき

候補となる数字の数は、

 b_n - C

となります。

 C \leq a_n, b_n \leq D のとき

候補となる数字の数は、

 b_n - a_n

となります。

 C \leq a_n \leq D かつ  D \leq b_n のとき

候補となる数字の数は、

 D - a_n

となります。

 a_n \geq D のとき

区間の検査を終えます。

コード
import java.util.Scanner;

public class ProblemA {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        long C = scan.nextLong();
        long D = scan.nextLong();
        scan.close();

        long k = 1;
        long ans = 0;
        while(true) {
            long a = 140 * k;
            long b = 170 * k;

            if(a > D) {
                break;
            }
            if(a <= C && b >= C && b <= D) {
                ans += b - C;
            }else if(a >= C && b <= D) {
                ans += b - a;
            }else if(a >= C && a <= D && b >= D) {
                ans += D - a;
            }


            k = k * 2;
        }
        System.out.println(ans);
    }
}

感想

A問題で、最初考えたときはfor文を回さないで解けると思ったんですが、僕には分からず、繰り返し区間を調べることにしました。

ですが、 2^n の発散スピードを考えると、for文で十分に間に合うことが分かりました。

B問題は累積和を使うのかな?と思ったんですが、解けませんでした。