ヤマカサのプログラミング勉強日記

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

AtCoder Beginner Contest 105 の感想

AtCoder Java

問題

Tasks - AtCoder Beginner Contest 105

結果はB問題まで解くことができました。

A - AtCoder Crackers

N \mod K = 0 なら全員に同じ枚数のおせんべいが行き渡ります。そうでない場合は、差は 1 となります。

B - Cakes and Donuts

4x + 7y = N

を満たす正の整数 x, y が存在するかという問題です。

数学的には下のサイトで解説されています。

mathtrain.jp

N の最大値は 100 なので、for文で0から調べても良いですね。

コード

import java.util.Scanner;

public class ProblemB {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        int N = scan.nextInt();
        scan.close();
        for(int i = 0; i <= 25; i++) {
            for(int j = 0; j <= 14; j++) {
                int t = 4 * i + 7 * j;
                if(t == N) {
                    System.out.println("Yes");
                    System.exit(0);
                }
                if(t > 100) {
                    break;
                }
            }
        }
        System.out.println("No");
    }
}

C - Base -2 Number

考え方

N が2進数で何桁になるかを考えます。ここで桁とはビット列の長さを表すものとします。ここで、ビット列の長さを l とします。

長さ l で表すことができる数の範囲を考える

ビット列において、奇数番目の符号は正となり、偶数番目の符号は負となることに注意します。

また、最高位のビットは必ず1として考えます。これは長さ l のビット列を考えているためです。

この範囲を [ a, b] と表すことにします。

* l = 2n + 1 のとき

まず初めに、最大値を考えます。

奇数番目のビットが全て 1 のとき最大値を取ります。また、奇数番目のビットの数は n + 1 個あります。

したがって、

b = 1 + 4 + 4^2 + \cdots + 4^n

= \dfrac{4^{n + 1} - 1}{3}

次に、最小値を考えます。

最高位のビットが 1 であることから、最小値は偶数番目のビットが全て 1 のとき最小値を取ることが分かります。また、偶数番目のビットは n 個あります。

したがって、

a = 2^{l - 1} - \left ( 2 + 2 \cdot 4 + 2 \cdot 4^2 + \cdots + 2 \cdot 4^{n - 1} \right )

= 2^{l - 1} - 2\dfrac{4^{n} - 1}{3}

= \dfrac{4^n + 2}{3}

ここで、 l = 1 のとき、 n = 0 ですが、 a = 1 となってしまいます。なので、 n = 0 のときは例外として、 a = 0 とします。

以上より、 l が奇数のとき、長さ l のビット列で表すことができる数値 N は、

l = 1 ならば、 0 \leq N \leq 1

l \neq 1 ならば、 \dfrac{4^n + 2}{3} \leq N \leq \dfrac{4^{n + 1} - 1}{3}

となります。ここで、気が付くことは、 l が奇数ならば 0 以上の整数となることが分かります。

* l = 2n のとき

奇数のときと同様にして考えます。

まず、最小値を考えます。

最小値は偶数番目のビットが全て 1 でそれ以外は 0 です。したがって、

a = - \left ( 2 + 2 \cdot 4 + 2 \cdot 4^2 + \cdots + 2 \cdot 4^{n - 1} \right )

= -2\dfrac{4^{n} - 1}{3}

となります。最大値は最高位のビットが 1 で奇数番目のビットが 1 です。したがって、

b = -2^{l - 1} + \left (1 + 4 + 4^2 + \cdots + 4^{n - 1} \right )

= -2\cdot 4^{n - 1} + \dfrac{4^{n} - 1}{3}

= - \dfrac{2 \cdot 4^{n - 1} + 1}{3}

となります。したがって、 l が偶数のとき、長さ l のビット列で表現できる数値 N は、

-2\dfrac{4^{n} - 1}{3} \leq N \leq - \dfrac{2 \cdot 4^{n - 1} + 1}{3}

となります。

また、ビット列の長さが偶数のときは負の整数を表すことが分かります。

N の -2 進数表記を求める

上記の長さ l のビット列で表現できる数の範囲を用いて、 -2 進数表記を求めます。

N の -2 進数表記におけるビット列の長さを l とします。

上記から、 N が正の数であれば、 l は奇数となり、 N が負の数であれば、 l は偶数となります。

上記の正の区間を p_i 、負の区間を q_j とします。

例えば、

p_1 = [0, 1]

p_2 = [2, 5]

p_3 = [6, 21]

q_1 = [-2, -1]

q_2 = [-10, -3]

q_3 = [-42, -11]

のようになります。

