Dwango Programming Contest V / 第5回ドワンゴからの挑戦状予選 B - Sum AND Subarrays

Dwango Programming Contest V / 第5回ドワンゴからの挑戦状予選 B - Sum AND Subarrays
B - Sum AND Subarrays
を解いた。
公式解説はこれ
https://img.atcoder.jp/dwacon5th-prelims/editorial.pdf。

bit演算系の問題は苦手だけど、初めてコンテスト中に解けた。
理解の整理のために解説を書くことにした。

解説

bit演算といえば、2進数表示の各桁ごとに見るのがよくある。
一般に、ピッタリの値を求めるよりも以上の値を確認するほうが"楽"らしい。
これを前提に考えると、 $2^n$ を考えるのが良さげに見えてくる。
特に、大きい桁から決めていけばいいことが分かる。
というのも、
$2^n > \sum_{k=1}^{n-1}2^k$
なので、上の桁を確定した後に、それ以下の桁で数の大きさが逆転されることがない。
例えば、

10000  01111

では、10000 の方が大きい。
というわけで、上の桁から決めていこう。
$N \leq 1000$ と $a_i \leq 10^9$ なので、部分列の和は高々 $10^{12}$ である。
ここで、
$\log_2(10^{12}) = 39.86313713864835 \cdots$
なので、 $2^{40}$ くらいまで考えれば良い。

次に、 $2^k$ 桁目を確定する方法を解説する。
非負整数 $x$ が与えられたとき、 $x$ の 2進数表示において、 $2^k$ が $1$ であることは、
$x \, mod \, 2^{k+1} \geq 2^k$
と同値です。
というわけで、 $K$ 個以上の部分列に対して、上記の条件が満たされることを確かめれば良い。
あとは、プログラムの中に説明をかく。

from itertools import accumulate
N, K = map( int, input().split())
A = list( map( int, input().split()))
accA = [0] + list( accumulate(A))
V = [1]*(N*(N+1)//2)
ans = 0
check = False
for i in range(40,-1,-1):
    W = [0]*(N*(N+1)//2)
    for l in range(N):
        for r in range(l+1,N+1):
            if V[l*(2*N+1-l)//2+r-l-1] == 0:#Vは現時点で採用されている部分列を示している
                #l*(2*N+1-l)//2+r-l-1はVの大きさに合わせて何番目を更新するか決定した。(時間節約のため)
                continue
            if (accA[r]-accA[l])%(2**(i+1)) >= 2**i:
                W[l*(2*N+1-l)//2+r-l-1] = 1
    if check == False:#初めに並ぶ 0 を無視するため
        if sum(W) >= K:
            check == True
        else:#無視して次のloopに遷移する
            continue
    if sum( V and W) >= K:#すでに確定している部分列と合わせて、K個以上あれば2**i桁目を採用する
        #V and W はlistの各成分のbool値の論理積を取っている
        ans += 2**i
        V = V and W
print(ans)