安全で爆速なRollingHashの話 - Qiita
要約 ロリハ(RollingHash)のModを$2^{61}-1$にすると安全で爆速になってむちゃくちゃ幸せになれます。 前提知識 bit演算に関する基礎的な知識を要求します。 また、RollingHashについては以下で解説しますが、分からない場合は別の記事を読んだほうがいいかもしれません。 RollingHashとは? 開く 「文字列を一つの大きな整数として見る」というのがRollingHashのアイデアです。 まず、0-9のみの数字を含んだ文字列s = "1234567890"を考えてみます。 ここで、この文字列のHash値を文字列を10進数と解釈したときの数値と定義します。 また、$s$の$a$文字目から$b$文字目の前までの部分文字列を$s[a..b]$と書くことにします。 例えば、s = "1234567890"について、$s[1..3]$は1文字目から3文字目の前までの部分
Heapのアルゴリズム - Wikipedia
HeapのアルゴリズムをA (琥珀色)、B (青色)、C (シアン)、D (ダークレッド)の4文字に使ってできる24の置換と23のスワップの図 Heapのアルゴリズムはn個のオブジェクトの全ての置換を生成するアルゴリズムである。1963年にB. R. Heapによって提案された。[1]このアルゴリズムは移動を最小化する。つまり、各置換は前の置換から1ペアを交換するだけで生成され、他のn−2要素を操作する必要はない。1977年の置換生成アルゴリズムの論評で、Robert Sedgewickはこのアルゴリズムをコンピュータによる現時点で最も効率的な置換生成用アルゴリズムと結論づけた。[2] Heapのアルゴリズムによって生成されたn個のオブジェクトの置換列はn+1個のオブジェクトの置換列の最初になっている。したがってHeapのアルゴリズムは無限置換列を生成する(オンライン整数列大辞典の数列 A
頻出パターンマイニング
1 2 3 4 2 X Y X Y 5 X X X X i X i 6 7 8 9 10 X Y Ti 11 12 R.Agrawal and R.Srikant "Fast Algorithms for Mining Association Rules", VLDB 1994 minsup minconf minsup minconf 13 minsup 14 15 minsup minsup 16 minsup minsup 17 18 19 minconf 20 21 minconf minconf minconf 22 23 24 J.Han, J.Pei, and Y.Yin “Mining Frequent Patterns without Candidate Generation” SIGMOD 2000 minsup minsup 25 26 27 28 29 30 31
並列環境におけるreduceとscanアルゴリズム
"fireking" by cmyk1219 1. 概要 reduceとscanはGPGPUなどの並列環境下において重要な役割を果たす関数だけど、あまりこれらの関数、特にscanについて言及している記事はあまり見かけない。なので今回はreduceとscanについて調べた結果をまとめていきたいと思う。 2. reduce, scan関数の概要 2.1. reduce scanについてはreduceが分かればより理解しやすくなるので、ひとまずはreduceから始めることにする。 reduceとは、端的に言うと、対象のリストを与えられた二項演算子で纏め上げる関数だ。とは言っても、いきなりそんなことを言われてもよく分からない。まずは例を見ていこう: >>> import operator >>> reduce(operator.add, [1, 2, 3, 4, 5]) 15 >>> reduce
ロボティクスにおける経路計画(Path planning and Motion planning)技術の概要 - MyEnigma
Robot Motion: Planning and Control (Artificial Intelligence Series)posted with カエレバMichael Brady The MIT Press 1983-03-10 Amazonで検索楽天市場で検索Yahooショッピングで検索 目次 目次 はじめに 経路計画 (Path Planning or Motion Planning)の各アルゴリズム Geometric Analytic Approach Spline Planning Voronoi Diagram Planning Dubins Path Planning Reed-sheep Planning Graph Search Approach ダイクストラ法 A* Dynamic Window Approach State Lattice Approac
Binary Indexed Tree のはなし
Binary Indexed Tree のはなし 保坂 和宏 (東京大学理学部数学科) 第 13 回 JOI 春合宿 2014/03/19 概要 Binary Indexed Tree とは 何ができる？ 何が嬉しい？ 具体的な実装 応用範囲 区間に足す問題 多次元 二分探索 目標 実装できるようにする 「普通に Binary Indexed Tree を使うだけ」の部 分で詰まらないようになる 補助的な道具としてぱっと使えるように Binary Indexed Tree とは Binary Indexed Tree Binary Indexed Tree (Fenwick Tree) Peter M. Fenwick, "A New Data Structure for Cumulative Frequency Tables" (199
Binary indexed tree
CTO, VPoE, テックリードなどリーダーポジションに登用したくなるのはどんな人材か？akihisamiyanaga1
競技プログラミングで使う有名グラフアルゴリズムまとめ
0. はじめに AtCoderなどでは、グラフを扱った問題が多く出るが、その度に一から実装していると時間が掛かりすぎてしまうため、有名なものをあらかじめ持っておく必要がありそう。そこで、Pythonを用いて、ダイクストラ法、ベルマンフォード法、プリム法、クラスカル法、ワーシャルフロイド法を実装した。 コメント、意見等ある方は是非! お待ちしてます! 1. ダイクストラ法 1.1. ダイクストラ法(defaultdictで実装) defaultdictで実装すると、リストで実装するよりも、ノード数$N$が大きい際には高速に動作する。ただし、経路復元の関数は、うまく書けなかった......。 (2019/7/6 追記)結局できました。1.1.1. を参照してください。 import collections import heapq class Dijkstra: def __init__(se
AtCoder橙になりました - ARMERIA
5月4日のAGCで、ついに橙になることができました！！！ 初めてratedに参加したのが昨年の4月上旬なので、およそ1年と1ヶ月での到達となりました。今年中には橙になりたいと思っていたので、予想より遥かに早くてびっくりしています。 ということで記事を書きます。ここまで来ると体系的に書けることがなくなってきたので、全体的にポエム成分が多めです。 解いた問題 AtCoder ProblemsのAC数と、AtCoder Scoresの精進グラフです。何だかんだでStreakをずっと繋いでいます。 全て埋めたのはABC全部と、ARCのE（昔のC）まで、AGCのDまで（今回のやつ解いていませんが）。最近はARC/AGCで残っている問題がかなり難しくなってきたので、JOIとか過去の企業コンとかを細々とやっています。 このゴールデンウィークは、コンテストに出る他はCodeforcesでDifficult
トポロジカルソートと強連結成分分解でWikipediaの特定カテゴリー配下のページをすべて取得する - 終末 A.I.
Wikipediaの特定カテゴリー配下のページをすべて取得するためには、整理されていないグラフデータ特有のいくつかの問題に向き合う必要があります。 一つは、Category:カツラ科と糸井の大カツラのように、サブカテゴリーにはページへのリンクが含まれているが、カテゴリー本体にはページへのリンクが含まれていないケースがあるという問題。 もう一つは、Category:インフォグラム・エンターテインメントームソフトとCategory:アタリのゲームソフトのように、お互いがお互いのサブカテゴリーに含まれてしまっているケースがあるという問題です。 これらの問題は、以下の手順を踏むことで解決できます。 カテゴリーにリンクされているページだけでなく、サブカテゴリー内のリンクを順にたどって含まれるすべてのページを収集する ただし、一度たどったカテゴリーに再度到達した場合、それ以上はそのルートを探索しない
「3の100乗を19で割ったあまりは？」を４通りの方法で計算する - tsujimotterのノートブック
この記事は 日曜数学 Advent Calendar 2015 の 8日目の記事です。（7日目：京大特色入試, コインの問題を解く | kinebuchitomo） ニコニコ動画の「数学」タグを検索するのが日課の日曜数学者 tsujimotter です。 「数学」で検索すると、本当にいろいろな動画が見つかるのです。ぜひお時間あるときに試してみてください。 日曜数学 Advent Calendar ８日目の本日は、そんなニコニコ動画で見つけた動画から１つ、みなさんにご紹介したいと思います。 今回ご紹介したいのは、初音ミクが歌うボカロ曲です。タイトルは 「 を で割ったあまりは？」 です。そのタイトル通り、まさに数学の問題をテーマとした珍しい曲です。まずは、ぜひリンク先の動画をご覧ください。 tsujimotter は、心地よいメロディーが素敵な曲だと思いました。この記事を書いている最中、バッ
ビット列による部分集合表現 【ビット演算テクニック Advent Calendar 2016 1日目】 - prime's diary
はじめに この記事はビット演算テクニック Advent Calendar 2016 www.adventar.org の1日目の記事です。 この記事ではビット演算を使って有限集合の部分集合を表現、操作するテクニックを紹介します。 本文中で説明を省略した部分については、詳しい説明のある参考文献を紹介しておきます。 2021/01/03: 高速ゼータ変換/メビウス変換/畳み込みに関する部分を全面的に書き換えました。 表現方法 S={A,B,C,D}という4要素の集合があったとします。 各要素を次のように2進数の数字と対応付けます。 A: 0001 B: 0010 C: 0100 D: 1000 こうすると、Sの部分集合は存在する要素のビットごとの論理和を取ることで4ビットのビット列として一意に表すことができ、例えば {A,B,C}: 0111 {B,D}: 1010 のようになります。 以後、
AtCoderで青になるまでにやったこと - 真面目なやつ
先週のエクサウィザーズコンテストで、念願の青になりました！ ということで、例のごとく青になりました記事を書こうと思います。 ほんとは「コードギアス見てたら青になってました！」だけ書こうと思っていたんですが、結構真面目に書いちゃいました。 目次 簡単な自己紹介 水色になるまでに必要なこと 青になるまでにやったこと 青になるためにやったけど多分必要なかったこと 競プロをやる上でめっちゃ参考にしたブログ どんな人ですか 今年から東京大学工学部システム創成学科4年になります。 研究室は確率統計をやることになりました。大学院は型システムを専攻したいなぁと思っております。 プログラミングを始めたのは2017年夏くらい。 本格的に始めたのは2017年11月。 競プロを始めたのは2018年6月10日です。 約10ヶ月で青になりました。（世間には1年経たずに黄色になったりする人がいて怖いですね...） パフ
不確実性と上手く付き合う意思決定の手法
予測モデルの不確実性を減らすActive Learning, モデルの不確実性を予測結果に反映するThompson Sampling, オンライン最適化など
劣微分・劣勾配と共役関数の可視化 - Qiita
最適化や凸解析の本のわりと序盤に登場するトピックに 劣微分・劣勾配 と 共役関数 があります。いずれも凸関数にとって特に重要な概念ですが、通常の書籍だと当然動きのない図でしか描かれていないため、イメージしづらい方もいるでしょう。そこで代表的な凸関数について、劣微分・劣勾配および共役関数のアニメーションを作りました（初めて本格的にGoogle Colabを使いました）。本の図よりはもっと鮮やかにイメージでき理解が深まるかと思います。なお、厳密には「閉真凸関数」などと呼ぶべき箇所を簡単のために単に「凸関数」と記述しています。厳密な定義などは専門書（例えば [福島2001,冨岡2015]）を参照ください。 多変数関数 $f$ のある一点 $x$ での傾き（昇る方向）を表すベクトルを 勾配 と呼び $\nabla f(x)$ と表しますが、微分不可能な点では勾配を求めることができません。この問題を
TechCrunch
In an attempt at damage control, the CEO of the equity management startup Carta, Henry Ward, today emailed customers, telling them that if they are concerned about “negative press” tied to the out In the Lego-like world of Roblox, about a hundred blocky avatars march through a lamplit street, wielding Palestine flags that are larger than their own animated bodies. Characters dressed like cartoo
いもす法 - いもす研 (imos laboratory)
いもす法とは，累積和のアルゴリズムを多次元，多次数に拡張したものです．競技プログラミングでは 2 次元 1 次のものまでしか出題されませんが，2012 年の研究成果としてこれをより高次元の空間により高次数のいもす法を適用することにより信号処理分野・画像処理分野において利便性があることがわかっています． いもす法の基本: 1 次元 0 次いもす法 最もシンプルな「いもす法」は 1 次元上に 0 次関数（矩形関数や階段関数などのように上部が平らな関数）を足すものです． 問題例 あなたは喫茶店を経営しています．あなたの喫茶店を訪れたそれぞれのお客さん i\ (0 \leq i \lt C) について入店時刻 S_i と出店時刻 E_i が与えられます（0 \leq S_i \lt E_i \leq T）．同時刻にお店にいた客の数の最大値 M はいくつでしょうか．ただし，同時刻に出店と入店がある場
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
pakencamp_slide.pdf
All the good tutorials found for Competitive Programming - Codeforces
プログラミングコンテストでのデータ構造
