ABC197 C - ORXOR

질문 링크
이 문제를 해결하려면 구체적으로 다음과 같은 정진이 필요하다

XOR 연산 가능

제한에서 비트 전체 검색을 의식

bit의 모든 검색이 그룹인 것을 이해

정보 1

XOR, OR 계산에 관해서는 처음에는 경원하고 싶었지만 계산만 했다면 사칙과 같은 연산을 했기 때문에 심리 블록을 해소해야 한다.
구체적으로 다음과 같은 문제를 해결해 보세요. 습관이 되세요.
XOR Circle

관2

제약에서 해법을 짜내는 것이 중요하다고 하지만 구체적으로 말하면 아래의 절차를 밟고 마음속으로 제약을 받아들이는 것이 중요하다.처음에 저는 제약을 보지 않고 자유롭게 순환하며 교류했습니다. 지금은 제약을 자주 보고 제약을 보면 경기 프로그램 설계의 본질이라고 생각합니다. 그래서 지금까지 이 점을 의식하지 못했다면 이를 의식하기 위해 열심히 전진하는 것이 좋다고 생각합니다.
구속과 계산량의 중요성을 이해하다

AC 문제를 해결하기 위해 적절하게 순환

TLE 문제를 해결하기 위해 적절하게 순환

TLE 수정을 위해 적당한 몇 배 개선(continue 또는 break 중도정지 등)을 시도했지만 특별한 해결이 없었다

TLE를 수정할 때 계산량을 개선해야 한다는 것을 배웠다.
구체적으로 어떻게든 이중순환이 이뤄져야 하는 상태에서 O(N^2)를 O(N)로 바꾸면 해결할 수 있다는 경험이 있다.그리고 아무것도 안 되는 게 아니라는 걸 이해합니다. N<=10^6이면 O(N^2)가 늦고 순환만 하면 늦지 않습니다.즉, N의 값에 따라 O(N^2)도 가능하고, 이번처럼 N<=20이면 O(2^N)도 가능하니 여러분이 납득할 수 있도록 계속 노력하겠습니다.이 점을 이해하면 몇 개의 학문처럼 보이지만 실제로는 모두 탐색할 때 따라잡는 문제라고 냉정하게 생각할 수 있다.또 B문제가 자주 제기되는 문제, 문제문은 야마로 보이지만 제약을 보면 두 개의 순환으로 전체 탐색을 하면 늦지 않은 문제, 그런 생각이 없다면 수학처럼 계산량을 O(1)로 고려하는 등 불필요한 일을 할 수 있어 불안정해질 수 있다.의식적으로 제약에 따라 이 문제는 전체적인 탐색을 할 수 없고 순환하면 여러 번 순환할 수 있다.

정보 3

N<=20이라면 모든 탐색을 생각할 수 있는 난이도가 그리 높지 않다.그러나bit 전체 탐색은 문제에 적용되는 난이도가 높다고 생각합니다.비트 전체 탐색 기사를 보면 비트가 서 있는 것, 선택, 선택하지 않는 것 같은 설명이 자주 나오는데 자꾸 알겠지만 금방 잊어버리는 일이 생긴다.비트 탐색을 이해하기 위해 가장 중요한 것은 비트 탐색은 그룹을 나누는 것이다.A, B, C, D, E 등 5명이 있다면 조합이 분류한 모든 모델을 열거하는 것이 우리의 본질이라는 것이다.
다음 코드가 자주 표시됩니다.

if bit & (1 << i):
  当てはまる場合の処理

이 항목만 적용할 수 없습니다.중요한 것은

if bit & (1 << i):
  当てはまる場合の処理
  当てはまる人はこっちのグループ
else:
  当てはまらない場合の処理
  当てはまらない人はこっちのグループ

이렇게else도 초점이 된다.즉, [A, B]로 선정되면else가 [C, D, E]라는 조합이 있다는 것을 이해하는 것이 중요하다.
아무래도 인상인 것 같아 if bit &(1이번 문제는 간격을 설정하는 것을 금방 알 수 있을 것 같아서bit 전체 탐색이 완성될 것 같다.하지만 비트 탐색을 어떻게 활용해야 하는지는 솔직히 인상을 남기기 어렵다.이것을 연상시키려면 조를 나누는 것을 생각해야 한다.칸막이를 놓는 것은 원래 그룹을 나누기 쉽다는 인상이지만 칸막이의 배치 방식으로 그룹을 나누고 싶다면 =>bit 전체 탐색을 통해 그룹을 나눌 수 있기 때문에 칸막이로 생각하면 된다.
하지만 비트가 서 있으면 분리된 것으로 보더라도 분리된 것으로 판단할 수밖에 없다.거기서 중요해진 건 아까 엘세야.칸막이가 등장할 때마다 그룹이 분리되기 때문에 비트가 일어나지 않았다면(칸막이 아님), 즉 엘즈의 경우 같은 조에 속한 사람이라고 볼 수 있다.
따라서 아래와 같이 else에 같은 그룹에 들어가는 처리를 적으세요.

if bit & (1 << i): 
  # 仕切りがある時の処理
else: #仕切りではない場合は同じグループに属する
  children.append(A[i])

하지만 자세히 말하면 칸막이가 있을 때도 같은 단체에 소속시켜야 하지만 여기서는 본질이 아니기 때문에 사랑을 끊을 거예요. 하지만 엘스의 중요성을 알아야 한다고 생각해요.코드의 양이 모두 있는 사람은 평어가 쓰여 있기 때문에 저쪽을 참조하세요.
이외의 말도 (bit>>i) & 1의 문법이 있다
나는

for bit in range(1 << N):

중의 1<코드의 총량은 다음과 같다.
이것은 채식비단으로 해결할 수 있는 문제다.(단지 나는 경기에서 비트 전체 탐색을 통해 풀지 않고 모든 모드, itertools의combination을 사용했다.)

N = int(input())
A = list(map(int, input().split()))

mn = float('inf')
for bit in range(1 << N):
  parent = [] # 区分けを束ねる大元のGroup
  children = [] #区分けごとのGroup
  for i in range(N):
    if bit & (1<<i): #bitが立ってる場合は仕切りと考えるが、その仕切がある値もグループには入れる
      children.append(A[i])
      parent.append(children) #parentがchildrenのグループを仕切りごとに持つ
      children = [] #仕切りができたら次のグループのために初期化
    else: #bitがたってない場合は同じグループ
      children.append(A[i])
  #上のループの一番最後がbit立っていない(else)の場合、parentに入れれていないので、入れる
  #別にlen(children) >=1 じゃなくて空配列が入っても答えには影響しない
  if len(children) >= 1: 
    parent.append(children)
  
  ORs = []
  for children in parent: #できたグループごとにそれぞれOR演算
    base = 0 #0と比べるので良い
    for child in children:
      base |= child #OR演算
    ORs.append(base)

  base = 0 #0と比べるので良い
  for e in ORs:
    base ^= e #XOR演算
  mn = min(mn, base)

print(mn)