ゲームを解く！Educational DP Contest K, L 問題の解説 - Qiita
0. ゲームを解くとは 世の中には将棋や、囲碁や、オセロのような複雑で難しいゲームから、マルバツゲームや、割りばしゲームや、立体三目並べのような比較的単純なゲームまで、たくさんの種類のゲームがあります。 この種の二人プレイのボードゲームにはある共通の特徴があります。それは 双方が最善を尽くした場合において、「先手必勝」か「後手必勝」か「引き分け」かが予め決まっている。 そして無限の計算時間と計算機資源さえあれば、それを容易に解析できる。 という点です。このように 「先手必勝」か「後手必勝」か「引き分け」なのかを解析する その必勝手順を求める できれば + α として初期盤面だけでなく、すべての局面について「先手勝ち」か「後手勝ち」か「引き分け」かも特定して最善手も求める という営みが「ゲームを解く」ということであり1、それができたならばそのゲームを「完全に理解した」ということができます。本
木と計算量 後編 〜全方位木DP〜 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ
前編はこちら 前編は汎用性も高い話題でしたが、後半は少しマニアックで雑学的です。 予習 全方位木DPについて予習します。 全方位木DP、有向辺に関するDPだと思うのが分かりやすい。 1. 青い矢印は普通の木DPで下から順に求まる 2. 根から出る矢印は全部求まっているので、根に入る矢印も求められる（ここの計算量改善に総和とって引き算とか左右からの累積和とかが出てくる） 3. 同様に赤い矢印を上から順に求めていく pic.twitter.com/p4bl6rXzGn— ꑄ꒖ꐇꌅꏂ🐾 (@snuke_) 2019年1月6日 補足として、以下の問題を解く具体的な実装も置いておきます。 N 頂点の木が与えられる。 頂点 v を含む部分木の個数を全ての v について求めよ。 制約：1 ≦ N ≦ 10^6 こういう、根を全部試して根付き木の問題を一括で計算する、的な状況で全方位木DPが活躍します。
木と計算量 前編 〜O(N^2)とO(NK)の木DP〜 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ
この記事はCompetitive Programming Advent Calendar 2018の46日目の記事として書かれました（嘘） 最近、木上のアルゴリズムの面白い計算量解析が２つ話題になったのでまとめておきます。 予備知識 まず、https://web.archive.org/web/20150819082918/https://topcoder.g.hatena.ne.jp/iwiwi/20120428/1335635594 について復習します。 iwiさんのブログとは違う、より直感的な解析方法も紹介します。 以下の問題を考えます。 N 頂点の木が与えられる。 頂点 1 を含む頂点数 K の根付き木の個数を求めよ。 制約：1 ≦ K ≦ N ≦ 3000 典型的な木DPの問題です。 解法は以下の通りです。（解法の細かい説明は本題ではないので追わなくて大丈夫です） 頂点 1 を根
Algorithms by Jeff Erickson
🔥1st edition, June 2019 🔥 (Amazon links: US, UK, DE, ES, FR, IT, JP) This web page contains a free electronic version of my self-published textbook Algorithms, along with other lecture notes I have written for various theoretical computer science classes at the University of Illinois, Urbana-Champaign since 1998. More information Get the book More algorithms lecture notes Models of computation n
半群の和が計算できる Deque - noshi91のメモ
概要 競プロでは知る人ぞ知るスライド最小値というテクニックは、より一般化されて sliding window aggregation という名前で知られています。本記事では両端で要素の追加/削除、全体での半群の和を得るというクエリを全て償却定数時間で処理するアルゴリズムの実装について説明します。 アルゴリズム 値と先頭からの累積和をペアにして要素として持つ stack を考えます。するとこの stack を2つ背中合わせにするように持てば、追加/削除は対応する stack に操作を行えばよく、累積和の更新も定数時間で実行可能です。また、総和を計算するクエリも左右の stack の累積和を単純に足せばよく、定数時間です。ここで問題となるのが、片方の stack から pop を多く呼び出すと空となり、それ以上 pop が出来なくなることにあります。ここで pop したいが対応する stack
量子アニーリングがチョットワカルようになる記事 - Yahoo! JAPAN Tech Blog
この例は規模が小さく、ちょっと頭で考えてれば答えがわかってしまうかもしれません。けれど、巨大なホテルだとしたら頭で考えるのが難しそうです。とにかくこの問題例をアニーリングマシンで解いてみることにします。 問題を量子アニーリングマシンで解くときは基本的に次のような流れに沿って解きます。 (1) 問題の抽出(2) 量子アニーリングマシン (イジングモデル) へのマッピング(3) アニーリングの実行(4) 解の解釈 (1) 問題の抽出 まずは、対象の問題を量子アニーリングで解くことのできるようにできる限りシンプルな問題に切り出すことが必要です。 この問題は実はグラフ頂点彩色問題に帰着させることができます。 グラフ頂点彩色問題とは、任意のグラフ G=(V,E) と色総数 K が与えられたとき、すべての頂点を、隣接する頂点 (すなわち、辺で接続されている頂点) が同色にならないという制約下でK色に塗
簡単なトライ - LINE ENGINEERING
これはLINE Advent Calendar 2018の14日目の記事です。 LINEの上村です。今日は文字列です。 はじめに トライ (trie)は文字列の集合を索引化し高速な検索を可能にするデータ構造であり、領域効率や高速性を向上させた多様なアルゴリズムが提案され種々の実装が公開されています。 IPアドレスの検索、形態素解析器における辞書からの候補の列挙、キー入力時のオートコンプリートといった有益な応用があり、文字列業界以外でもご存知の方は多いかもしれません。 この記事で紹介するsftrieは簡単で効率よい新たなトライ表現とそのC++実装です。 主な特徴は以下の通りです: 大きなアルファベットをサポートします。また、いわゆるNULL文字も必要としないため、バイト列やASCIIコードからUnicode、単語等に割り振ったIDのような一般の整数まで、様々な値を文字型として扱えます ノード
Big Sky :: flatten() に再帰は必要ない
先日、mopp さんが Vim に flatten() を追加するプルリクエストを追加してくれたのだけど、その時の記憶を整理する為に書く自分の為の記事。 add flatten() to flatten list by mopp - Pull Request #3676 - vim/vim - GitHub I'm a bit confused by the maxdepth argument. I would expect it to specify the maximum depth of the r... https://github.com/vim/vim/pull/3676 Vim script のリストは以下の様に、異なる型が混在できる。Ruby や他のスクリプト言語でも一般的。そしてスクリプト言語には一般的にリストを平坦化する為の flatten という関数ないしはメソッドが
The Swiss Army Knife of Hashmaps | Arrow of Code
A while back, there was a discussion comparing the performance of using the hashbrown crate (based on Google’s SwissTable implementation1) in the Rust compiler. In the last RustFest, Amanieu was experimenting on integrating his crate into stdlib, which turned out to have some really promising results. As a result, it’s being planned to move the crate into stdlib. While the integration is still ong
最短包含区間問題 - Qiita
本記事は、「データ構造とアルゴリズム Advent Calendar 2018」 11日目の記事です。 10日目の記事は @Gaccho 氏による「完全ローグライクダンジョン生成アルゴリズム🚪」でした。 12日目の記事は @Gaccho 氏による「「アルゴリズムこうしん」のアルゴリズムを作成する」です。 本記事では、「最短包含区間問題」という問題についてお話します。 本記事には新しい概念や高度なテクニックは登場しないため、アルゴリズムを生業とされている皆様にはお楽しみいただけないかもしれませんが、どうぞ最後までお付き合いください。 問題定義 以下のような、区間集合に対する問題を考えます。なお特に断りがない限り、本記事に登場する数値はすべて正の整数値であるとします。 最短包含区間問題 事前入力： $[1 ..N]$上の、互いに包含関係のない（ネストしない）区間の集合 $I$ クエリ入力：
Implicit Treap - 競プロ練習記録
この記事はCompetitive Programming (1) Advent Calendar 7日目の記事とISer Advent Calendar 8日目の記事として書かれました。 TL;DR Implicit Treapを実装しました。以下の操作がクエリ毎O(logn)で可能です。 配列のランダムアクセス 配列の任意箇所へのinsert 任意要素のerase 任意区間に対するsum, max, min等のクエリ 任意区間に対する加算、更新等のクエリ 任意区間のreverse 任意区間のrotate Implicit Treap上の二分探索 この記事では一般的なTreapから順を追って説明していこうと思うのでImplicit Treapだけコピペして使いたい！という人は最後の方へどうぞ。 追記 bug fixとかをした最新の実装はここにあります。 [12/24] [] operato
定数時間MSBアルゴリズム - Qiita
1-4ビット目yyyyはxxの値によって変わりますが、フラグの値は$X$のMSBと$A$中の１の位置で決まります。$A$の１が$X$のMSBより左にあるとフラグは０、さもなければフラグは１です。よって$X$に対してこの引き算を全部試せば、MSBの数だけ１が立ったフラグが手に入ることになります。 これを利用して$X’$を作っているのが下の図です。$X$にフラグをつけて√w個コピーしたあと、フラグで区切られた各区間（ブロック）に対して上記の引き算を一度に実行し、その後yyyyの部分をビットマスクで0クリアしたのが$X'$となります。$X'$のビット長は$\sqrt{w}(\sqrt{w}+1)=w+\sqrt{w}$なので、２ワード上で演算すれば$X'$は定数時間で計算できるというわけです。 X'の１を定数時間で数える方法について １が立っているビットを定数時間で数えるのは結構難しいのですが、
ハミング距離と鳩ノ巣原理 - Qiita
見ての通り地獄です。$k = 30$ で六百五十二京九千九百六十九兆八千九百三億千七百九十三万（ろっぴゃくごじゅうにけいきゅうせんきゅうひゃくろくじゅうきゅうちょうはっせんきゅうひゃくさんおくせんななひゃくきゅうじゅうさんまん）になります。3 4 そもそも、線形探索より高速に検索することが目的でしたので、$Q$ のサイズがデータの個数 $n$ を上回っては元も子もないのです。例えば $n$ が10億でも、$k = 8$ で $Q$ のサイズは $n$ をあっけなく上回ります。 でもまぁ安心してください。「だから皆さん線形探索を使いましょう！」なんてオチではないですし、まだ鳩も出てきてないです。以下では、この転置インデックスを用いた解法を上手く活用し、高速に問題を解くマルチインデックスという手法を紹介します。 マルチインデックス ここからは、転置インデックスによる解法を大きいパラメータに対し
01-BFSのちょっと丁寧な解説 - ARMERIA
先日Twitterで少し話題になったので書いてみます。データ構造とアルゴリズム Advent Calendar 2018 の8日目の記事でもあります。 「01-BFS」というものをちょっと丁寧に解説します。これは以下のような問題を解くことができるアルゴリズムです。 辺の長さが0または1である有向グラフにおいて、ある1つの始点から全頂点への最短路の長さを効率的な計算時間で求めよ。 ※図のグラフは非循環（DAG）ですが、必ずしもDAGである必要はないです。 この記事では01-BFSの解説の前に「ダイクストラ法」「幅優先探索」をそれぞれ復習し、その流れで01-BFSを解説します。必須ではありませんが、これら2つのコードを書いたことがない人は是非そちらからやってみてください。 ダイクストラ法 多くの人は 深さ/幅優先探索→ダイクストラ法 の順に学ぶと思いますが、今回は逆の記載順にしています。 ダイ
ワンス・アポン・アン・アルゴリズム - 共立出版
本書は、「計算」にまつわる様々な概念を、日常生活やよく知られた物語にたとえて描いている。『ヘンゼルとグレーテル』は森を抜けて家に帰るためのアルゴリズムを実行しており、『恋はデジャ・ブ』は決定不可能な問題の話であり、『シャーロック・ホームズ』はデータ構造を駆使して事件を解決している。『ハリー・ポッター』の世界の魔法は型と抽象化を通して理解でき、『インディ・ジョーンズ』は探索の複雑さを体現していることになる。議論されている内容は、アルゴリズム、記号と表現、データ構造、P=NP問題、言語・構文・曖昧さ、制御構造とループ、再帰、停止性問題、型、アルゴリズムの検証など多岐にわたる。 ・森に置き去りにされた『ヘンゼルとグレーテル』は、どうやって家に帰った？ ・『シャーロック・ホームズ』は犯人を見つけるのにどんなデータ構造を使った？ ・『インディ・ジョーンズ』が潜り抜けた死の罠はどれくらい難しい問題か？
ハルヒ問題（最小超置換問題）の紹介 - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? はじめに 皆さんこんにちは、「データ構造とアルゴリズムAdvent Calendar」の作成者、文字列大好き文字列初心者の@kgotoです。 一昨年と去年は「文字列アルゴリズムAdvent Calendar」を作り、去年は念願の完走をしました。有り難いことに反響も大きかったです！ 今年は「データ構造とアルゴリズム」と対象を広げて、一瞬でカレンダーの枠が埋まるのでは！？とドキドキしていたのですが、蓋を開けてみるとなんとまだ11日も空きがあります！！ ちょっと寂しいですね。。。 もちろん無理に参加してくれとは言いませんが、この記事を読んでち
競プロとかに使うアルゴリズム実装メモ（二分探索、2次元累積和、しゃくとり法） - 甲斐性のない男が機械学習とか最適化とかを綴るブログ
はじめに アルゴリズムメモ第３段です。今回は二分探索法、２次元累積和、しゃくとり法と様々な問題に使える汎用的なアルゴリズムを書いていきます。 今回は勉強のため、アルゴリズムの本質的な部分を記述した抽象クラスと実際の問題を解く具象クラス（関数オブジェクト）を分け、テンプレートメソッドパターンもしくはストラテジパターンを用いてコーディングしました。 二分探索 用途 広義単調増加関数または広義単調減少関数が条件を満たし、かつ、条件成立と不成立の境界となる点を探索（条件成立と不成立の境界が１つのみ） ソート済み配列から条件が成立する値が存在するかの判定 アルゴリズムのポイント 変数を探索範囲の最小値、変数を最大値で初期化 をの中点（例えば、で求める）として、が条件を満たすか否かを判定 このとき、見つけたい点（条件成立と不成立の境界）がより小さいか、大きいかはが広義単調増加（減少）関数なのでわかる
意外と解説がない！動的計画法で得た最適解を「復元」する一般的な方法 - Qiita
NTTデータ数理システムでアルゴリズムを探求している大槻 (通称、けんちょん) です。 好きなアルゴリズムは最小カットやマッチングですが、会社ではなぜか「動的計画法が好きな人」と呼ばれています。今回は動的計画法を用いて得られた最適解を復元するための汎用的な方法について紹介します。 0. はじめに 動的計画法を用いて効率的に解くことのできる最適化問題は数多くあります。パッと思いつくだけでも ナップサック問題 迷路などの最短路問題 区間スケジューリング問題 音声認識パターンマッチング問題 レーベンシュタイン距離 発電計画問題 分かち書き 隠れマルコフモデル ... などなど、多種多様な分野の問題を動的計画法によって効率よく解くことができます。このように、分野横断的な活用をできることが、動的計画法をはじめとした数理工学的手法の特長であり醍醐味であると常々感じています。今回は動的計画法によって得ら
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
https://amy.dev/?p=853
Strings with hamming distance exactly $1$