AtCoder Beginner Contest 105 の感想
問題
Tasks - AtCoder Beginner Contest 105
結果はB問題まで解くことができました。
A - AtCoder Crackers
なら全員に同じ枚数のおせんべいが行き渡ります。そうでない場合は、差は となります。
B - Cakes and Donuts
を満たす正の整数 が存在するかという問題です。
数学的には下のサイトで解説されています。
の最大値は なので、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
考え方
が2進数で何桁になるかを考えます。ここで桁とはビット列の長さを表すものとします。ここで、ビット列の長さを とします。
長さ で表すことができる数の範囲を考える
ビット列において、奇数番目の符号は正となり、偶数番目の符号は負となることに注意します。
また、最高位のビットは必ず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問題はコンテスト中に解法は思いついたんですが、実装までには至りませんでした。