Hatena::Grouptopcoder

TopCoderの学習のお時間 RSSフィード

戦績(topcoder.com) / 戦績(competitiveprogramming.info) / 過去記事 / 日記

 | 

2009-12-18

[][]SRM455 02:18 はてなブックマーク - SRM455 - TopCoderの学習のお時間

2009-12-17 25:00-(JST

http://www.topcoder.com/stat?c=coder_room_stats&cr=22744421&rd=14179&rm=303019

初のratedなMember SRM。3問全部変則セットはたぶん初経験


Levelタイトル試合中あとで感想
DIV1 300DonutsOnTheGridEasyAC 56min-ad-hoc
最初DPっぽく考えてたらO(N^5)な感じになって泥沼に。
落ち着いてN重のドーナツを心の中に思い浮かべると、
「中心から外周に向かう間に何回ドーナツをまたぐか」を数えればよいのではないかと思いつく。
ポイントは「特定の長方形を中に含む "最小のドーナツ" は一意に決まる」ことで、
証明はしてないが直感と実験がそう告げた。
なので、各マスを起点として、
最小包含ドーナツを求める→そのドーナツを含む最小包含ドーナツを求める…
という操作を何度繰り返したら外周に到達するかを数えて、それらの最大値が答え。
各マスに対して '0' の列が上下左右どこまで伸びてるかを前計算しておくと全体の計算量O(N^3)?
最小包含ドーナツを求める実装がなかなか難しくて時間がかかってしまった
DIV1 550ConvexHexagonsOpened-DPっぽいなーと眺めただけ
DIV1 900ActivateTreeUnOpened-読んでない

  • Challenge & System Test
    • 部屋内では300しか提出されていない
    • よく分からないのでだらだら読む
    • けっこう時間経った後でも、単純な最大ケース(50*50の'0')で落ちるのが2個残ってた。おいしく頂いた
      • チャレンジまじめにやる人って意外と少ないのかなー
    • システムテストの結果で、もう1つ最大ケースTLEがあったことに気づく。開き漏らしてたみたい
    • あと2つWAで落ちてるのがあったけど読めません。レート上位の人だったし
  • スコア: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が難しかったということか。

http://www.topcoder.com/tc?&sc=6&sd=asc&module=MatchList

 |