O(3^N) のビット DP 入門 CoffeeScript(Beta)編（paizaランク A 相当）
問題にチャレンジして、ユーザー同士で解答を教え合ったり、コードを公開してみよう！
下記の問題をプログラミングしてみよう！
paiza 大学院には N 人の学生がいます。
人 i には整数 A_i が割り当てられています。
いまから N 人を 1 つ以上のいくつかのグループにわけます。
グループ j に属している人の集合を S_j = {i_1, i_2, ... , i_{c_j}} とします。ここで、c_j はグループ j の人数を表します。
このとき、グループ j の相性は Z_{S_j} := (A_{i_1} XOR A_{i_2} XOR ... XOR A_{i_{c_j}}) × c_j として定義されます。
どの人も必ず 1 つのグループに属さなければなりません。
すべての人のグループ分けが終わった後、各グループの相性の総和 Σ Z_{S_j} の最大値を求めてください。
入力例 1 を説明します。
グループ 1 を {人 1, 人 2, 人 4}、グループ 2 を {人 3} とします。
このとき、グループ 1 の相性は (1 XOR 2 XOR 4) × 3 = 21、グループ 2 の相性は 3 × 1 = 3 であり、相性の総和は 24 です。
相性の総和を 24 より大きくすることはできないので、24 を出力します。
- 入力される値
-
入力は以下のフォーマットで与えられます。
N
A_1 A_2 ... A_N
・ 1 行目には、学生の数を表す整数 N が与えられます。
・ 2 行目には、数列 A が与えられます。
・ 入力は合計で 2 行からなり、入力値最終行の末尾に改行が 1 つ入ります。
入力値最終行の末尾に改行が１つ入ります。
文字列は標準入力から渡されます。 標準入力からの値取得方法はこちらをご確認ください
- 期待する出力
各グループの相性の総和 Σ Z_j の最大値を求めてください。
末尾に改行を入れ、余計な文字、空行を含んではいけません。
- 条件
-
すべてのテストケースにおいて、以下の条件をみたします。
・ 1 ≦ N ≦ 12
・ 0 ≦ A_i < 2^50
- 入力例1
-
4
1 2 3 4
- 出力例1
-
24
- 入力例2
-
3
7 4 3
- 出力例2
-
21
- 入力例3
-
12
68504118415765 90474570101523 922563537824190 420046408417988 499272973328355 220164565273819 646963944280525 228525537462380 130425130971069 1070794804905576 805739339007659 915883642657565
- 出力例3
-
13508615999493192
