■ [SRM][本番]SRM455 
http://www.topcoder.com/stat?c=coder_room_stats&cr=22744421&rd=14179&rm=303019
初のratedなMember SRM。3問全部変則セットはたぶん初経験
| Level | タイトル | 試合中 | あとで | 感想 |
|---|---|---|---|---|
| DIV1 300 | DonutsOnTheGridEasy | AC 56min | - | ad-hoc 最初DPっぽく考えてたらO(N^5)な感じになって泥沼に。 落ち着いてN重のドーナツを心の中に思い浮かべると、 「中心から外周に向かう間に何回ドーナツをまたぐか」を数えればよいのではないかと思いつく。 ポイントは「特定の長方形を中に含む "最小のドーナツ" は一意に決まる」ことで、 証明はしてないが直感と実験がそう告げた。 なので、各マスを起点として、 最小包含ドーナツを求める→そのドーナツを含む最小包含ドーナツを求める… という操作を何度繰り返したら外周に到達するかを数えて、それらの最大値が答え。 各マスに対して '0' の列が上下左右どこまで伸びてるかを前計算しておくと全体の計算量O(N^3)? 最小包含ドーナツを求める実装がなかなか難しくて時間がかかってしまった |
| DIV1 550 | ConvexHexagons | Opened | - | DPっぽいなーと眺めただけ |
| DIV1 900 | ActivateTree | UnOpened | - | 読んでない |
- Challenge ＆ System Test
- スコア：121.15 + 0.00 + 0.00 + (50*2-25*0) = 221.15
- 順位：74位/563人
- レート：1834→1920
自己ベスト大幅更新！ そういえばTopCoder部日記始めたときには目標2000とか言っていたんだった。ちょっと見えてきた。
しかし明らかに今回はチャレンジ運のおかげです。自分ではまだ1700台が適正レーティングという肌感覚。
【追記】Div1で参加者1人あたりのサブミット数が0.82問で、これはSRM127に続いて歴代2番目に小さい数字です。つまりそれだけ今回のEasyが難しかったということか。
