競技プログラミング

Codeforces Round 685 (Div. 2) E Bitwise Queries

問題概要

リンク: https://codeforces.com/contest/1451/problem/E1
インタラクション問題
整数配列の異なる二数の AND, OR, XOR のいずれかを回聞くことで配列自体を特定する。
制約: ,

key



解法 1(Easy)

想定解.
より
, , が 6 回の query でわかるのでが特定できる。
ここでよりこれを 5 回に削減可能. 残りの要素は前の要素との XOR を調べることで判定できる。
最後の削減ができず…

解法 2(Easy)

解答: (https://codeforces.com/contest/1451/submission/99209729)
コンテスト後, これで解いた. hard の想定解の一部に似ている。
以降の qbit 目をとする. は 1 か 0 のいずれかである。 ここでがわかっていると仮定すると b_2 はとの XOR より判定できる。
以降 nbit 目まで XOR をとっていくことで配列 b がが 1, 0 の２つの場合で定まる。よってこれまでに必要な query は n-1 回. 残り 3 回の query でが特定できれば解ける。

  1. の場合
    {} = {0, 0} or {1, 1}なのでについて AND を取れば ok
  2. かつの場合
    について AND を取れば ok
  3. かつの場合
    について AND を取れば ok

以上より事前に{}, {}, {}それぞれの AND 取得しておけば n+2 回で解ける。
時間計算量:

解法 1(Hard)

上記解法 2(Easy)の XOR は順番に取る必要はなく, 全てととっても ok

  1. に被りがある場合, との XOR が同一となった数は同一なのであとは XOR をたどることで n 回で ok
  2. 被りがない場合, a には 0 から n-1 のすべての値が含まれる。 ここでになるような i は必ず存在し, このとき, よって AND が分かり, 一つ減らすことができる。