👋

ABC197 C - ORXOR

2021/03/28に公開

競技プログラミング

AtCoder

tech

問題のリンク

この問題を解ける様になるには具体的に以下の精進が必要です

XOR, OR演算になれる
制約からbit全探索を思いつけるようにする
bit全探索はグループ分け、という理解をする

1について

XOR、OR計算については、始めたての頃は敬遠したくなりますが、計算だけですと、四則演算と同じですので、メンタルブロックを解除するようにします。
具体的には、以下の問題を解いてみて、慣れましょう。
XOR Circle

2について

制約から解法を絞るのが大事とよく言われますが、具体的に以下のステップを踏んで、制約を見るのが大事というのを心の底から納得するようにしましょう。はじめ、私は制約を見ずに適当にループ回してACしていましたが、今となっては制約を常に見るようになり、制約を見ることが競技プログラミングの本質とまで思うようになりましたので、今までそこまで意識していなかった場合は、意識できるよう、精進をするかと良いと思います。

制約、計算量の大事さを理解するステップ

適当にループ回してACする問題を解く
適当にループ回すとTLEする問題を解く
TLEを直すために、適当に定数倍改善を試みる (continueやbreakで途中で止める等)が特に解決しないことを経験する
TLEを直すためには計算量の改善が必要であるということを学ぶ。
具体的には、どうしても二重ループになるなあ、という状態で、O(N^2)をO(N)に直せば解決できるといったようなことを、経験します。また、何でもかんでもO(N^2)がだめというわけではなく、N <= 10^6だと O(N^2)が間に合わず、1重のループだと間に合うといったことを理解します。つまり、Nの値によっては、O(N^2)でも良いし、今回のように、N<=20だと、O(2^N)でも良いということを、納得できるように精進しましょう。これが理解できるようになれば、数学問のように見えて、実は全探索で間に合った、といったような問題に対して、冷静に考える事ができるようになります。また、B問題でありがちな、ちょっと問題文がややこしそうに見えるが制約を見ると二重ループで全探索すれば間に合うという問題の場合、この考え方が無いと、数学問のように、計算量をO(1)で考える等、その問題に必要でないことをしかねないので、安定しなくなります。意識的に、制約をみて、この問題は全探索ができるできない、ループなら何重ループまで可能、といったことを判断できるよう、精進しましょう。

3について

N <= 20ならbit全探索を思い浮かべるのはそこまでハードルは高くないです。しかし、bit全探索を問題で適用するのはハードルが高いと思います。bit全探索の記事をみてみると、bitが立っているのをみて、選ぶ、選ばない、といったような説明がよく出てきて、何となく分かるがすぐに忘れるといったことがあると思います。bit全探索を納得するために一番大事だと思っているのは、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 << i)だけをみて覚えると、使うところまで理解ができないので、コンテストで使いたくても、使えません。なぜなら、実際のコンテストでは、elseの方も書かないといけない場面もあり、その部分の理解が浅いと、本番で結局よくわからなかった、ということになると思います。

今回の問題でいうと、仕切りを置くのはすぐにわかりそうで、なんとなくbit全探索でできそうだ、というのもわかるかと思います。ただ、bit全探索をどのように適用するのかは正直イメージがつきにくいと思います。これをイメージできるようになるには、グループ分けを思い出します。仕切りを置くということはそもそもがグループ分けっぽいイメージではありますが、仕切りの置き方でグループ分けをしたい => bit全探索はグループ分けができるので、それを仕切りと考えたらいけるのでは、となります。

しかし、bitが立っている場合、仕切りと考えるにも、それだと仕切りしか判断できないのでは、となります。そこで大事となってくるのが、先程のelseです。仕切りが登場するごとに、グループが区切られるのですから、bitが立っていない (仕切りではない)場合、つまり、elseの場合は、同じグループに所属する人と考えることができるのです。
なので、以下のように、elseで同じグループに入れる処理を書きます。

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

ただ、細かくいうと、仕切りがある時の場合も、同じグループに所属させないといけないですが、それはここでは本質ではないので割愛しますが、elseの大事さがわかるかと思います。コード全量の方に、コメントを書いていますのでそちらをご参照ください。

余談ですが、(bit >> i) & 1 という書き方もありますが、

for bit in range(1 << N):

の1<<Nを揃えるほうが、忘れにくいと思いますので、個人的には、bit & (1 << i)で覚えるほうが混乱しなくて良いと思っております。

コード全量は以下です。
精進の組み合わせで解ける問題です。(ただ私は、コンテストでbit全探索では解けず、仕切りを全パターン、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)

1について

2について

3について

Discussion