牛客小白月赛138 C - AND and OR
- サイト
- NowCoder
- コンテスト
- 牛客小白月赛138
- 問題
- C - AND and OR
長さ の非負整数列 と非負整数 が与えられます(、)。
を満たす があれば 1 つ出力し、なければ を出力してください( の総和 )。
AND と OR の和は普通の和
Section titled “AND と OR の和は普通の和”実は、どんな非負整数 についても
が成り立ちます。ビットごとに確かめると分かります。各ビットについて、 と のそのビットの組み合わせは次の 3 通りです。
| のビット | AND | OR | AND + OR | |
|---|---|---|---|---|
| 両方 | ||||
| 片方だけ | ||||
| 両方 |
どのビットでも AND と OR の寄与の和が と の寄与の和に一致するので、全体でも等しくなります。
したがって、問題は「 となる を 1 つ見つけよ」という、よくある問題に言い換えられます。
和が になるペアを探す
Section titled “和が kkk になるペアを探す”の組を値でソートしておきます。各要素 について、相手の値 が列にあるかを二分探索で調べます。見つかった相手が自分自身でなければ、そのペアが答えです。
のときは、二分探索で見つかる最初の要素が自分自身になることがあります。ただ、同じ値がもう 1 つあれば、その要素を見たときに最初の要素が相手として見つかるので、取りこぼしはありません。
計算量はソートと二分探索で です。
Python
import bisectfor _ in range(int(input())): N, K = map(int,input().split()) A = list(map(int,input().split())) Ai = [(A[i],i) for i in range(N)] Ai.sort() for i in range(N): j = bisect.bisect_left(Ai,(K-Ai[i][0],-1)) if 0<=j<N and i!=j and K-Ai[i][0]==Ai[j][0]: print(*sorted((Ai[i][1]+1,Ai[j][1]+1))) break else: print(-1)Ai は (値, 元の添字) の組をソートしたものです。(K-Ai[i][0],-1) で bisect_left すると、値が 以上である最初の位置が求まります。添字は 以上なので、第 2 要素に を入れておけば、値が の組より必ず前に来ます。出力は の順にする必要があるので、元の添字をソートしてから出力しています。