遅延評価を活用して線形時間でGoogle Code Jam 2014 Round 1AのB問題を解く - tosの日記
公式の解説で，「遅延評価を使ってもできる」と書いてくれなかったので。 注意：この記事は，Google Code Jam 2014 Round 1AのB問題 Full Binary Tree についてのネタバレを含みます。 この問題は木DPをする典型的な問題であり，公式の解説にもあるように， 木を根付き木にした後， 頂点でのスコアを，子のスコアのうち大きい方から2つを用いて計算する ことで解けます。何を根として選ぶかをすべて試すとO(N2)解法となり，すべての根の可能性について同時にDPをする*1とO(N)解法になります。だから，根の選び方によって隣接頂点のうち「親以外が子となる」ので，隣接頂点のスコアのうち大きい方から3つを保存するような構造を持つ――待ってください。 もちろん，降順ソートされたスコアのすべてを計算すると，O(N2)時間かかってしまいます。しかし，先頭3つを結果的に計算でき
No Such Blog or Diary - ICPCをHaskellでやろうとしたときのテンプレート
ICPCをHaskellでやろうとすると入出力はこんな感じだろうか？ とりあえずメインルーチンはデータセットのリストを getProblems で生成し，mapM_ で各データセットに対して solve で解いた結果を putStrLn.show で出力と． main = getProblems >>= mapM_ (putStrLn.show.solve) getProblems に関して．各入力セットの先頭の数字が終了フラグになるタイプは，終了なら [] をリターン，そうでなければデータをタプルにして cons をリフトする． main = getProblems >>= mapM_ (putStrLn.show.solve) getProblems = do [n] <- getNums if n==0 then return [] else do xs <- replicateM
Codeforces用Haskell I/Oライブラリ - 似非学問的な手記
HaskellでCodeforcesに参戦しようとしたときに、ちょっと面倒なのが入出力だったりします。 たとえば、Int型の値を直接読み込むI/Oはないので、そんな時は適当にgetInt::IO intみたいな関数を用意しなければならない訳ですが、文字列と数値が混ざっててそれをm行読み込んで……などに逐一適応するのは面倒ですし、そこで2〜3分時間をとられているようじゃ既に不利です。 そこで、HaskellにもC/C++におけるscanfのような関数があればいいと思い、試しに作ってみました。 前回記事にした#82 Div.2の時よりもさらに一般化しています。 {-# LANGUAGE TypeSynonymInstances #-} class Scan a where scan' :: String -> a instance Scan Int where scan' n = read n
1
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
処理を実行中です
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
