おねえさんを組み合わせ爆発から救う：2分決定木を作る - きしだのHatena
おねえさんを組み合わせ爆発から救うために、まず格子グラフを作成しました。 http://d.hatena.ne.jp/nowokay/20121015#1350267331 こんどは、そのグラフの辺について、それぞれ通るか通らないかの組み合わせによって、始点から終点までの単純な経路になってるかどうか判定して、それをツリーとして表してみます。 右の実線に行く場合はその辺を通る、左の点線にいく場合はその辺は通らない、ということをあらわします。そして、最終的に始点から終点までの単純な経路になっている場合を「T」なっていない場合を「F」とします。 ここでは、1x1マスのグラフをあらわしているので、「1:3」と「3:4」を通る場合、つまり右に分岐する場合と、「1:2」と「2:4」を通る場合、右に分岐する場合だけが「T」となっています。 判定方法は、ツリーの途中では、始点と終点に入る辺が2本以上になる
はてなグループの終了日を2020年1月31日(金)に決定しました - はてなの告知
はてなグループの終了日を2020年1月31日(金)に決定しました 以下のエントリの通り、今年末を目処にはてなグループを終了予定である旨をお知らせしておりました。 2019年末を目処に、はてなグループの提供を終了する予定です - はてなグループ日記 このたび、正式に終了日を決定いたしましたので、以下の通りご確認ください。 終了日: 2020年1月31日(金) エクスポート希望申請期限:2020年1月31日(金) 終了日以降は、はてなグループの閲覧および投稿は行えません。日記のエクスポートが必要な方は以下の記事にしたがって手続きをしてください。 はてなグループに投稿された日記データのエクスポートについて - はてなグループ日記 ご利用のみなさまにはご迷惑をおかけいたしますが、どうぞよろしくお願いいたします。 2020-06-25 追記 はてなグループ日記のエクスポートデータは2020年2月28
Gauche:MetropolisProceduralModeling:MCMC-1D
(Shiro 2012/01/03 10:04:38 UTC): 「正月にMetropolis Procedural Modelingを基礎から理解してみる」その1。 (この項は主に、Christophe Andriew, Nando De Freitas, Arnaud Douchet, Michael I. Jordan, "An Introduction to MCMC for Machine Learning", Machine Learning, 50, 5--43, 2003. を読んで自分なりに理解したところをメモしている。) モンテカルロ法で円周率を求めてみたことがある人は多いだろう。 左下が(0,0)、右上が(1,1)である正方形の中の一点をランダムに選び、 それが(0,0)を中心とする半径1の円内に入っているかどうかを調べる。 十分に多くのサンプルを取れば、円内に入った
情報オリンピック夏季セミナーの参加記一覧とか - 簡潔なQ
2012/08/25 - 08/29の間、夏季セミナーというのにチューターとして参加していました。以下はその記録として参照できる各種媒体へのリンクです。 募集案内 実施の概要 参加者のtwitterリスト 発表会の様子(Togetter) その1 その2 その3 その4 その5 slideshare 『確率と計算 ―乱択アルゴリズムと確率的解析―』 (2) @nullmineral ARC #003 D「シャッフル席替え」の乱択アルゴリズムによる解法の解説 (4) @hyksm 乱択アルゴリズムでK-th numberを解く (5) @HziwarA 最小全域木に対する乱択アルゴリズムの評価 『抽象によるソフトウェア設計-Alloyではじめる形式手法』 (1) @sugspi_c Alloyさん (2) @everysick Alloyでハミルトン閉路 (3) @ichigo_o_re A
情報オリンピック夏季セミナー(2012) 発表会 その1
情報オリンピック夏季セミナー http://www.ioi-jp.org/seminar/2012/summer-semi.html で高校生・高専生が4日間のゼミで学んだことの発表会の記録 まとめ その1 http://togetter.com/li/363651 『確率と計算 ―乱択アルゴリズムと確率的解析―』 まとめ その2 http://togetter.com/li/363672 『抽象によるソフトウェア設計-Alloyではじめる形式手法』 まとめ その3 http://togetter.com/li/363694 『Introduction to Algorithms』 続きを読む
第12回アルゴリズム勉強会に行ってきました - アスペ日記
人生初勉強会。 やったのは counting sort と radix sort。 この二つは書いたことがなかったので、Python で超手抜きに書いてみた。 https://gist.github.com/1395308 base = 10 def radix_sort(x, max): radix = 1 while radix < max: x = counting_sort(x, radix) radix *= base return x def counting_sort(a, radix): c = [0] * base for k in a: r = (k / radix) % base c[r] += 1 for i in range(1, base): c[i] += c[i - 1] b = [0] * len(a) for k in reversed(a): r =
動的計画法とナップサック問題を学びたい人におすすめのサイト - ダウンロードたけし（寅年）の日記
組み合わせ最適化の手法として「動的計画法」というモノがあります。 wikipediaから抜粋 動的計画法（どうてきけいかくほう、英: Dynamic Programming, DP） コンピュータ科学の分野において、ある最適化問題を複数の部分問題に分割して解く際に、そこまでに求められている以上の最適解が求められないような部分問題を切り捨てながら解いていく手法 一見難しそうですが、実は理解するのは以外と簡単です。いろいろな場面で応用が利く便利な手法ですので、覚えておいて損はないものです。コンピュータ系、情報系のお勉強をする人であれば、おそらく一度は習ったりするかもしれません。 ナップサック問題と動的計画法 動的計画法の一番親しみやすそうな例として「ナップサック問題」というのがよく取り上げられます。 こんな感じの問題です。 今ここに様々な大きさの品物が置いてあるとします。そしてそれらの品物は各
嘘解法のススメ - てきとーな日記
（この記事は Competitive Programming Advent Calendar の 18 日目の記事として書かれました．まだ18日です！セーフ！！！） 自分はICPC時代によく嘘解法を駆使して問題を解いていたので（ジャッジの方々ごめんなさい），よく使われる嘘解法テクニックを紹介したいと思います． これらのテクニックはマラソンマッチのようにそもそも最適解を求める必要のないコンテストにおいても活用できます． 嘘解法とは プログラミングコンテストにおいては，ジャッジの用意した入力データに対し，正しい答えを出力できれば正答とみなされます． このため，正しくない解法（嘘解法）が通ったりすることがときどきあります． しかし一般に嘘解法で通ることはあまりなく，嘘解法を試すのは終盤まで控えるべきです． 残り時間が少なく今から正しい解法を考える・実装するのは無理だという場合の最終手段と考えてく
はてなグループの終了日を2020年1月31日(金)に決定しました - はてなの告知
はてなグループの終了日を2020年1月31日(金)に決定しました 以下のエントリの通り、今年末を目処にはてなグループを終了予定である旨をお知らせしておりました。 2019年末を目処に、はてなグループの提供を終了する予定です - はてなグループ日記 このたび、正式に終了日を決定いたしましたので、以下の通りご確認ください。 終了日: 2020年1月31日(金) エクスポート希望申請期限:2020年1月31日(金) 終了日以降は、はてなグループの閲覧および投稿は行えません。日記のエクスポートが必要な方は以下の記事にしたがって手続きをしてください。 はてなグループに投稿された日記データのエクスポートについて - はてなグループ日記 ご利用のみなさまにはご迷惑をおかけいたしますが、どうぞよろしくお願いいたします。 2020-06-25 追記 はてなグループ日記のエクスポートデータは2020年2月28
二分探索の話 in icpc直前会議
Statistics Favorites 1 Downloads 0 Comments 1 Embed Views 0 Views on SlideShare 110 Total Views 110 二分探索の話 in icpc直前会議 — Presentation Transcript ⼆二分探索索の話@hama_duICPC国内予選直前対策会議 in チームラボ(⼀一部修正を加えてます。) こんにちは。¤ @hama_du ¤ 「はまづ(ず)」と読んでね ¤ 修⼠士２年年¤ ICPC出場経験 ¤ ⼈人間⼒力力なくてチーム作れなかったのでなし！ ¤ (国内予選にすら参加してない) ¤ ⾃自⼤大学をひいきするため活動中¤ その他、主なプロコンの成績 ¤ Topcoder : 1606(SRM) / 1703(MM) ¤ Codeforces : 17
TopCoder Open 2012 Marathon Round 3参戦記 - chokudaiのブログ
見せるフォーマットになってませんが、せっかくなので公開しておきます。 自分が組むプログラムは最低限説明出来るレベルになければならないと思うので、コンテスト中にそのことを意識したメモです。でも全く説明になってません。 自分のプログラムを追いかけたい！みたいな奇特な方がいればどうぞ 5/31(1日目) 問題を確認 http://community.topcoder.com/longcontest/?module=ViewProblemStatement&compid=26332&rd=15101 rnd(A,B)は、ランダムにA〜Bの値を意味する、という表記で ケーキがC個あります。C=rnd(1,10) ケーキを食べる人がG人居ます。G=rnd(2*C,10*C) 一つのケーキにつき2〜10人 ケーキの材料がI個あります。I=rnd(2,10) ケーキは正方形で、S*Sマスで表わされます。S
Fast median search: an ANSI C implementation
Introduction Median filtering is a commonly used technique in signal processing. Typically used on signals that may contain outliers skewing the usual statistical estimators, it is usually considered too expensive to be implemented in real-time or CPU-intensive applications. This paper tries to gather various algorithms picked up from computer literature, offers one possible implementation for eac
はてなグループの終了日を2020年1月31日(金)に決定しました - はてなの告知
はてなグループの終了日を2020年1月31日(金)に決定しました 以下のエントリの通り、今年末を目処にはてなグループを終了予定である旨をお知らせしておりました。 2019年末を目処に、はてなグループの提供を終了する予定です - はてなグループ日記 このたび、正式に終了日を決定いたしましたので、以下の通りご確認ください。 終了日: 2020年1月31日(金) エクスポート希望申請期限:2020年1月31日(金) 終了日以降は、はてなグループの閲覧および投稿は行えません。日記のエクスポートが必要な方は以下の記事にしたがって手続きをしてください。 はてなグループに投稿された日記データのエクスポートについて - はてなグループ日記 ご利用のみなさまにはご迷惑をおかけいたしますが、どうぞよろしくお願いいたします。 2020-06-25 追記 はてなグループ日記のエクスポートデータは2020年2月28
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Divisor
メトロポリスライトトランスポート - tuedaの日記
アルゴリズムイントロダクション15章 動的計画法
http://www.kupc.jp/editorial.html
計算機ソフトウェア 第四回
中央値分割
バケット法の時の計算量