ZONeエナジープログラミングコンテスト “HELLO SPACE” C - MAD TEAM

問題

考察

基本方針は
5種類すべての能力がチーム全体として $X$ 以上にできる3人の組み合わせが存在するかを二分探索で探っていく。

3人のチーム全体の各能力は以下の通り、3人の能力の最大値となる。
$A_{max} = max(A_1, A_2, A_3)$
$B_{max} = max(B_1, B_2, B_3)$
$C_{max} = max(C_1, C_2, C_3)$
$D_{max} = max(D_1, D_2, D_3)$
$E_{max} = max(E_1, E_2, E_3)$

そして、チームの総合力は以下の通り、チーム全体の各能力の最小値となる。
$min(A_{max}, B_{max}, C_{max}, D_{max}, E_{max} )$

各能力において、3人の内いずれかの能力が $X$ 以上であれば、チームの総合力として $X$ 以上になることが確定する。
例えば、パワーの場合は
$A_2$ のみ $X$ 以上であれば、他の $A_1,A_3$ は $X$ より小さいということなので、
$A_{max} = A_2$ となり、 $A_{max}$ が $X$ 以上の値になるということである。
あとは他の能力についても同様に言える。

これらのことから $X$ について二分探索出来そうなことが分かる。

あとは任意の3人の組み合わせで
5つある各能力のチーム全体の値が $X$ 以上にできるかを確認するのだが、
各能力について、 $X$ 以上にできるか出来ないかの01の状態を持つことで確認することができる。

N人の各メンバーについて、各能力について $X$ 以上にできる、できないの状態を5桁のビットで持ち、できる場合は1、できない場合は0とする。
（例えば01010だと、スピードと知識については $X$ 以上にすることできる）
なので3人のビット状態を合わせて11111にすることが出来れば、チームの総合力を $X$ 以上にできる。

単純にN人のメンバーから3人分のビット状態を合わせて確認すると $O(N^3)$ で間に合わないが、
ビットの状態数は $2^5$ 程度しかなく、同じビット状態のメンバーを選んでも、合わせたビット状態が変化せず無駄になってしまうので
N人それぞれにビット状態を持たせるのではなく、ビット状態のみに着目して
特定のビット状態にできるメンバーがいるかどうかを情報として持つ。
（具体的にはビット状態をSetで管理するようなイメージ）
これで高々 $O((2^5)^3)$ 程度の計算量で3人分のビット状態を合わせて確認することができる。