Algorithms
というかチートシートを作りました。C++版APIに準拠しています。URLはこちら：https://www.notion.so/AtCoder-Library-ACL-01a562f6c38e481e88f5a838fd78eb0e www.notion.so
遅延伝搬セグメント木の復習をしたので、beetさん作問のセグ木コンテスト（2019/9/6開催）の問題を解いてみた。 難しいけど面白かった（解けたので）。
LeetCode Weekly Contest 146のQ4でN個の点の3次元マンハッタン距離の最大値を求める問題が出たのでメモ。内容的には マンハッタン距離が最大である2点を選ぶ問題 - ICPC突破専用ザク を理解する過程で噛み砕いたものなので、上記記事を既読の方は本稿を読む…
蟻本p.337 "なお、接尾辞配列を構成するアルゴリズムは他にも多数存在しています。例えば、SA-ISと呼ばれるアルゴリズムなど、線形時間で非常に高速に構成するアルゴリズム等も存在していますが、プログラミングコンテストではほとんどの場合で上のアルゴリ…
個ある何かの0個以上から成る集合をビットの整数で表すことにする。 このとき、集合に含まれる要素が個なら全部でビット立っている 。 （__builtin_popcount(S) == k）この集合の部分集合をすべて列挙しようとすると、空集合も含め通りある。 集合Sとしてあ…
蟻本拾い読みプログラミングコンテストチャレンジブック [第2版] ～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～posted with amazlet at 18.08.20秋葉拓哉 岩田陽一 北川宜稔 マイナビ 売り上げランキング: 20,173Amazon.co.jpで詳細を…
ABC100の解説で触れられていた「中央値の中央値 (median of medians)」のことを調べたメモ。 厳密なmedian値でなくていいのでそれっぽい値をO(n)で求める方法。少なくとも上下に3n/10個ずつ、それより小さい（or 大きい）値が存在することが示せる。 真のmed…
「期待値の線形性」について、けんちょん先生やふるやん先生の解説を参考にしながら自分の理解を整理するためのメモ。 期待値の線形性そのもの E[ax+b]=aE[x]+E[b] は分かってるし、「E[Σf(x)]の形で書けるものはΣE[f(x)]に書き換えて解ける」という事実にも…
ゼータ変換／メビウス変換は互いに逆変換の関係なのはわかったんだけど…どっちがどっち？というか、4種類あるんだけど…どれがどれ？（けんちょん先生が全ての謎を解いてくれるのを待ちつつ）
先日ARC埋めの一環でATC001のC問題（高速フーリエ変換）を解いたのだけれど、こういう畳み込み問題はDFT（discrete Fourier transform；離散フーリエ変換）の代わりに NTT（number-theoretical transform；数論変換）という "整数（剰余環）を用いたDFT" で…
先日の連分数の計算と拡張ユークリッド互除法って少し似てるなと思ったというメモ。（連分数の計算で次の項を求める時にやっている操作ってユークリッドの互除法そのものだし当然か）拡張ユークリッド互除法というのは、 を満たす を求める方法。 を で割れば…
6月は永続データ構造強化月間（そういうことにしました）、ということで qnighy先生の Re永続データ構造が分からない人のためのスライド で紹介されていた、IOI 2012の"Crayfish Scrivener"を解いてみたメモ。
連分数 - WipikediaこないだのJune Long ChallengeのEuler Sumを考えてる時に Mark Jason Dominus氏のスライド Arithmetic with Continued Fractions を読んだ時のメモ。連分数とかいじるのって多分昔SICPを読んだ時以来。
CodeChefのフォーラムで June Challenge 2017の問題 Chef and Prime Queries (PRMQ) の解法を読んでいて discuss.codechef.com素因数分解をするのに This can be done by creating a Smallest Prime Factor array in the sieve function itself. とあって。…
ふと2-SATの事が気になって、復習がてらPractice RoomでSRM464のDiv1 Medium問題を開いてみた。（ちなみにSRM464には出場している）SAT (充足可能性問題, SATisfiability problem) についてはここの読者の皆さんはご存知とは思います。NP完全問題でおなじみ…
前回までのあらすじ（〜9/8）9/18からScalaで学ぶ関数型プログラミングのクラスが始まったけど、参加するかは未定。 参加中のクラス Quantum Mechanics and Quantum Computation (Umesh Vazirani, UCB) - 7/17開講; 全課程(8週)終了 Week 8 (最終週) Grover…
前回までのあらすじ（〜8/26）現在、量子力学＆量子計算のクラス（Umesh Vazirani先生）と、8/26に参戦したアルゴリズムのクラス（Robert Sedgewick先生＋Kevin Wayne先生）を受講中。量子計算の方がメイン。 Quantum Mechanics and Quantum Computation (Um…
nokunoさん来るかな？と思って参加登録したアルゴリズム勉強会＠芝浦四丁目 http://partake.in/events/b913f41d-5ec6-4310-89e4-342820616641 @viperlike のくのにうむ摂取しに行きましょうか！— naoya tさん (@naoya_t) 8月 24, 2012 「アルゴリズムイント…
cafelierさんの500のコード見てたら LL gcd(LL a, LL b) { while(a) swap(a, b%=a); return b; } あ、そうか。swapってそう使えるのか。短くていいな。
皆さんの脳内でも赤西仁×黒木メイサが2-3-4木でいうところの3-節として内部表現されていることと存じますが、今日は赤黒木を題材にGraphvizで描いたグラフをGIFアニメにしてみたいと思います。というか単なる Graphviz入門です。いきなりGraphvizの本家ドキ…
はい、毎度おなじみのグラフ描きたいだけのエントリですw今回のお題は「三分探索（ternary search）」。二分探索（binary search）は割とおなじみかと思うのですが、二分探索が単調増加(減少)関数fについてf(x)=kとなるxを求めるのに対し、三分探索（とか黄…
