問題 A’ の解法

「\(X\) 回開催できるが \(X+1\) 回は開催できない」ような \(X\) を求めれば良いです。

\(X\) 回開催できるかの判定は以下のような貪欲法で判定できます。

• \(i=K-1, \dots ,2,1\) の順に以下を行う。
  • 「\(2^i \le A_j\) なる \(j\) を \(1\) つ選び、\(A_j\) から \(2^i\) を引く」を \(X\) 回繰り返す。
  • そのような \(j\) が存在しない場合は不可能。

（予選 B のように下の桁から取っていくことでも判定できますが、その方針だと数え上げが難しいと思います。）

数え上げ

問題 A’ の答えが \(X\) 以上であるような \(A\) の個数を \(f(X)\) として、\(f(X)-f(X+1)\) を求めれば良いです。

ただし、この定義では \(f(X)\) は無限になってしまうので、\(A_i \lt 2^{(K+10)}\) という制約をつけます。

上記の貪欲法を少し整理します。

• 各 \(A_i\) を \(2\) 冪の和に分解（二進表記で \(1\) の桁を取り出すイメージ）し、それらの多重集合を \(S\) とする。
• \(i=K+9,\dots,2,1\) の順に以下を行う
  • \(i \lt K\) の場合、\(S\) から \(2^i\) を \(X\) 個取り除く
  • その後、\(S\) から \(2^i\) を全て取り除き、その倍の個数の \(2^{i-1}\) を追加する

これを元にすると以下のような dp で \(f(X)\) を求めることが出来ます。

• \(dp[i][j] =\) 各 \(A\) を（二進表記で）\(i\) 桁目まで決め、\(S\) に \(2^i\) が \(j\) 個あるような場合の数

\(2^i\) が \(2X\) 個以上になると常に判定が true になることを考えると、\(j\) は \(2X\) との min を取ればよいことが分かります。

計算量は \(O(NKX)\) です。