サクサク読めて、アプリ限定の機能も多数!
トップへ戻る
円安とは
toslunar.hatenablog.com
今年も*1チームUnagiで参加しました。チームメイトの日記: ICFPC2016ぷち参戦記 - chokudaiのブログ ICFPC 2016 参加記 - wataの日記 開始前 Unagiは例年iwi家に集まって戦っているのだが,残念ながら私は海外出張が重なってしまい,iwi家にいられるのは最初の1日ちょっとになってしまった。 公式ツイートのうちhttps://twitter.com/ICFPContest2016/status/757792006345150464の出題者が中野圭介先生だと予想。根拠: In this talk, I introduce an interesting property of B-terms, that is, whether repetitive right applications of a B-term circulates or not. htt
公式の解説で,「遅延評価を使ってもできる」と書いてくれなかったので。 注意:この記事は,Google Code Jam 2014 Round 1AのB問題 Full Binary Tree についてのネタバレを含みます。 この問題は木DPをする典型的な問題であり,公式の解説にもあるように, 木を根付き木にした後, 頂点でのスコアを,子のスコアのうち大きい方から2つを用いて計算する ことで解けます。何を根として選ぶかをすべて試すとO(N2)解法となり,すべての根の可能性について同時にDPをする*1とO(N)解法になります。だから,根の選び方によって隣接頂点のうち「親以外が子となる」ので,隣接頂点のスコアのうち大きい方から3つを保存するような構造を持つ――待ってください。 もちろん,降順ソートされたスコアのすべてを計算すると,O(N2)時間かかってしまいます。しかし,先頭3つを結果的に計算でき
アルゴリズムの代表っぽい存在とも言えるDPですが,Haskellは参照透明なので書きにくいと思われがちです. しかし,実際は,C言語やSTLなしのC++より遥かに簡単に動的計画法が書けます. リストを用いる 最初に知るであろう方法. フィボナッチ数列の第100項だと, let f = 0 : 1 : zipWith (+) a (tail a) in f!!100 です. 「ずらして足したものを後ろにつなげる」と言えばいいのでしょうか. これについては,他でよく解説されているので詳しくは説明しません. 利点: リストの知識のみでよい. 無限リストの恩恵が受けられる. importが不要. 欠点: 使えるケースが限られる. 書くときに,混乱することも(上の例だと,と考える必要がある. ランダムアクセスができないので,場合によってはO(n)倍の時間がかかる*1. 添字を自由に用いることができな
このページを最初にブックマークしてみませんか?
『toslunar.hatenablog.com』の新着エントリーを見る
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く