Hatena::Grouptopcoder

kohyatohの日記

 - 非数学系な人のTopCoder参加記です。

2011-01-23

SRM 494

| 17:12

ソース・成績(要ログイン)

新年2回目。前回レートhighest更新したので、「慎重に」を心がけたけど、あまりうまくいかなかった...

Easy250PaintingAC (19min)シミュレーション
Medium500AlternatingLaneAC (47min)引っ掛け+期待値
Hard1000KnightsOutUnopened-


26:00 部屋割り

Room 3. 赤が数人、青黄がたくさんの標準的な部屋。


26:05 Easy

250落ちると洒落にならないので、少しぐらい遅くても確実路線で行こうかな、と思いながら開く。


地道に計算すると、O(50^6)になって(※嘘)いくら何でもアウトだよなー、と思い、それぞれのマスに対して可能な最大ブラシ幅を求めるDPを書いてしまう。

しかも全部覆えるかのチェックで結局計算量はO(50^5)。何無駄なことを...


しかも幅と高さを一箇所間違えていて、そのデバッグで時間が潰れる。

直して、入念に見直して、submit。180点ぐらい。いくら何でも遅すぎだろう...


26:30 Medium

500は400点台で提出してる人もいるし、速く解いて挽回しないとなぁ、と思いながら。


見たところDPっぽい。

dp[i][h][v] := i番目の高さがhの時、v=0ならそこを谷部分、v=1ならばそこを山部分とした時の得点の期待値

とかでできそう。


で、ちょっと書き始めてみたけど、これは複雑すぎる。こんなの400点で出せるわけないし、他に方法があるのか?

...もう一度よく眺めてみると、木を抜いても抜かなくても得点は変わらない! ならば山か谷かの判断はいらなくて、dp[i][h]のみで行ける!


DP式を立てると、

dp\[i\]\[h\] = \sum_{k=low\[i-1\]}^{high\[i-1\]} \frac{dp\[i-1\]\[k\]+|h-k|}{r\[i-1\]} (ただしr[i]=high[i]-low[i]+1)

となる。


これは、

p\[i\] = \sum_{h=low\[i\]}^{high\[i\]} \frac{dp\[i\]\[h\]}{r\[i\]}

とおけば、上のDP式から

p\[i\] = p\[i-1\] + \sum_{h=low\[i\]}^{high\[i\]}\sum_{k=low\[i-1\]}^{high\[i-1\]}\frac{|h-k|}{r\[i\]r\[i-1\]}

が導ける。


ここまでくれば、あとは|h-k|の和を計算するだけ!これは、すべてのhに対して、等差数列の和の公式を適用すればいい。簡単じゃん!と思って実装。


...サンプル合わない。

必死にprintfデバッグ。


よく見てみると、high[i-1]<hだったりlow[i-1]>hだったりするときの処理が1ずれてる。

直して提出。終了1分前。220点ぐらい。危ない...


Hard は開けませんでした。


27:22 Challenge

Easyを'B'となってるところの最小幅のみ調べる方法でやってる人がいたので、やった!と思って適当なのを投げたら、返り討ちにあった。

その人はあとでちゃんと落とされてたので、完全に自分のミス。やはりチャレンジケースはしっかり用意しておくべき。


Result

AC/AC/Unopened 1 failed challenge

180.55 + 221.53 + 0 - 25.00 = 377.08 120位(部屋4位)

2012 -> 2058


Challengeの-25はあまり順位に関係しなかったので助かった。

レートとしては微増。このまま赤に行ければいいけど。


Review

250は50^6とか思ったけど、ブラシが正方形と決まっているので50^5で大丈夫だった。勘違いしたまま進むのはまずい。

500は結局数式をごにょごにょして正解を導き出したけど、期待値の性質 E(sum(Xi))=sum(E(Xi) を理解していればもっと簡単に思いつけたらしい。

数学(chokudaiさんのいう「算数」)大事だなぁ。


あと、今回は「慎重に」を心がけたけど、「慎重に」やるのとのんびりやるのは違うのであって、もっとスピーディーにやらなくちゃならない。


Challengeはやっぱ前回みたいに事前にケースを準備して望むべき。自分がはまりそうになったところとか。