もうひとつの全方位木DP - ei1333の日記
なにもかくことがないね（えーん） もうひとつの全方位木DPなんですが、任意の全方位木DPが記述できるかは確認してない(多分できないと思う(うく))ので期待はしないでね ゴメンネ この記事は Competitive Programming (2) Advent Calendar 2018 の20日目の記事です。 adventar.org ei1333.hateblo.jp ※ 辺視点のほうが考えやすいので、辺視点で考えます。 頂点1を根とする根付き木があって、各辺についてDPの計算に必要な値が求まっているとします（根に向かう辺の値だけあればよい）。 下図のように別の頂点（今回は頂点 ）に根をうつしたときの木について求めたい場合は、もともとの木の根から離れる辺の値についての値をトップダウンに求めていきます。 矢印の先が、それが指す頂点からみたときの辺の値を示すこととします。 この操作により、頂
Main Page - Competitive Programming Algorithms
Home Algebra Data Structures Dynamic Programming String Processing Linear Algebra Combinatorics Numerical Methods Geometry Graphs Miscellaneous Last update: April 17, 2024 Algorithms for Competitive Programming¶ The goal of this project is to translate the wonderful resource https://e-maxx.ru/algo which provides descriptions of many algorithms and data structures especially popular in field of com
【決定版】コンピュータ将棋のHASHの概念について詳しく | やねうら王 公式サイト
いまどきの将棋ソフトを使っていると、「HASH 50%」などと表示されている。これはHASH利用率と呼ばれる。この数字が大きくなってくると探索の効率が悪くなる。要するに潤沢にメモリがある場合に比べると弱くなる。これは、どれくらいの値までであるなら適切なのか？HASH利用率が99%にならない限りHASHには余裕があるものなのか？HASHはどういう仕組みになっているのか？HASH利用率が50%の状況で、ハッシュ衝突はしているのか？など、わりとソフトを長年使っていても知らない人が多いのでここに原理から詳しく説明した決定版的な記事を書く。 ShogiGUIや将棋神やねうら王に表示されている「HASH」とは何ですか？ 一度探索した局面を保存しておく表です。 この表に登録するときにハッシュ(hash)という値を使って登録するため、ハッシュテーブル(hash table)と呼ばれます。これを略して(値と
ABC113-D 「Number of Amidakuji」 発展解法 - Mister雑記
この記事は以下に移植されました。 tiramister.net
ABC113-D:Number of Amidakuji - 思考の墓場
フィボナッチ数列が登場しがち。 問題 D - Number of Amidakuji 解法 こういうのはdpが有効である。を位置まででに行くようなあみだくじの数とおく。の遷移先はのいずれかである。あとはそれぞれの遷移先について，そこに遷移するような位置での横線の置き方の数がわかればよく，これはbit全探索することででできる。本番でここが思いつかなかった。悲しいね。 ところで，次のような事実がある。 縦棒が本のあみだくじのある位置での横線の置き方の数は，フィボナッチ数列の第項をとすると，に等しい。フィボナッチ数列とは，で定義される数列である。 証明 に関する帰納法で示す。左から順に縦棒にと番号をつけることにしよう。のときはそれぞれ通りである。での成立を仮定して，のときの横棒の置き方の数を求めよう。縦棒と縦棒の間に横棒を置かないとき，横棒の置き方はからまでの横棒の置き方に等しく，通りある。縦棒
【PDF】包除原理 解ける数え上げの範囲を広げよう
tsutaj (@_TTJR_) Hokkaido University M1 October 16, 2018 tsutaj (Hokkaido Univ.) October 16, 2018 1 / 78 1 2 ϕ Uncommon Ball and Boxes 3 lahub and Permutations 3 LCM Rush Enumeration 4 (2) Rotated Palindromes Everything on It 5 tsutaj (Hokkaido Univ.) October 16, 2018 2 / 78 ▶ 積集合 (intersection) 和集合 (union) tsutaj (Hokkaido Univ.) October 16, 2018 3 / 78 ▶ ▶ ▶ (intersection) ▶ (union) 1 積集合 (inter
傾きの単調性が要らない Convex Hull Trick - kazuma8128’s blog
はじめに 傾きに単調性がなくても insert ができる Convex Hull Trick を書きたいなーと思ったものの, 平衡二分木で書くのはめんどくさそうだし定数倍遅そうとか考えて色々調べてたら, セグメントツリーを使った簡単な方法を見つけたので, 備忘録的に書いておきます. http://codeforces.com/blog/entry/51275 ちなみにここの記事のコメント欄で見つけたものです. 中国では Li Chao Segment Tree と呼ばれているらしいです. あと, 自分なりの勝手な解釈が入ってるので, 元のものと少し違うかもです. Convex Hull Trickとは Convex Hull Trickとは, 直線集合を管理するデータ構造で, 以下の2種類のクエリをオンラインで処理できます. 直線の追加クエリ ： 直線 f(x) = a * x +
ベズーの等式 - Wikipedia
ベズーの等式（ベズーのとうしき、英: Bézout's identity）は初等整数論における定理である。ベズーの補題（ベズーのほだい、英: Bézout's lemma）とも呼ばれる。 ベズーの等式 ― a と b を 0 でない整数とし、d をそれらの最大公約数とする。このとき整数 x と y が存在して ax + by = d となる。さらに、 d は ax + by と書ける最小の正の整数であり、 ax + by の形のすべての整数は d の倍数である。 x と y は (a, b) のベズー係数 (Bézout coefficients) と呼ばれる。それらは一意的ではない。ベズー係数の組は拡張ユークリッドの互除法によって計算できる。a と b がどちらも 0 でなければ、拡張ユークリッドの互除法から かつ であるような 2 つの組の一方が出る。 ベズーの補題は任意の主イデアル整
『みんなのデータ構造』発売および予約開始のお知らせ – 技術書出版と販売のラムダノート
ご来店ありがとうございます。 本日より、新刊『みんなのデータ構造』の発売を開始しました。紙書籍の発送は7月25日前後を予定しています。電子書籍は購入後すぐにお読みいただけます。 『みんなのデータ構造』は、Pat Morin氏による “Open Data Structures” を翻訳して書籍として出版するものです。Pat Morin氏による原文は、クリエイティブコモンズ継承ライセンス（CC BY）で公開されており、誰でも自由に教材として活用できるだけでなく、内容に手を入れて別のライセンスで再配布したり、販売したりできるようにされています。堀江氏、陣内氏、田中氏による翻訳と、ラムダノート株式会社による編集も、すべてCC BYで公開しており、同様に自由に利用していただくことが可能です。 書籍版『みんなのデータ構造』（紙書籍および電子書籍）につきましては、クリエイティブコモンズライセンスではなく
競プロでよく使われる組み合わせアルゴリズムの意味がよくわからない人に送るまとめ
しゅういち @hideh_1231 @tempura_pp けんちょんさんのブログのB問題の解法見てたんですけど、1/n!がどうしてああなっているのかよくわからないのです… 2018-06-05 01:49:40 てんぷら @tempura_cpp @hideh_1231 とりあえずmod11で7の逆元を考えてみましょうか。 逆元を求める作業がかけて1になる、つまり7*xを11で割ったあまりが1になるようなxを求める作業だというのはよいですか 2018-06-05 02:02:20 リンク Wikipedia 逆元 逆元 （ぎゃくげん、英: inverse element）とは、数学、とくに抽象代数学において、数の加法に対する反数や乗法に関する逆数の概念の一般化で、直観的には与えられた元に結合してその効果を「打ち消す」効果を持つ元のことである。逆元のきちんとした定義は、考える代数的構造によ
UnionFindTree に関する知見の諸々 - noshi91のメモ
2018/08/17 ポテンシャル付きUnionFindTreeの記述を変更し、RetroactiveUnionFind についての記述を追加しました。 2019/07/19 集合内の要素の列挙についての記述を追加しました。 はじめに UnionFindTree って知ってますか？ 競プロでは恐らく最も使用頻度の高いデータ構造だと思います*1。この記事ではプログラミングコンテストで役に立つものから全く役に立たないものまで、UnionFindTree に関するいくつかの知見を書き留めておきます。記事の最後に各内容の実装例を貼っておきます。 計算量と実装のバリエーション UnionFindTree の操作辺りの計算量が O(α(N)) であることは良く知られていますが*2、この計算量を達成するアルゴリズムはいくつかのバリエーションがあります。併合時に木の高さと大きさのどちらを指標にするかという
よくやる二項係数 (nCk mod. p)、逆元 (a^-1 mod. p) の求め方 - けんちょんの競プロ精進記録
1. 典型的な二項係数の求め方 競プロをしていると、「 mod 」を計算する場面にしばしば出くわします。最近では、 であることが多いですね。 mod の計算方法は、時と場合によって色んな方法が考えられますが、すぐ下で紹介する方法が最も頻繁に使用されています。多くの AtCoder のトッププレイヤーたちも使用している形式で、高速です。 使い方としては、最初に一度前処理として COMinit() を呼び出します。その後は、毎回 COM(n, k) 関数を呼べばよいです。 前処理 COMinit()：計算量 クエリ処理 COM(n, k)：計算量 1-1. mod の実装 この実装では、ACL (AtCoder Library) の modint を用いています。さらに下に、modint を使わない実装も載せています。 #include <iostream> using namespace s
二項係数 mod 素数を高速に計算する方法 [累積和, フェルマーの小定理, 繰り返し二乗法, コンビネーション, 10^9+7] - はまやんはまやんはまやん
要望 nCk mod 10^9+7を高速に計算したい n,k≦10^5 追記：llはlong longのことです 使ってるテンプレートはこんな感じです。 #include<bits/stdc++.h> #define rep(i,a,b) for(int i=a;i<b;i++) using namespace std; typedef long long ll; 高校で習うやり方でやると… ll mod = 1000000007; //--------------------------------------------------------------------------------------------------- ll C(int n, int k) { ll res = 1; rep(i, 0, k) res = (res * (n - i)) % mod; rep(
![二項係数 mod 素数を高速に計算する方法 [累積和, フェルマーの小定理, 繰り返し二乗法, コンビネーション, 10^9+7] - はまやんはまやんはまやん](https://cdn-ak-scissors.b.st-hatena.com/image/square/e5b388d4aa8524d7a1ac008f05bde9a2dccdd7a8/height=288;version=1;width=512/https%3A%2F%2Fogimage.blog.st-hatena.com%2F10328537792368951407%2F17391345971651666693%2F1582545411)
競技プログラミングで青になるまでにやったこと - hogecoder
リクエストを受けたので、最近流行りの「○○色になるまでにやったこと」記事を書きたいと思います。 自分の現在の位置について少し話すと、AtCoder 青上位・ Codeforces 青中位・CSAcademy 青中位・ TopCoder 青下位くらいです。全身青いです。近いうちに青卒業できるように頑張っているところです。なので「青色になったので書いている」わけではないのですが、青を目指している人々にとって参考になる記事になっていれば幸いです。 水色 → 青 これは Twitter などでもよく言われていることなのですが、 AtCoder の ABC / ARC の D がコンスタントに通せる ようになると青が見えてくると感じています。問題セットにもよるので一概には言えませんが、 C 問題は呼吸、 D 問題は最低でも 20 分以内には片付けたいところです。なので、コンスタントに通すにはどのよう
Link-Cut 木 - ei1333の日記
えーむずかしかったのでかきます. まちがってたらごめんね. コードはverifyしたので間違ってないはずです. あとからなんか書き加えたり修正したりするかも. 最初に このスライドがわかりやすいです(それはそう). ソースコードをほとんどこれ参考にしてるので, こっちも参考にしてね. プログラミングコンテストでのデータ構造 2 ～動的木編～ from Takuya Akiba www.slideshare.net HL分解 突然ですが, みなさんはHL分解を知っていますか. 僕は知っています(イキり). HL分解は木を分解するアルゴリズムの一つです. 次のような木が与えられたとします. 根はどこでもいいんですが, ここでは頂点 を根とする根付き木として考えます. 与えられる木 次に, それぞれの頂点に対して部分木の大きさ(頂点数)を求めます. 部分木の大きさを求めた木 最後に, それぞれの
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Exponential algorithm making Windows XP miserable could be fixed | Ars Technica
ゆかたゆさんのツイート: "この前教えて頂いた、高速にsqrtを計算する闇コードなのです。 https://t.co/UrZiLMlNJX… "
C++ STL: Policy based data structures - Codeforces
高速な倍精度指数関数expの実装
ceptree on Twitter: "離散フーリエ変換がすっきりするアニメーション。ただし説明がないとわからないと思う。 https://t.co/bD1AqeM0oR"