hotpepsiの練習帳

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