外部サイトへ移動します

リンク先の URL を確認してから開いてください。

別タブで開く

解説

M - You were a Cat All Along

作成者 nekooooooo、siooisi、jammy、trueryob

テスター jammy、nekooooooo、siooisi、tau0529

配点 425 点

実行時間制限
2.2 秒
メモリ制限
222 MiB

解説

AA, BB, CCのすべての組み合わせから値を作っていては、O(N3)O(N^3)の計算量になり、間に合いません。

代わりに、値から組み合わせを作ることを考えます。これは、なんとO(Nlog⁡V)O(N \log{V})で解くことができます。

達成可能である ねこ度をKKとします。

どの要素a∈Aa \in A, b∈Bb \in B, c∈Cc \in Cをとっても、K∧(a∧b∧c)=KK \land (a \land b \land c) = Kとなるように、それぞれの集合AA, BB, CCの中身を削るような手法を取ります。

上位のビット桁から、順番に、現時点での集合(初期の部分集合)のAA, BB, CCにおいて、それぞれ、その桁で11が立っている要素の数を数えます。

これが、AA, BB, CCのいずれも空集合でない場合は、今までの条件を満たし、且つこの桁のビットを11にできる組み合わせが存在することを意味します。

それに該当しない要素を集合から外して、次に進みます。この一回の処理の実行時間複雑度はO(N)O(N)です。

このように、貪欲に漸化的に、そのビット桁を立てられるか探索することで、達成可能な最大のねこ度を求められます。

ここから、得られた最大のKKを作る要素の組み合わせを復元します。値xxがKKを構成可能である必要十分条件はx∧K=Kx \land K = Kです。

簡単な実装の仕方

setなどを活用により、実際に、反復可能な要素列から、要素を選択的に落とすことはできます。

但し、maskといったテクニックを活用することで、実際に要素列を触ることなく、それを再現することができます。

前者がO(Nlog⁡N)O(N\log N)であるのに対し、後者はO(N)O(N)です。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))

ユーザー解説

ユーザー解説を書く

ユーザー解説はまだありません。