Hatena::Grouptopcoder

tanakhの日記 このページをアンテナに追加 RSSフィード

 | 

2010-01-15

SRM458コード

00:50 | SRM458コード - tanakhの日記 を含むブックマーク はてなブックマーク - SRM458コード - tanakhの日記 SRM458コード - tanakhの日記 のブックマークコメント

昨日の問題は全部一行で書けるそうなので、書いてみる。けどC++だとよくわからないので、Haskellで。一行に収まってないけど。900は解き方わからないので書けず。

expectBounces x t =
  sum [ 0.25 | a<-x, b<-x, a<b, b-a <= 2*t ]

main = do
  print $ expectBounces [5, 8] 2
  print $ expectBounces [5, 8] 1
  print $ expectBounces [91, 857, 692, 54, 8679, 83, 792, 86, 9537, 913, 64, 592] 458
  print $ expectBounces [75432] 386
  print $ expectBounces [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12] 3
import Data.MemoTrie

minCoins price = sum price - f (1::Int) where
  f = memo $ \c -> maximum (0: [ f n + sum [ p`div`n*(i-1) | p<-price] | i<-[2..100000`div`c], let n=i*c ])

main = do
  print $ minCoins [25, 102]
  print $ minCoins [58]
  print $ minCoins [1, 4, 5, 9, 16]
  print $ minCoins [1, 1, 1, 1, 1]
  print $ minCoins [28, 569, 587, 256, 15, 87, 927, 4, 589, 73, 98, 87, 597, 163, 6, 498]

SRM458

00:23 | SRM458 - tanakhの日記 を含むブックマーク はてなブックマーク - SRM458 - tanakhの日記 SRM458 - tanakhの日記 のブックマークコメント

http://www.topcoder.com/stat?c=coder_room_stats&cr=22627322&rd=14180&rm=303242

2196…赤コーダーを神回避。

250 228.80 AC

一直線上に同じ質量の体積0の玉が幾つかあって、それらが左右どちらかに一定の速度で動いている。ある時間までに、それらは何回衝突するか?

衝突はすり抜けと同じなので、それらが時間以内に距離0まで近づくかどうか調べればいい。あとは、玉の数が12個しかないから、2^12全部試せば期待値が出るが、玉を二つ選んだ時、それらが互いに近づく方向向いてる確率は1/4だから、全部試さなくても距離が近い対の数に0.25を掛けるだけで良かった。

450 192.07 AC

いくつかの商品を買うのだけど、通貨を適当に決めて、最小の枚数のコインで支払いたい。コインの価値は下から整数倍になってないといけない。支払うのに必要な最小枚数は?

ちょっと考えて、これはコインの組み合わせそんなに多くないんじゃないかと思ったので、とりあえず探索を書くことにする。全組み合わせを求めて、それからそれぞれ最小枚数を求める。ひとまずかけたが、サンプルでかなり遅い。余計なコインがあっていいので、新しいコインを追加するときに、前のコインの素数倍だけ試せばいいということに気づく。10倍ぐらい早くなるが、まだ10倍ぐらい足りない。枝刈りをやりたいが、枝刈りをするには途中の経過が必要だ。そのためには、再起のたびに何か計算しないといけない。さらに少し考えるに、新しいコインを一個作る度に、何枚コインを減らせるかがわかるはずだ。それの最大値を求めればいい。そうすると、最後に最小枚数を計算する必要がなくなって、全体が速くはずだ。そういうわけで、組んでみる。確かに速い。最悪ケースでも間に合いそうだ。しかし答えが全然合わない。どうしたことか。計算にあんまり自信がないので、そもそもこれ間違ってるんじゃないかと、さっきのコードに戻して高速化することにする。しばしうなる。アイデアが浮かばない。さらにうなる。うーむ、やっぱりさっきのはあってるような気がする。コードがバグってるだけじゃなかろうか。一つ目のケースが間違っていたので、ゆっくり原因を探っていくと、a*(b/c)と書くべきところがa*b/cになっていた。なんというしょぼいミス。それを直して正しくなったのでサブミット。サブミットしてから気づいたが、この探索、どのコインを作ったかを覚えて置く必要がないので、簡単にDPにできるのか。よくできてるなあ。

900 Opened

約数として、4の剰余が0のものをa個、1のものをb個、2のものをc個、3のものをd個もつような数が存在するかどうかをO(1)で確かめるような問題。

450に時間をとられすぎて、残り15分ほど。無理っぽいが一応読んだ。でもやっぱりだめだった。

Challenge

結構入力が親切だったので、コーナーケースみたいなのは作れず。450が他の人が結構TLEで落ちたっぽい。自分のも探索だったせいか二回ほどChallengeもらった。まあぎりぎりで出したわけではないので、ちゃんと確認はしてます。

反省

3回連続で100位付近で、そろそろいい順位がとりたい。すんドめが続いて辛い。450なんでこんなに時間かかったのか。デバッグで20分ほどロスしたのが痛い。900もゆっくり考えたかった。

ゲスト



トラックバック - http://topcoder.g.hatena.ne.jp/tanakh/20100115
 |