Java初心者の競技プログラミング日記

Dvorak配列でjavaを書いてます

yukicoder No.688 E869120 and Constructing Array 2

方針

・0と1の順番は関係ないので、リストに1を適当個詰めたあと、0を適当個詰めて、出力する
・ここでは便宜上、1を「2を作るための数」と定義し、0を「組み合わせを増やすための数」と定義する。
・合計が2になるには、1が少なくとも2個は必要。
 →k=0のときは、0か1をひとつだけ出力すればよい。


1のみで数列を構成した場合

合計が2となる選びかたは……

・11 → 選び方は1通り
・111 → 3通り
・1111 → 6通り
・11111 → 10通り

1のみで配列を構成した場合、合計が2となるような選びかたは、「(1の数)C2」のコンビネーションで求まる。


0のみで数列を構成した場合

数列の部分集合(すべての選びかたの合計)は……

・0 → 選び方は2通り
・00 → 4通り
・000 → 8通り
・0000 → 16通り

0のみで配列を構成した場合、その部分集合の数は「2^(0の数)」で求まる。


1と0から数列を構成する

・1の個数とその選び方 2(1), 3(3), 4(6), 5(10), 6(15)......
・0の個数とその選び方 0(1), 1(2), 2(4), 3(8), 4(16), 5(32)......

たとえば、K=96のとき、1が4個(6通り)、0が4個(16通り)からなる数列を作ることで、題意を満たす数列となります。

K=10のときは1を5個並べればよいですし、K=2のときは1を2個と0を1個並べればよいです。


実装する

まず、k=0の場合は1もしくは0を出力して終わらせます。

次に、数列を1のみから構成した場合の選び方(Key)とその個数(Value)をmapに入れます。
・11 map.put(1,2)
・111 map.put(3,3)
・1111 map.put(6,4)
・11111 map.put(10,5)
・1*30 map.put(435,30) 最大値

もし指定されたkがこのmapのKeyに含まれているなら、そのValueぶんだけ1をリストに追加し、それを出力します。

さて問題は、指定されたkがmapのKeyに含まれていない場合です(2560など)

この場合は、kが(mapのKeyに含まれている数)*(2^n)の形になればよいわけですから、kを手当たり次第にmapのKeyで割っていきます(k/key = dとします)。このdが2^nの形になっているかどうかを確かめ、もしなっているなら、1をvalue回、0をn回リストに追加し、それを出力します。

追記:この方法だと配列の長さが30を超えてしまいそうなので、公式解説にある通り、0と1の個数を全探索するのがよいと思います。


import static java.lang.System.*;
import java.util.*;

public class Main {
	static Scanner sc = new Scanner(System.in);
	public static void main(String[] args) {
		Map<Integer,Integer> map = new HashMap<>();
		for (int i=2; i<=30; i++) {
			map.put(i*(i-1)/2, i);
		}
		
		Set<Long> set = new HashSet<>();
		for (int i=1; i<=28; i++) {
			set.add((long)Math.pow(2,i));
		}
		
		
		List<Integer> ans = new ArrayList<>();

		long n = sc.nextLong();
		
		if (n == 0) out.println(1);
		if (map.containsKey((int)n)) {
			for (int i=0; i<map.get((int)n); i++) {
				ans.add(1);
			}
			printList(ans);
		}
		else {
			for (Map.Entry<Integer,Integer> e: map.entrySet()) {
				int k = e.getKey();
				long d = n/k;
				if (set.contains(d)) {
					
					for (int i=0; i<map.get(k); i++) {
						ans.add(1);
					}
					while (d%2 == 0) {
						d /= 2;
						ans.add(0);
					}
					printList(ans);
					
					break;
				}
			}
		}
	}

	static void printList(List<Integer> list) {
		for (int i=0; i<list.size(); i++) {
			out.print((i==0?"":" ")+list.get(i));
		}
	}
}