hotpepsiの練習帳

TCO12 Round 2A

00:58

Easy (300) SwitchesAndLamps

問題

• N個のスイッチとN個の電灯がある。
• それぞれのスイッチと電灯との位置関係はばらばらである。
• どのスイッチが接続されているか何回かチェックした。
• あと何回チェックすれば対応関係がわかるかを求める。

方針

• 矛盾判定をunion find木で書いてみたりとか
• 確定したやつを取り除いてみたり
• 75分終了
• komiyaさんのを写経
• スイッチの状態をbit化
• i番目のスイッチに着目したとき、そのon/offと連動しているものをbitwise andして、同じグループであるとみなす
• 最大グループのサイズが1なら確定しているので答えはゼロ
• 1度チェックすると、グループのサイズを約半分に減らせる
• https://github.com/firewood/topcoder/blob/master/tco_2012/SwitchesAndLamps.cpp

結果

0pt rating 1363 -> 1377

難しすぎて0点だけどrating上がった。

コードは短いけどなかなか書けない。

Max -= Max / 2;

を

Max /= 2;

と書いたら間違いだった。難しい。