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]
トラックバック - http://topcoder.g.hatena.ne.jp/tanakh/20100115
 |