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

問題

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

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

A - Feel the Beat

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

区間 と区間 ] が重なるものを の値を増加させて調べます。

かつ のとき

候補となる数字の数は、

となります。

のとき

候補となる数字の数は、

となります。

かつ のとき

候補となる数字の数は、

となります。

のとき

区間の検査を終えます。

コード

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文を回さないで解けると思ったんですが、僕には分からず、繰り返し区間を調べることにしました。

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

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