解説
, , のすべての組み合わせから値を作っていては、の計算量になり、間に合いません。
代わりに、値から組み合わせを作ることを考えます。これは、なんとで解くことができます。
達成可能である ねこ度をとします。
どの要素, , をとっても、となるように、それぞれの集合, , の中身を削るような手法を取ります。
上位のビット桁から、順番に、現時点での集合(初期の部分集合)の, , において、それぞれ、その桁でが立っている要素の数を数えます。
これが、, , のいずれも空集合でない場合は、今までの条件を満たし、且つこの桁のビットをにできる組み合わせが存在することを意味します。
それに該当しない要素を集合から外して、次に進みます。この一回の処理の実行時間複雑度はです。
このように、貪欲に漸化的に、そのビット桁を立てられるか探索することで、達成可能な最大のねこ度を求められます。
ここから、得られた最大のを作る要素の組み合わせを復元します。値がを構成可能である必要十分条件はです。
簡単な実装の仕方
setなどを活用により、実際に、反復可能な要素列から、要素を選択的に落とすことはできます。
但し、maskといったテクニックを活用することで、実際に要素列を触ることなく、それを再現することができます。
前者がであるのに対し、後者はです。writerは後者の実装方針を採択しています。
提出例(Python)
N=int(input())
A=[]
B=[]
C=[]
for _ in range(N):
a, b, c=map(int, input().split())
A.append(a)
B.append(b)
C.append(c)
mask=0
def check(K):
found=False
for k in K:
if (k & mask)==mask:
found=True
return found
for i in range(20, -1, -1):
mask+=(1<<i)
valid=check(A) and check(B) and check(C)
if not valid:
mask-=(1<<i)
def index(K):
for i in range(N):
if (K[i] & mask)==mask:
return i+1
assert False
print(index(A), index(B), index(C))
ユーザー解説
ユーザー解説を書くユーザー解説はまだありません。