Hatena::Grouptopcoder

kohyatohの日記

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

2011-05-04

SRM505

| 03:36

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

Easy300RectangleAreaOpened数学ではない
Medium500SetMultiplesOpenedsqrt
Hard1000PerfectSequences2Unopened-

惨敗。

負けるとブログに書く事は少なくなります。


20:15 Easy

n*m+1個の連立方程式で、未知数がn+m+α個で...とか考え出した時点で死亡。


20:55 Medium

Easyを諦めて開くも、計算量の計算をミスって死亡。


21:20 Challenge

300で正解のコードに対して反例を探していて死亡。


結果

Opened/Opened/Unopened +0/-0

0 + 0 + 0 + 0 = 0 306位 (部屋9位)

2253 -> 2118

黄色に戻りました。


反省

ここのところ簡単な回が続いていたので、なんか甘く見ていた気がする。

この300は解ける気がしないけど、500は解けるべき。

なんか全体的に思考がバグってた気がする。

2011-04-18

SRM 503

| 10:16

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

Easy250ToastXToastAC (24min)気づくだけ(それが一番...)
Medium500KingdomXCitiesandVillagesAC (26min)期待値の線形性
Hard1000KingdomXEmergencyStaircaseOpened?


25:00 部屋割り

Room 21.

普通。


25:05 Medium

別に、心を入れ替えたとかそんなのじゃなくて、普通にマウス操作をミスってMediumを開いてしまった...


問題を読むと、「期待値の線形性」を知っていればさくっとできそうな問題。

一つ一つの村に対し、その村のために建設される道路の長さの期待値を求め、合計すればいい。

ある村に対し、他の村が前にくる確率は対称性より1/2。

それを累乗すればいい...と思ったら答えが違う。


村が3つの場合について書き出して調べてみる。確率の計算が思ったほど簡単ではない。

(自分にしては)頑張って数式を導き出し、直して提出。300点。


もう少し、数学的直感力みたいなのを身につけたいなぁ...


25:30 Easy

他の人のスコアを見る限り、そんなに簡単そうではない。


読む...ややこしい!

DPっぽい...それとも貪欲?

とりあえず貪欲書く->サンプルの最後のが合わない。

え、これ何で2になるの? 3じゃないの...


......結構時間がかかって、ようやく意味がわかる。

トーストの種類は高々2で良い。

なので、答えが-1と1になる条件のみ調べればいい。


書く->提出。160点。あちゃ..


26:00 Hard

いやいくら何でも15分でHardはムリでしょう。とか思いながら。

時間切れ。


26:20 Challenge

250で、{4},{4}とか入れたら結構落ちるんじゃないかなぁ、と思いながら探す。

案の定いたので投入したら、入力がinvalidだとか言われた。

問題親切だな...


その他は落とすケースが見つからず。


結果

AC/AC/Opened 0/0

160.68 + 309.76 + 0 + 0 = 470.44 79位(部屋2位)

2217 -> 2253


停滞中。


復習

まだまだ解くのが遅い。


250とか、もっと簡単に解けるだろー、とか疑ったほうがいいかもしれない。

2011-04-10

SRM 502

| 01:20

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

Easy250TheLotteryBothDivsAC (9min)やるだけ
Medium500TheProgrammingContestDivOneWAソート貪欲
Hard1000TheCowDivOneOpened?

敗北...


10:00 部屋割り

Room 9.

黄色多め。


10:05 Easy

パッと見、被っているsuffixを除外してから、当たりの本数を数えるだけでよさそう。

書く->サンプル合わない。


あれぇ...

よーくよーく問題文を見直すと、"suffix"じゃん!"prefix"だと思ってた!

直して提出。230点ぐらい。もったいない。


10:15 Medium

なんか簡単な回っぽいし、サクっと行けるかな?


...問題は、pointsPerMinuteが多い順に解くのが最適そう(※嘘)

解く順番が決まっているとすれば、あとはDPするだけ。

書く->サンプル合う。提出。420点。

お、いいぞ...


10:30 Hard

なんか式がフィボナッチっぽくなる。

数理の問題か...?

...時間ぎれ。


11:20 Challenge

Mediumでオーバーフローしてる人がいないか狙う。

...逆に自分が落とされた!

neal_wuの解答を見てみると、ソートを「密度の逆数」でやるようになってる。

そういえばそうだった...


結果

AC/Challenge Succeeded/Opened 0/0

229.89 + 0.00 + 0 + 0 = 229.89 167位(部屋7位)

2264 -> 2217


復習

Mediumみたいな、累積していくものは、「密度の逆数」でソートするのが最適、っていうのは一回PKUでやったことがあったし、証明もしていた(*)ので、それを忘れるとかひどい。

今回は「どうせ大丈夫だろう」と思って証明なしで突っ走ってしまったのが最大の敗因だと思うので、証明はきっちりしないといけない。


