【今日の精進】ARC100E - Or Plus Max

毎日格上の問題を倒すやつの57日目です。

問題リンク

atcoder.jp

問題概要

を満たすすべての に対して、 となるような に対する の総和の最大値を求めてね。

解法

とりあえず、 のビットが立っている場所と同じ場所にしかビットが立っていないものを考えたくなります。

そしてこれは、高速ゼータ変換そのものです。やることは単純で、上位2つをモノイドとするだけです。

あとは累積maxをとればよいです。

提出コード

INF=pow(2,61)-1
N=int(input())
A=list(map(int,input().split()))
for i in range(1<<N):
    A[i]=[A[i],-INF]
for i in range(N):
    bit=1<<i
    for j in range(1<<N):
        if bit&j:
            A[j]=sorted(A[j]+A[j^bit],reverse=True)[:2]
ans=-INF
for i in range(1,1<<N):
    ans=max(ans,sum(A[i]))
    print(ans)

Submission #47606011 - AtCoder Regular Contest 100

感想

あまりにも知識ゲー