TopCoder SRM469(Div 1) - simezi

符号を間違えるとか頭バカすぎ。おまけに問題解くの遅いにもほどがある……超鬱……

173.33/Failed System Test/Unopened -25
474位 1641->1590

n列それぞれにm個席がある映画館で、いくつかの席が埋まっている。
埋まっている席の座標が与えられるとき、二人が同じ列の隣同士に座る座り方は何通りあるか。二人の座り方は区別しない。
n,mは10億以下、埋まっている席の数は50以下である。

うーんと、同じ列に人が居る場合とかがあって……
列ごとに人のsetを持っていればよい。で、setを、列の番号をキーにしたmapに入れる。
そいで人のいる列について隙間を見てって、幅が2以上なら両端の座標の差-2通りを答えに足す。

書けた。サンプル合わない。
あー最後の人と右端までの隙間の場合m-最後の人-1か。

直した。送信。

送信して気づく。あー足し算するとこは直したけど条件分岐のほうは2より大ならのままになってる！！！危ないとこだった。Resubmit.点数酷い。

ホラー映画（20本以下）を見たいが、疲れているので恐怖度が0より小さくなると寝てしまう。
恐怖度の初期値は74であり、1分に1ずつ減っていく。映画の怖いシーンに差し掛かると47だけ恐怖度が増える。各映画iは、

このとき、寝ずに見る映画の本数を最大にするような映画を見る順序において、並び順が辞書順で最も先頭に繰るような順序を求めよ。
一度寝てしまうと起きてその後の映画を見ることはできない。

むず……かしい気がする。いい解法が思い浮かばない。探索なのかなあ。
探索の方向でしばし考える。要するに、

20!の探索空間かあ。枝刈り探索とかギャンブルっぽいのはTopCoderでは（少なくともMediumでは）出ないよなあ。

ん？待てよ、今まで見たビデオが一緒ならビデオの順によらず、ビデオの数は20以下？
てことはビットでメモすればいい！！
これなら探索空間は20*2^20で2000万しかない！！
ついでに幅優先探索すれば辞書順で小さい順に答えが自動で出てくる！！

書こう。がりがり。送信。
送信後気づく。や、別に20*する必要ないじゃん。100万だよ！
訂正して再送信。スコアは低いが2問通っただろう。これはかつる。

ひらいてない。

Easyで端を足してないっぽい人がいる！！
ミスると怖いので良く見る。これサンプルすら通らないよなあ？？？うーんどうも通らなさそうだ。投げてみよう。

失敗orz

あー列の最後にm+1番目に番兵の客がいることにしてる。頭いいなー。
その後落とせそうなのは発見できずorz1ミス

500おちたああああああああ何でだあああああああああ！！！！！

Practice roomで間違い探ししていたら、ビデオが見られるかを、ビデオ突入時に調べるときの符号が間違っていた。そこだけ直したらすんなり通りやがった！！！悔しすぎる。

ちょっと頭わるすぎですよ。解くのも遅すぎですよぼく