ステップ1：ネックレスの種類数は \(O(3^{\frac{N}{3}})\)

色 \(c\) の宝石の個数を \(n_c\) とします。ネックレスの種類数は \(n_c\neq 0\) であるような全ての \(c\) についての積 \(\prod_{c}n_c\) です。この値がどのくらい大きくなるかを考えてみましょう。すなわち、\(\sum_c n_c=N\) の条件下での \(\prod_c n_c\) の最大化を考えます。

もし、\(N\neq 1\) の場合に \(n_c=1\) となる \(c\) が存在するとき、\(1+x>1\times x\) であることから、その宝石をすでに存在する別の色に塗り替えることで、ネックレスの種類数を増やすことができます。したがって、最適解において \(n_c=1\) となる \(c\) は存在しません。
もし \(n_c=2\) であるような \(c\) が \(3\) 個以上存在するとき、\(3^2\gt 2^3\) であることから、\(2\) 個ずつ \(3\) 色の \(6\) 個の宝石を \(3\) 個ずつ \(2\) 色に塗り替えることで、ネックレスの種類数を増やすことができます。したがって、最適解において \(n_c = 2\) となる \(c\) は高々 \(2\) 個しか存在しません。
もし \(n_c\geq 4\) であるような \(c\) が存在するとき、\(2(n_c-2) \geq n_c\) であることから、\(2\) 個を新たな色に塗り替えても、ネックレスの種類数は減りません。したがって、最適解において \(n_c \geq 4\) となる \(c\) は存在しないとしてよいです。
以上から \(N\geq 2\) における最適解は、\(n_c=2\) となる \(c\) が \(2\) 個以下ある他は全て \(n_c=3\) となることがわかります。\(N\) を \(3\) で割ったあまりに基づいて場合分けすることで冒頭の主張が示せます。

ステップ2：半分全列挙+二分探索

ネックレスの種類数 \(\prod_c n_c\) を \(P\) とします。ステップ 1 の結果から \(P\leq 4\times 3^{22} \leq 1.3\times 10^{11} \) と比較的小さいことがわかりました。このため、この問題は以下のように半分全列挙により解くことができます。

\(\prod_{c\in A}n_c\) と \(\prod_{c\in B}n_c\) がおよそ等しくなるように、色を \(2\) つの disjoint な集合 \(A,B\) に分け、\(A,B\) に属する色の宝石を選ぶ方法を \(\prod_{c\in A}n_c\), \(\prod_{c\in B}n_c\) 通りそれぞれ列挙し、\(\{A_i\},\{B_i\}\) とします。これは\(O(3^{\frac{N}{6}})\) でできます。\(\{B_j\}\) を binary trie で持っておくことで、任意の \(x,i\) に対し \(A_i \ {\rm XOR}\ B_j \geq x\) を満たす \(j\) の個数を \(O(\log V)\) で取得することができます。したがって、答えを二分探索することで \(O(3^{\frac{N}{6}} (\log V)^2)\) によりこの問題を解くことができます。しかし、C/C++などの高速な言語を用いても実行時間制限に間に合わせるのは難しいでしょう。

ステップ3：計算量の削減

答えを上のbitから決めていく二分探索においては、各 \(A_i\) でbinary trie の同じノードを繰り返し辿っているため無駄があります。二分探索の前のステップですでに見たノードの続きから調べることで、各 \(A_i\) に対して二分探索全体で \(O(\log V)\) の計算量となり、全体で \(O(3^{\frac{N}{6}} \log V)\) となります。

なお、実際に binary trieを構築するのではなく、「今見ているノード以下に存在する \(\{B_j\}\)」と「そのノードに到達する \(\{A_i\}\)」の組を持つことで実装が容易になります。

実装例(Python)