Segment Trees
Motivational Problems: http://www.spoj.pl/problems/BRCKTS/ http://www.spoj.com/problems/GSS3/ http://www.spoj.com/problems/HORRIBLE http://www.spoj.pl/problems/IOPC1207/ https://www.spoj.com/problems/GSS2/ http://www.spoj.com/problems/SEGSQRSS/ http://www.spoj.com/problems/ORDERSET/ http://www.spoj.com/problems/HELPR2D2/ http://www.spoj.com/problems/TEMPLEQ Segment trees (shortened as segtrees), a
三目並べで学ぶミニマックス法 | POSTD
最近、「絶対に勝てない三目並べ」のゲームを作ったのですが、非常にささやかながらも楽しいプロジェクトで、いろいろ学ぶこともできました。ゲームの全体像に興味がある方は、 こちらでゲームを試してみてください 。 無敵のゲームにするには、コンピュータ側が全ての手を計算し、何らかの基準を用いて最善の手を決められるようなアルゴリズムを作る必要があります。多岐にわたって調べた結果、このプロジェクトにはどうやら ミニマックス アルゴリズムが適当そうだということが分かりました。 このアルゴリズムを根本的な意味で真に理解し、自分のゲームに実装できるようになるまでにはある程度の時間が必要でした。多くのコードサンプルと説明に目を通しましたが、私が能なしだからか、どれを見てもプロセスの内実を十分に理解することはできなかったのです。この投稿が、ミニマックスアルゴリズムに関する皆さんの理解に少しでもお役に立てたらと思い
Heavy Light Decomposition
Long post with lot of explanation, targeting novice. If you are aware of how HLD is useful, skip to “Basic Idea”. Why a Balanced Binary Tree is good? Balanced Binary Tree A balanced binary tree with N nodes has a height of log N. This gives us the following properties: You need to visit at most log N nodes to reach root node from any other node You need to visit at most 2 * log N nodes to reach fr
焼きなまし法でThomson問題の解を探索する - lan496の日記
Thomson問題 Thomson問題とは、三次元単位球の表面にN個の電荷の等しい粒子を配置するとき、クーロンポテンシャル\( U = \sum_{i < j} \frac{1}{|\rm{r}_{i} - \rm{r}_{j}|}\)が最小となる配置となるを求める問題です。詳しくはwikiをThomson problem - Wikipedia, the free encyclopedia。N=5のときにて三方両錐形が解になったり、N=8で立方体が解にならないなどいろいろと面白い問題です。 去年の12月頃、そもそもこの問題設定に名前が付いていることをある方から教えていただき、N=5の場合で実際に初期条件を与えて時間発展させることで本当に三方両錐形になるのか実験してみました。 球面上の点電荷が最も安定する配置(thomson problem)のRK4を利用したシミュレーションの進捗 pic
催促 - 対戦講座 : ぷよぷよ講座 | 壱大整域
とこぷよ等、邪魔するものが無い場合自分の連鎖のみ考えればいいのですが、実際の対戦では対戦相手がいます。なので対戦相手のことも考えなければいけません。ぷよぷよ(初代)では、相殺がないので、相手を埋められる量の連鎖(5連鎖)をすればいいですが、通以降は相殺があるので、当然勝つためには連鎖数が多ければ多いほどいいはずです。しかし、ある程度連鎖数が大きくなると、次の法則が成り立ちます。 後撃ち有利の法則 (以下、図は左を1P、右を2Pとします) 左図のように、今1Pが10連鎖、2Pが8連鎖を作っているとします。 当然10連鎖＞8連鎖だから、「今1Pが連鎖すれば1Pの勝ちだ」と思うかもしれません。 しかし、連鎖は発火してから終わるまで結構時間が掛かります。この間に2Pは連鎖を伸ばす事が出来ます。 だから、先に大連鎖を打ってしまうと相手に連鎖を伸ばされ、負けてしまうのです。 つまり、対戦では連鎖を後に
組み合わせの個数(二項係数)を計算する - 唯物是真 @Scaled_Wurm
Pythonで組み合わせ(Combination)を計算 - 唯物是真 @Scaled_Wurm 数年前に上のような記事を書きましたが、ライブラリを使わない場合の計算について書いてなかったので記事にしました 組み合わせとは いくつかの要素の中から、順番を区別せずにいくつかの要素を選ぶ方法 組合せ (数学) - Wikipedia 具体的なそれぞれの組み合わせを得たい場合、Pythonならitertools.combinationsで引数に与えたiterableの組み合わせを返すイテレータが得られます C++ならnext_permutationが使えますが、あらかじめソートしておかないといけないので注意が必要です 組み合わせの数 \(n\)個の要素の中から、\(k\)個要素を選ぶ方法の個数は以下のように階乗(!)を使って計算できます $${\binom nk} = \frac{n!}{k!(
詰将棋を解く時の脳の使い方 - 将棋棋士 遠山雄亮のファニースペース
先日、若島正著「盤上のファンタジア」という詰将棋作品集を解いていると書いたところ、業界内で意外と反響がありました。 詰将棋が解ける時 その作品集の中の問題で、合計10時間以上苦しんだものがありました。 問題の途中図に以下のような部分図が発生します（ネタバレを防ぐため、一部の駒は除いています）。 ここで▲７二銀打と攻めると、非常に際どいのですがどうしても詰みません。 この図に至るまでの手順もとても複雑。そして総計で10時間以上経ったある時、▲８二銀と打つ手を発見しました。 ６一の銀も取られますし、不利感のある手です。 ですがこの手が妙手で、以下は守備馬の只捨てなどを経て17手程度かかって収束します。 この▲８二銀に辿り着いた時、守備馬の只捨ても含め、その後の17手が瞬く間にわかりました。 10時間以上分からなかったのに、１手（▲８二銀）が見えたことで何故一気にその後の全てが分かるのでしょう。
本当に実用的なたったひとつのソートアルゴリズム - CARTA TECH BLOG
コンテンツメディア事業本部の新卒エンジニア坂本がお送りいたします。 突然ですが、皆さんの好きなソートアルゴリズムはなんですか？ 私は基数ソートのスマートでストイックな雰囲気に惹かれます。 とはいえ、普段の開発では「どのソートアルゴリズムを使うか」を意識することは少ないのではないでしょうか。 むしろ現実世界で「トランプが全部揃ってるか」を手作業で確認するときとかのほうが、実はソートアルゴリズムが必要なのかもしれません。 ということで（？）、そのような現実的な場面で、本当に実用的なソートアルゴリズムを決める戦いが始まりました。 選手紹介 今回試したソートアルゴリズムは、独断と偏見で選んだ以下の5種類。 1 挿入ソート シンプル・イズ・ベスト！正直言ってベンチマークの噛ませ犬！ 2 クイックソート 「クイック」の名前はダテじゃない！王者の貫禄を見せてやれ！ 3 マージソート 安定感のある隠れた実
キャッシュフレンドリーな二分探索 ー データ構造を再考する | POSTD
現代のコンピュータのアーキテクチャに搭載されている高速のキャッシュメモリは、 参照の局所性 に優れた(＝一連のものとしてアクセスした要素が、互いに近いメモリのアドレスに配置されている)データ構造を好みます。これは、 Boost.Containerの平坦な（ツリー状ではない）連想コンテナ のようなクラスを陰で支えている理論的根拠です。要素を連続的に（かつ順序だてて）保存すると同時に、標準的なC++ノードベースの連想コンテナの機能性をエミュレートします。以下にあるのは、要素が0から30の範囲の時、 boost::container::flat_set の中で 二分探索 がどのように行われるのかを示した例です。 探索で目的の値を絞り込むにつれて、アクセスされる要素は次第に近くなっていきます。そのため、最初のうちは大きな距離を飛び越えていくような感じであっても、参照の局所性は このプロセスの最後の
RubyとPythonにおけるガベージコレクションの視覚化 | POSTD
本稿は、ブダペストで開かれたイベント「 RuPy 」で、Pat Shaughnessyが披露したプレゼンの内容をまとめたものです。 プレゼンの映像はここ から視聴できます。 本稿は当初、 同氏の個人ブログ に投稿されましたが、同氏の了承を得て、Codeshipに再掲載します。 このイベントは「RubyとPython」に関するカンファレンスなので、RubyとPythonでは、ガベージコレクション（以下「GC」）の動作がどう違うのかを比較すると面白いだろうと私は思いました。 ただしその本題に入る前に、そもそもなぜ、GCを取り上げるのかについてお話しします。正直言って、すごく魅力的な、わくわくするテーマではないですよね？ 皆さんの中でGCと聞いて、心がときめいた方はいらっしゃいますか？ ［実はこのカンファレンス出席者の中で、ここで手を挙げた人は数名いました！］ Rubyコミュニティで最近、Rub
橋本環奈が司会でプログラミングの世界を紹介。NHK「アルゴリズミ子研究所」が話題
リンク 世界を変える魔法！ - NHK 世界を変える魔法！ アルゴリズミ子研究所 - NHK 世界は今アルゴリズムで動いている！世界経済からスマホ、家電まであらゆる物を動かすコンピュータプログラムの世界を紹介。 【案内役】橋本環奈、有野晋哉（よゐこ） 42 users 1524 sefuumi @sefuumi がっつり数学的な話でしょうか、それともアルゴリズムってスゲーって話でしょうか。どちらにしても気になるところ。ただ、子供に見せるには遅い時間。 世界を変える魔法！アルゴリズミ子研究所 ［Ｅテレ］9月30日(火)… plus.google.com/10758128188852… 2014-09-30 14:51:26
もし先輩女子エンジニアが『アルゴリズム』を図解で教えてくれるとしたら -
2014年7月30日より8月27日まで開催した、paizaオンラインハッカソン（略してPOH![ポー！]）Lite「天才火消しエンジニア霧島 もしPMおじさんが『丸投げ』を覚えたら」ですが、どのような解法が有ったのでしょうか。 今回もPOH恒例の「解説図解」を、天才火消しエンジニア霧島が解説するとしたら、という体で書いてみたいと思います。(特に文体とか変えませんがｗ 最後に霧島壁紙DLが有るので是非最後までお読みください。) ■どのような高速化ステップがあるのか？ 今回の問題ですが、実行時間に大きく影響する計算量別にみたアプローチでは、すべての組み合わせを出して、人数を満たして一番安い組み合わせを見つける全探索[計算量はO(2^N)]と、動的計画法[計算量はq = max(q_i) としてO(Nq) ]（やり方によってはO(NM)）による2種類があります。 また全探索を改良し、効率的な枝刈
組合せ最適化を使おう - Qiita
野菜の選び方はナップサック問題、乗り換え駅探索は、最短路問題といいます。典型問題は、よく研究もされているので、多くの場合、効率的な解法があります。あるいは、定式化がされているので、すぐ解くことができます。あとで、やってみましょう。ここで、あげている全ての典型問題の実行例は、典型問題と実行方法をご覧ください。 汎用問題 最近、私がやっているコンテナの仕事のお話しをします。 世界中の人たちが、いろいろなものを安く買えるのはコンテナ輸送のおかげです。中国などで生産したものを日本やアメリカやヨーロッパに、大量に安く運べるからです。でも、空のコンテナが、どんどんたまります。また中国に戻さないといけません。いつ、どこからどこに戻すかを決めるのが、最小費用流問題になります。ところが、最小費用流問題で表せない制約条件もあります。1 つが、カボタージュとよばれるものです。カボタージュというのは、国内のみの輸
はてなグループの終了日を2020年1月31日(金)に決定しました - はてなの告知
はてなグループの終了日を2020年1月31日(金)に決定しました 以下のエントリの通り、今年末を目処にはてなグループを終了予定である旨をお知らせしておりました。 2019年末を目処に、はてなグループの提供を終了する予定です - はてなグループ日記 このたび、正式に終了日を決定いたしましたので、以下の通りご確認ください。 終了日: 2020年1月31日(金) エクスポート希望申請期限:2020年1月31日(金) 終了日以降は、はてなグループの閲覧および投稿は行えません。日記のエクスポートが必要な方は以下の記事にしたがって手続きをしてください。 はてなグループに投稿された日記データのエクスポートについて - はてなグループ日記 ご利用のみなさまにはご迷惑をおかけいたしますが、どうぞよろしくお願いいたします。 2020-06-25 追記 はてなグループ日記のエクスポートデータは2020年2月28
はてなグループの終了日を2020年1月31日(金)に決定しました - はてなの告知
はてなグループの終了日を2020年1月31日(金)に決定しました 以下のエントリの通り、今年末を目処にはてなグループを終了予定である旨をお知らせしておりました。 2019年末を目処に、はてなグループの提供を終了する予定です - はてなグループ日記 このたび、正式に終了日を決定いたしましたので、以下の通りご確認ください。 終了日: 2020年1月31日(金) エクスポート希望申請期限:2020年1月31日(金) 終了日以降は、はてなグループの閲覧および投稿は行えません。日記のエクスポートが必要な方は以下の記事にしたがって手続きをしてください。 はてなグループに投稿された日記データのエクスポートについて - はてなグループ日記 ご利用のみなさまにはご迷惑をおかけいたしますが、どうぞよろしくお願いいたします。 2020-06-25 追記 はてなグループ日記のエクスポートデータは2020年2月28
問題 I : 乱択平衡二分探索木
東京大学プログラミングコンテスト 2011 問題 L : 𝐿 番目の数字 東京大学大学院情報理工学系研究科 秋葉 拓哉 2011/05/14 東京大学駒場キャンパス 問題概要 • 各ノードに数字が決まってるツリーがある • 以下のタイプのクエリを大量に処理: ある頂点 𝒗 から 𝒘 への経路上の数字で， 𝒍 番目に小さい物を求めよ 頂点番号 頂点 1 に決ま っている数字 例: 頂点 1 から頂点 6 への経路での，3 番目 → 2, 5, 8, 7 の 3 番目 → 7 が答え 問題を変形 • 頂点 1 を根にして，向き付きの木にする • 以下を効率的に計算できるか？ 頂点 𝒗 から根までで 𝒙 以下が何個あるか？ 例: 頂点 4 から根に 6 以下は何個あるか？ → 8, 5, 2 に 6 以下は何個あるか？ → 2 個 それができると？ • それができると，任意の 2 頂
明日使えないすごいビット演算
最適輸送問題（Wasserstein 距離）を解く方法についてのさまざまなアプローチ・アルゴリズムを紹介します。 線形計画を使った定式化の基礎からはじめて、以下の五つのアルゴリズムを紹介します。 1. ネットワークシンプレックス法 2. ハンガリアン法 3. Sinkhorn アルゴリズム 4. ニューラルネットワークによる推定 5. スライス法 このスライドは第三回 0x-seminar https://sites.google.com/view/uda-0x-seminar/home/0x03 で使用したものです。自己完結するよう心がけたのでセミナーに参加していない人にも役立つスライドになっています。 『最適輸送の理論とアルゴリズム』好評発売中！ https://www.amazon.co.jp/dp/4065305144 Speakerdeck にもアップロードしました: https
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Chromeのなかのコンピュータ・サイエンス
ICPC国内予選F解説
【2ch】ニュー速クオリティ:【朗報】 日本のスパコン「京」 ソフトウェアアップデートで、ぶっちぎり世界1位を奪還！！