srm431

srm430からそれほど間を空けずにsrm431。前回は登録出来なかったので助かった。
ただ来年は月二回ペースとの噂があるのでなんとも残念。

div1:250

直行座標系の第一象限と第四象限に、y軸と並行な長さ1以上の線分がいくつか与えられる。偏角-PI/2 〜 PI/2の範囲のランダムな方向に向けて光線を発射する時に、貫通可能な線分の数の期待値を求めよ。
ある直線を貫通する確率は貫通可能な偏角の範囲をPIで割れば求まる。従って

• 線分の端点をpairで表す（偏角と線分の始点か終点か）
• vector >保存してsort
• オーバーラップしている線分の数を数えながら偏角の範囲をかけたものを足し合わす
• 最後にPIで割る

で期待値は求まる。のだけど、もっと賢い方法があって、それぞれの線分について貫通可能な偏角の範囲を足し合わせてやって最後にPIで割れば同値な計算になってとても簡単。
半分位の人はそっちでやってたような。自分は前者でやったので遅くなってしまった。
failed system testな人はなんと5人しか居なかった。なんつーrobustな問題ｗ

passed system test: 193.52

div1:500

数字列を長さ(N)、分割数(A)、最も右にある数(RIGHTMOST)、最も右の部分列の公差(DIFF)の四つ組S(N, A, RIGHTMOST, DIFF)で表して四次元DPで行けそうだな〜（1000 * 1000 * 10 * 10 = 一億の空間が必要になって不安だけど）と思ったので書いてみたけど基底条件を正しく列挙できなかったので正答まで持っていけなかった。難しかったらしくて皆提出していない。

opened

div1:1000

challengeの為に必要な情報しか読まず。ところが時間内にcompileしなかったためtest caseを入力する事が出来ずchallenge phaseで先を越されてしまった。次回からは最低compileだけはするようにしよう。

opened

ratingは1397 -> 1415と微増。微すぎる！