TCO2011 Algorithm Round4

(問題文はTopCoderのサイトを見てください)

解答例

300

点iと点jが決まっているとき、( i , j )と交差するルートは、「領域Aにある点の数×領域Cにある点の数+領域Bにある点の数×領域Dにある点の数」になる。
i , jを全通り回し、各領域にいくつの点があるかも回して求めて、O(500^3)。
X座標とY座標にかぶりはないので、境界とかはあまり気にしなくてよい。
最後に重複をのぞくために2で割る。

500

ファイナルターンのドローでビンゴにする自分カードの集合Aを回す。(2^5通り)
Aの全カードに含まれる数字が1つ以上ない場合はスキップ。
Aに含まれない自分のカードと相手の全カードをBとする。Bは1枚もビンゴになってはいけない。
「数字の集合Xを選び、BのどのカードにもXの元が1つ以上含まれているようにする」と、75-|X|ターン続けられる。つまり|X|が最小になるように選べばよい。
dp[i]=「iの全カードにはXの元が1つ以上含まれて、そうでないカードには1つも含まれていないようにしたときの、|X|の最小値」としてビットDPすると求められる。どの数字を使って達成したかは覚えておく必要がない。

参加記

300 → 0

X座標とY座標にかぶりがないという条件を読んだけれど頭から抜け落ち、面倒くさい場合分けを頑張るが、時間内に組みきれない。

500 → 0


(正)
for(i=0;i<(1<これを、

(誤)
for(i=0;i<(1<逆向きでもいけるような気がして逆向きにやってしまった。

結果

R2297 → R2188

激弱ですらなくなった……。