Hatena::Grouptopcoder

hotpepsiの練習帳

2016-12-24

SRM 694

00:27

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

Div1 Easy (250) TrySail

問題

  • N人の生徒がいる
  • 各生徒の強さが非負の整数で与えられる
  • 3グループにわける
  • 各グループの強さは、グループ内の生徒の強さのXORである
  • 3グループの強さの最大値を求める

方針

  • DPっぽい全列挙
  • 最大でも255までしかないので、到達する可能性のある値を全て列挙する
  • グループ3の値はグループ1と2の値から求まるので、256^2を調べれば良い(グループ1にも2にも所属しない人は3にいるものとして扱う)
  • dp[i番目の生徒][グループ1][グループ2] = 到達可能性(0: 不可能、1: 可能)
  • 最後に、到達可能性のある値から最大値を求める
  • Passed System Test
  • htts://github.com/firewood/topcoder/blob/master/srm_6xx/srm_694/TrySail.cpp

結果

o-- +1 110.22 + 50 = 160.22pt 177th/358 rating 1478 -> 1500 (+22)

なんとか解いて黄色復帰。

必ず3チームにわかれると考えて良い。なぜなら、2チームにわけてから、誰か一人を3チーム目に行かせても、合計は同じか大きくなるかのどちらかで、3チームにわけて損することはないため。


http://togetter.com/li/997991

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