簡単な問題を速く正確に解く、っていうのは、もはや完全に練習量の世界だと思う。練習しないと。

2011-04-03

SRM 501

| 05:06

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

Easy250FoxPlayingGameAC (12min)貪欲...
Medium500FoxAverageSequenceAC (33min)どこかで見たようなDP
Hard1000FoxSearchingRuinsOpenedデータ構造(らしい)

Fox(Ciel)回。


19:30 ウォーミングアップ

簡単な問題をゆっくり。

簡単な問題は、あまりゆっくり解いても意味がない気がした。


20:00 部屋割り

Room 13.

若干赤多め。


20:05 Easy

掛け算部分はまとめるとかそういう感じ?

でも証明ができない...


式をばらすと、それぞれのaにbを何回ずつ掛けるか、という問題に落ちる。

ので、DPすればいい。


書く->提出。210点ぐらい。完全に出遅れてる。


20:20 Medium

現在位置、前2つの値、そこまでの合計値を状態にすると状態数が多すぎてアウト。


...よく見ると、前2つの値は必要なく、前2つで上がったか下がったかのみ分かればよい。

これでO(n^5).

もう一段減らさないといけないような気もするけど、それは和の部分をちょっと変更するだけなので、とりあえず書いてみる。

すると普通に最大ケース通ったので、確認して提出。250点ぐらい。あちゃー...


20:55 Hard

dp[現在位置][左右の動く回数] := 取れる宝石の最大値

とすればよさそうだけど、O(n^3).


他に思いつかないので、とりあえず書いてみる。

...答えが合わない。そのまま終了。


21:20 Challenge

Easyで0の時の扱いが変な人がいたのでチャレンジ。

...unsuccessful. え?

よく見ると、aとbを関数の引数部分で逆にしてる。難読化か!

他の部分が間違っていたので再チャレンジ。successful. もったいない。


結果

AC/AC/Opened +1/-1

212.99 + 268.48 + 0 + 25 = 506.47 114位(部屋5位)

2258 -> 2264


復習

こういう簡単な回だと、コーディングの遅さが際立つ。

難しい問題ならしっかり考える、簡単な問題ならさっさと解く、を徹底しないと。

2011-03-22

SRM 500

| 00:41

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

Easy250MafiaGameAC (16min)手計算が大事
Medium500FractalPictureOpenedフラクタル
Hard1000ProductAndSumUnopened-

記念すべき500回目。



23:30 ウォーミングアップ

かるーく解くつもりが、1時間ぐらいはまって若干不安に。


25:00 部屋割り

Room 37.

するめタイマーでお世話になっているd:id:Tayamaさんと一緒の部屋。


25:10 Easy

しばらく様子見していたけど、誰も提出しないので、どんな難しいんだと戦々恐々。

時間も減ってきたので開く。


一瞬見ただけではワケがわからない。


最初の投票でn人に対してn票なのがなんだか怪しい(候補者に対して票の数が少なすぎる)。

ちょっと紙の上で試して見ると、一回目の投票で、固定票を1票でも獲得した人は、浮動票は得られない。

逆に、固定票を1票も得られなかった人は、1票だけ浮動票がもらえる可能性がある。


もうちょっと考えると、一回目の投票で、

(1)固定票を2票以上もらった人がいない場合

->浮動票により全ての人が1票ずつ受け取ることになるので、無限ループに陥る。

(2)固定表を2票以上もらった人がいる場合

->最多得票タイの人達が生き残る。この人たちは固定票の数が同じなので、全て同じとみなせ、それぞれが勝利する確率は等しい。(ただし、途中の投票で無限ループに陥らないかチェックは必要。)

となる。


コード自体はあまり難しくない。

書く->submit. 200点弱。体感時間より時間がかかったみたい。


25:30 Medium

これまたムズそう。

長さが1/3ずつになっていくのに対し、クリッピング領域は整数なので、長さが1未満になったら後は計算でいけそう。

...と思って式を立ててる間に時間切れ。


Hardは開いてません。


26:20 Challenge

Easyだけなのにそこそこいい位置にいたので、あまり冒険はせず。

vectorのオーバーランしてる人がいたけど、他の人の猛チャレンジをことごとく防いでいたのでチャレンジはしなかった。


結果

AC/Opened/Unopened

194.72 + 0 + 0 + 0 = 194.72 63位(部屋5位)

2186 -> 2258


念願の赤!

Easy解いただけで63位とは...


復習

500は明らかに方針ミス。

はまりかけたら、もうちょっといい方法がないか一旦考え直してみるべき。


challengeむずい。ていうか、部屋で落ちた人2人しかいない。

そのうち一人は最大値を求めるコードがミスってたので、これは落とせておくべき。

もう一人は微妙な配列外アクセスだったので、ちょっとムリっぽい。