ABC197 C - ORXOR

備忘録

問題

atcoder.jp

回答

import sys
import os
import math
import bisect
import itertools
import collections
import heapq
import queue
import array
import time
import datetime

# 時々使う
# import numpy as np
# from decimal import Decimal, ROUND_HALF_UP
# from scipy.sparse.csgraph import csgraph_from_dense, floyd_warshall

# 再帰の制限設定
sys.setrecursionlimit(10000000)


def ii(): return int(sys.stdin.buffer.readline().rstrip())
def il(): return list(map(int, sys.stdin.buffer.readline().split()))
def it(): return tuple(map(int, sys.stdin.buffer.readline().split()))
def fl(): return list(map(float, sys.stdin.buffer.readline().split()))
def iln(n): return [int(sys.stdin.buffer.readline().rstrip())
                    for _ in range(n)]


def iss(): return sys.stdin.buffer.readline().decode().rstrip()
def sl(): return list(map(str, sys.stdin.buffer.readline().decode().split()))
def isn(n): return [sys.stdin.buffer.readline().decode().rstrip()
                    for _ in range(n)]


def lcm(x, y): return (x * y) // math.gcd(x, y)


# MOD = 10 ** 9 + 7
MOD = 998244353
INF = float('inf')


def main():
    if os.getenv("LOCAL"):
        sys.stdin = open("input.txt", "r")

    N = ii()
    A = il()
    ret = INF
    for i in range(0, 1 << N, 2):
        k = 0
        L = []
        # bit全探索で、全ての区間に対して
        # その区間で分けるか否かを判定する
        for j in range(1, N+1):
            if (i >> j) & 1:
                o = 0
                # 分けた区間のor演算
                for a in A[k:j]:
                    o |= a
                k = j
                L.append(o)
        else:
            o = 0
            # 分けた区間のor演算
            for a in A[k:]:
                o |= a
            L.append(o)

        # or演算の結果をxor演算
        ans = 0
        for l in L:
            ans ^= l
        ret = min(ret, ans)
    print(ret)


if __name__ == '__main__':
    main()

考え方

区間分けを全通り試して、
演算結果を求めます。

ある要素とある要素の間で分けるか否かをbit全探索で判定して、
区間分けを行うことが出来るパターンを全て求めます。
あとは区間分けした要素をor演算して、結果をさらにxor演算するだけです。

上記の回答例は実装がよくないため、Python (3.8.2)で提出すると制限時間超過となります。
PyPy3 (7.3.0)で400ms前後