hotpepsiの練習帳

SRM 699

13:59

https://competitiveprogramming.info/topcoder/srm/round/16803/div/1

Div1 Easy (250) OthersXor

問題

• N匹の狼がいる
• それぞれの狼は0から2^30-1までの任意の数値を選ぶ
• それぞれの狼は、情報を開示しないか、あるいは、自分以外の全ての狼の数値のXORを開示する
• 開示された情報が正しい場合、狼の数値の合計の最小値を求める
• 開示された情報に一貫性がない場合は-1とする

方針

• (終了後)
• いろいろな方々の解説を読む
• ビット毎に独立して考えていい
• 非開示のものは任意として扱えるので除外して考える
• 元の値をW[i]、XORの値をX[i]、W[i]の全てのXORの値をSとする
• X[i]==0の個数をC0、X[i]==1の個数をC1とする
• Xの全てのXORは、全ての値をN-1回XORした値と等しいので、Sになる
• W[i]^X[i]==Sなので、W[i]==W[j]ならX[i]==X[j]
• つまりW[i]==0の個数はC0かC1、W[i]==1の個数はC1かC0 (Wの全ビットを反転すると個数が逆転する)
• Sが0になるときと1になるときで場合分け
• Sが0のとき
  • Wについて、0の個数は何個でもいいが、1の個数は偶数であること
  • W[i]==1のX[i]は、自分以外の1は奇数なので、1になる
  • C1が偶数になり、これが必要条件
• Sが1のとき
  • Wについて、0の個数は何個でもいいが、1の個数が奇数であること
  • W[i]==1のX[i]は0になる
  • C0が奇数になり、これが必要条件
• C1が偶数のとき
  • C1を1の個数と仮定できる
• C1が奇数で、非開示が1個以上あるとき
  • C1+1を1の個数と仮定できる
• C0が奇数のとき
  • C0を1の個数と仮定できる
• C0が偶数で、非開示が1個以上あるとき
  • C0+1を1の個数と仮定できる
• 1の個数の条件を満たさなければ一貫性がない
• 1の個数は複数の可能性があるが、最小のものを採用する
• 1の個数×ビットマスクの値が、そのビットの合計の最小値
• https://github.com/firewood/topcoder/blob/master/srm_6xx/srm_699/OthersXor.cpp

結果

--- 0pt

全体が満たすべき性質を考える必要があった。

https://togetter.com/li/1029558