SRM467 div1 (practice)

250

• ループする区間の問題
  • てきとうに実装すればいいんじゃないの
  • これって端はどうなってんの？よく見たら左端は入らずに右端が入るとか変なことになってるし…。
  • しかも実数だからbestとworstが一致するときだけコーナーケースになってる…。
  • 実装に時間がかかった。submit。WA。
  • よく見るとlate >= worstかつ外に出る直前に先生が必ず来る場合に死んでた。

500

• SumをSumする問題。
  • ちょっとむずい。
  • 式変形するとになるなあ。
  • もっと変形させるとになった。
  • これって行列乗算で行けるんじゃね。
  • Matrixのライブラリを貼りつけて実装。なんか合わない。
  • いろいろ調べたら最初の行列が左右反転してた…。
  • submit。TLE？
  • vectorとかテンプレートを使ったMatrixライブラリが遅すぎた。
  • classを使ってない奴を使ったら余裕で間に合った…。

結果

xx- 0pts 282位くらい。
こういう風な問題は苦手だなあ。
解法見たら、コンビネーションを使うって書いてたんで、nCk % MはMが素数以外の時にもO(k^3logn)くらいで求めることが出きるのか。
(追記)よく考えると自明にO(k^2)の方法があった。