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)); } } }