TopCoder SRM 520 (Div1) - simezi

219.72 / Compiled / Unopened
200位 1985 -> 1999

500は解けていた。
今回はレートを稼げる回のはずだった。悔しい。

3問の問題を解く。
それぞれの問題はproblem[i]点であり、各問題を解くのにはskill[i]分かかる。

luckをもっていて、luck1につき問題を1分はやく解くことができる。
luckは好きに問題に割り振れるが、問題を1分未満で解くことはできない。

問題はt分かかって解くと、一問目はproblem[0]-2*t点
二問目はproblem[1]-4*t点
三問目はproblem[i]-8*t点がもらえる。
解かないと0点である。

制限時間は75分で、全ての問題を解く時間の和は75以下になっていなければならない。
得られる最大の得点を求めよ。

全探索でいける。
書いた。
サンプル合わない。なぜだろう。しばらく考える。

あ、ICPCルールでやってた。（問題ごとに独立して時間を数えるのではなく、スタートからの累計時間で得点を計算してた）
直す。
サンプル合わない。

あー、ペナルティを2,4,6点で計算してた……
なんかミス多いなあ。
修正してサンプル合った。送信。

3問の問題がある。それぞれの満点はpoint[i]点である。
問題が解けた場合、1点からpoint[i]点以下の整数の点数がつく。

n人がそれぞれの問題を解いたかどうかの表が与えられる。
表は、合計得点の大きい順にならんでいて、なおかつ全員の合計得点が違う点数であるとき、考えられる全員の点数の場合の数をmod 10^9+7で求めよ。

おーこれは簡単なDPじゃね？一瞬で方針が見える。
えーとdp[i][j]を、i番目の人がj点取るときの場合の数としてDPすればいい。

i番目の人の点の取り方は、0点か、1点からN点があるのかな……？
愚直に更新するとTLEになるけど、和を求める部分はbinary indexed treeでも使ってやれば高速に求まる。

書く。なんかバグる。
直す。なんかバグる。
最後のサンプル合わない！！なんでだ！！

何回も見直す。オーバーフローもしてないよな？
また見直す。問題文を勘違いしてないよな？読み直す。
勘違いしてないと思う。
また読み直す。意味不明。

あー！！ある人が3問解いた場合最低得点は1点ではなく3点か。
直す。んでもサンプル通らない。

しばらく問題文を読み直して、
これ、合計得点が同じでも、それぞれの問題で取った点数が違うならば違う状態とみなすんじゃねーの？と思う。

そんな気がする。
てか問題文に書いとけよ！！ふざけんな！！！

残り14分しかない。
えーと、ある点を取るときの場合の数を求めればいい。
それにはもう一段階前処理でDPをしておく必要があって。
愚直にやるとアレだから直前の値を使ってオーダー落とすDPだ。
最近蟻本で復習したのでスラスラ書く。

残り5分。最後のサンプルがやはりあわない。
方針とか漸化式とか間違ってるのだろうか。
色々出力してみる。

おかしいとこはなさそう。
ああああああ一箇所オーバーフローしてたああああああ

時間切れ。本当酷い……

あけてない

何も挑戦してない。
Twitterで愚痴っていたら「clar出てたよ」という返信を貰う。
ぐ、ぐぬぬ……

250は通った。悔しいなあ。