Hatena::Grouptopcoder

hotpepsiの練習帳

2016-12-31

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

トラックバック - http://topcoder.g.hatena.ne.jp/firewood/20161231