これらを利用すると、 N = 5 は p_2 の区間に入るので、 l = 2 \cdot (2 - 1) + 1 = 3 となります。また、 N = 12 では、 p_3 の区間に入るので、 l = 2 \cdot (3 - 1) + 1 = 5 となります。

負の数では、 N = -5 は、 q_2 の区間に入るので、 l = 2 \cdot 2 = 4 となります。

上記より、 N が区間 p_i に入るのならば、

l = 2(i - 1) + 1 = 2i - 1

となり、 q_j に入るのならば、

l = 2j

となります。

ある区間に入るということは、そのビット列の長さが分かるということであり、ビット列の最高位は必ず 1 となります。

まず初めに N_1 = N のビット列の長さを求めます。この時の長さを l_1 とします。

N が正の数の場合

N_2 = N_1 - 2^{l_1 - 1}

N が負の数の場合

N_2 = N_1 + 2^{l_1 - 1}

として、 N_2 のビット列の長さ l_2 を求めます。

これらを N_i = 0 になるまで続けます。 l_i が N のビット列の左から l_i 番目のビットが 1 となります。

まとめると、

N_{i - 1} が正のとき

N_{i} = N_{i - 1} - 2^{l_{i - 1} - 1}

N_{i - 1} が負のとき

N_{i} = N_{i - 1} + 2^{l_{i - 1} - 1}

となります。

コード

整理するつもりでしたが、この記事書いてて疲れたのでやめます。

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class ProblemC {
    public static void main(String[] args) {
        Scanner scan = new Scanner(System.in);
        long N = scan.nextLong();
        scan.close();
        if(N == 0) {
            System.out.println(0);
            System.exit(0);
        }
        // 長さ2n + 1で表すことができる数値の最小値と最大値
        List<Long> list1 = new ArrayList<Long>();
        List<Long> list2 = new ArrayList<Long>();

        for(int i = 1; i <= 33; i += 2) {
            int k = (int)Math.ceil((double) i / 2.0);
            long max = (long)(Math.pow(4, k) - 1) / 3;
            long t1 = (long)(Math.pow(2, i - 1));
            long t2 = 2 * ((long)(Math.pow(4, k - 1)) - 1) / 3;
            long min = t1 - t2;
            list1.add(min);
            list2.add(max);
        }
        list1.set(0, 0L);

        long t = N;
        int[] bi = new int[33];

        // 長さ2n で表すことができる数値の最小値と最大値
        List<Long> list3 = new ArrayList<Long>();
        List<Long> list4 = new ArrayList<Long>();
        for(int i = 2; i <= 33; i += 2) {
            int k = i / 2;
            long min = -2 * (long)(Math.pow(4, k) - 1) / 3;
            long t1 = -(long)(Math.pow(2, i - 1));
            long t2 = -((long)(Math.pow(4, k)) - 1) / 3;
            long max = t1 - t2;
            list3.add(min);
            list4.add(max);
        }

        while(t != 0) {
            if(t < 0) {
                for(int i = 0; i < list3.size(); i++) {
                    if(list3.get(i) <= t && t <= list4.get(i)) {
                        bi[(2 * (i + 1))] = 1;
                        t = t + (long)(Math.pow(2, 2 * i + 1));
                        break;
                    }
                }
            }else if(t > 0) {
                for(int i = 0; i < list1.size(); i++) {
                    if(list1.get(i) <= t && t <= list2.get(i)) {
                        bi[(2 * i + 1)] = 1;
                        t = t - (long)(Math.pow(2, 2 * i));
                        break;
                    }
                }
            }

        }
        int index = 0;
        for(int i = 0; i < 33; i++) {
            if(bi[i] == 1) {
                index = i;
            }
        }
        for(int i = index; i > 0; i --) {
            System.out.print(bi[i]);
        }
        System.out.println();

    }
}

感想

途中でunratedなコンテストなりましたが、レートだけを考えるとそれで良かったのかもしれないです。

C問題はコンテスト中に解法は思いついたんですが、実装までには至りませんでした。

AtCoder Beginner Contest 105 に参加しよう

雑記

AtCoder Beginner Contest 105

AtCoder Beginner Contest 105 - AtCoder

8月11日 (土曜日) 21:00 にAtCoder Beginner Contest 105が開催されます。

前回はC問題を解くことができなかったので、今回は解けるように頑張ります。

Codeforces Round #502 (Div.1, Div. 2) に参加した感想

Cordeforces Java

問題

codeforces.com

コンテストの途中でトラブルなどがあったので、unratedなコンテストとなりました。

結果はB問題まで解くことができました。初めてコンテスト中にB問題を解くことができたので、進歩だと思います。

続きを読む