Sliding Window Aggregation - data-structures
#Sequences Operations 半群の列 を扱う． 空間計算量 空の状態でデータ構造を作成する 時間計算量 を計算する 時間計算量 を末尾に追加する 時間計算量 を削除する 時間計算量 Summary Queue をつの Stack でシミュレートする技法を用いる それぞれの Stack は要素の他に、最初の要素からその位置までの累積和も管理する 先頭側の Stack 全体と末尾側の Stack 全体の fold 結果はわかっているので，それらを結合すればに答えられる 先頭側の Stack が空でないとき，単に先頭側の Stack を pop する 先頭側の Stack が空になった際に末尾側の Stack の全要素を反転して先頭にする この操作にはかかるが，つの要素が Stack に される回数を考えると償却定数時間になることが言える． References Knapsack
競プロでWAが出たときのランダム入力データ生成入門 - ARMERIA
概要 競技プログラミングで提出コードがWAになったとき、実際に不正解となるような入力データを入手できると役に立つ場合があります。ただ多くのコンテストサイトでは、コンテスト中には入力データを見ることはできません。 そのような時に、小さめの入力データを乱数で大量生成して、提出コードと愚直解法の結果を突き合わせ、答えが一致しないものを探すという方法があります。もちろんそのようなデータを確実に得られる保証はありませんが、もし見つかればデバッグの大きな助けになります。 今回の記事はその手順を紹介します。また、生成コードの例としてC++とPythonを扱います。 手順1：愚直解法コード作成 まずは問題に対する愚直解法のコードを書きます。小さな入力データで回すので、 だろうと だろうと気にせず書きましょう。これがバグっていると破綻するので計算量よりも正しさ優先です。 C++等の場合はコンパイル時に提出コ
Runの列挙 (Main-Lorentz algorithm) - 迷いませんか？
Main-Lorentz Algorithm 概要 文字列のrunをで列挙することができるアルゴリズム runは文字列内に現れる部分文字列の繰り返しのことで、特に長さが極大で周期が最小のものを指すっぽい 情報としては区間と周期を持ち、実際に使うときは(l, r, period)としてs[l, r)の周期がperiodみたいに持つ 注意するべきなのは、繰り返しはピッタリである必要はなくて(r - l) % period != 0でもよい ただしr - l >= 2*periodであるもののみを考える 例 "mississippi" 区間: [1, 8), period: 3 長さ3の"iss"が7/3周期分ある s[0] != s[0+period(= 3)] かつ s[8] != s[8-period(= 5)]だからこれ以上伸ばせなくて長さが極大である あとは周期1で2周期分のやつが3つ
競技プログラマのための抽象セグメント木実装のすすめ - beet's soil
午前起床！（素振り） はじめに 先にこっちを見て beet-aizu.hatenablog.com うし木（一点更新区間取得）について書きます おまけ なんだこれはたまげたなあ（わかる人にはわかる記事、わからない人にはわからない） beet-aizu.hatenablog.com 前提知識(C++) 厳密性や歴史的背景をガン無視しています。あんまりあてにしないでください。 雰囲気を掴むためと割り切って読んでもらえるといいと思います。 C++のバージョンは14を前提にしていますがそのうち17に上がりそう？ struct is 何 競技プログラマならpairやtupleくらいは使ったことがあると思いますが、自分でそういうのを作るための機能です。 たとえば struct Node{ int fi,se; }; Node v; v.fi=0;v.se=1; みたいな感じで使えます。 つまり、大きな
External memory algorithm - Wikipedia
In computing, external memory algorithms or out-of-core algorithms are algorithms that are designed to process data that are too large to fit into a computer's main memory at once. Such algorithms must be optimized to efficiently fetch and access data stored in slow bulk memory (auxiliary memory) such as hard drives or tape drives, or when memory is on a computer network.[1][2] External memory alg
様々なrate limitアルゴリズム - Carpe Diem
概要 インターネットに晒されているWebサービスでは TV等で紹介されたことによる大量流入 悪意ある人物からの攻撃 クライアントのバグに依る大量リクエスト など、本来想定していた以上のトラフィックが来ることはよくあります。 単純にシステムを構築すると大規模トラフィックに対応できずシステムがスローダウンしてしまうため、何かしらrate limitをかけておいた方が良いです。 ただしrate limitと一口に入っても色々あるため、今回は主なrate limitアルゴリズムを紹介します。 Leaky bucket Leaky bucketはデータ転送レートを一定にする（＝上限を設定する）アルゴリズムです。 下の図のように、様々な流量の水流がそのバケツに流れ込んでも小さな穴からは一定の水流が流れ出す仕組みです。 ref: What is the difference between token
スーパーマリオのジャンプのアルゴリズム - Qiita
先日、気持ちのいいジャンプを目指してというQiitaの記事を見かけました。記事中では、マリオのジャンプについても触れられています。マリオというと、マリオブラザースやスーパーマリオブラザース等々、色々あるのですが、これはおそらくスーパーマリオブラザースの事だと思われます。ジャンプアクションゲームといったらスーマリですね。 そのマリオのジャンプの仕組みは「マリオの速度ベクトルを保存しておいて座標を計算するんじゃなくて～」と書かれていて、別サイトのブログへのリンクが張られています。 マリオのジャンプ実装法とVerlet積分 ただ、この記述については不正確であるという別のブログもあったりします。 マリオの完コピvol.28 ジャンプの解析と修正 ホントのところはどうなんでしょうか？世界で最も有名なゲームのジャンプがどのように処理されているのか気になったので調べてみることにしました。 原典にあたる
動的計画法によるDVDのディスク分割の改善
こんにちは。「家族アルバム みてね」の開発チームに所属している黒川と申します。今回は、その「みてね」の機能の1つで、写真や動画をDVDにして注文できる機能を動的計画法を使って改善した話をします。 「みてね」では家族の写真や動画をアップロードし、アプリ上で月ごとに振り返ることが可能になっています。一方、たとえば自宅のテレビやパソコンでまとめて振り返りたいという要望もあり、「みてね」では最長過去1年間の写真や動画をDVDにまとめて注文することができます。 このときに問題となるのがDVDのディスク分割です。1年分の写真や動画はともすると1枚のディスクに収まりきらず、複数のディスクに分割する必要があります。いままでは、動画を月ごとに分けて各ディスクに入れていく、というシンプルなアルゴリズムで分割を行っていました。しかし、ユーザーさんからは「1枚のディスクにすこしの動画しかないがどうなっているのか」
Googleが量子超越を達成 -新たな時代の幕開けへ（前編）
2019年10月23日、Googleが量子超越を実現したという論文を公開し、量子コンピュータの歴史に新たな1ページが刻まれた。 「量子超越」は、量子コンピュータの歴史における大きな一歩である。Googleの研究チームは、最速のスーパーコンピュータを使っても1万年かかる問題を、Googleの53量子ビット(qubit)の量子コンピュータは10億倍速い、200秒で解けることを示したという。 今後、Googleが示した量子超越性に対して様々な角度から検証がなされていくだろう。量子超越性は、物理学及び計算科学の歴史の1ページに刻まれるべきマイルストーンである一方、量子超越性や量子コンピュータの実用化についても、様々な憶測や誤解が広まっている。 この記事では、Googleが示した量子超越性について前編と後編の2つのパートに分けて解説していく。 前編では、量子超越性を実証するための基本的な考え方、量子
【画像処理超入門】アルゴリズムの仕組みと実装方法を簡単に解説
画像処理とは 画像処理（Image Processing）とは、コンピュータを用いて画像に対して様々な処理を行う技術の総称です。 画像処理には大きく分けて以下2つの目的があります。 画像から画像への変換 画像の編集や加工、見やすさの改善を行うことです。 例えば、画像の拡大・縮小、高画質化、ノイズ除去などが含まれます。 画像から情報の取得 画像を分析し、有用な情報を抽出することです。 例えば、顔検出、自動運転技術における障害物認識、医療機器でのCT画像の分析などが含まれます。 「画像から画像への変換」を画像処理、「画像から情報の取得」をコンピュータビジョンと区別する場合もあります。 画像処理技術を活用した分析は、自動運転技術における障害物認識、医療機器でのCT画像の分析など多方面で活躍しています。 画像センサ（カメラ）は、他のセンサーと比較しても多くの情報を取得できるため、対応できる課題分野
素数テーブルをO(n)で構築する - 裏紙
からまでの数が素数であるかどうかの配列(素数テーブル)をで構築する。 はじめに まず、このような素数テーブルの構築といえばいわゆるエラトステネスのふるいが有名です。小さい方から、その倍数にバツマークを付けていくと、で構築できます。実装も素直で簡単です： const int N = 10000001; bool prime[N]; void build_sieve(){ fill(prime,prime+N,true); prime[0] = prime[1] = false; for(int i=2; i<N; ++i)if(prime[i]){ for(int j=2*i; j<N; j+=i) prime[j] = false; } } 実装 次にの実装を見てみます。 const int N = 10000001; int mind[N]; vector<int> pr; void b
文字列の頭良い感じの線形アルゴリズムたち３ - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ
昨日の記事の続きです。 Z algorithm 文字列が与えられた時、各 i について「S と S[i:|S|-1] の最長共通接頭辞の長さ」を記録した配列 A を O(|S|) で構築するアルゴリズムです。 例えば、 aaabaaaab 921034210 こんな感じです。 Z algorithmのテクニックはManacherとよく似ています。ですので、以下の解説記事を読む前に少し考えてみると分かるかもしれません。 さて、結論から言うと、Z algorithmのコードは以下のようになります。 A[0] = S.size(); int i = 1, j = 0; while (i < S.size()) { while (i+j < S.size() && S[j] == S[i+j]) ++j; A[i] = j; if (j == 0) { ++i; continue;} int k
LCAをベースに構築するAuxiliary Treeのメモ - 日々ｄｒｄｒする人のメモ
(2019/09/15 20:50頃追記) ただAuxiliary Treeと書くと(一般的すぎて)齟齬を生む可能性が高いので、タイトル及び一部文章を変更しました。申し訳ないです。今回はLCAをベースに構築するAuxiliary Treeについて取り上げてます。 最近、LCAを元に構築する Auxiliary Tree を使う問題に出会ったので書いた。 CodeChef July Challenge 2019 で以下の問題があった。 smijake3.hatenablog.com 自分は Auxiliary Tree を使わず解いたが、想定解法が Binarization of a tree + Centroid Decomposition on Edge + Auxiliary Tree だったらしい。 discuss.codechef.com 以下を参考にしている。 虚树学习笔记 -
競プロのための高速フーリエ変換
■「フーリエ変換って知ってる？」 ●「フーリエ変換ですか？ 信号処理でもするんですか、先輩」 ■「いや、競プロで使えるようになりたいなって」 ●「ああ、畳み込みの高速化ですか。あれは高速フーリエ変換をそのまま使うだけですからね」 ■「勉強しようと思って色々調べたんだけど、なかなか理解できなくて」 ●「私もうまく説明できるかわかりませんが、お話しましょうか」 離散フーリエ変換（DFT） フーリエ変換の仲間たち ●「フーリエ変換の仲間には色々種類があるんですけど、競プロで使うのは離散フーリエ変換（DFT: Discrete Fourier Transform）ですね」 ■「離散ってことは、連続もあるんだよね」 ●「はい。ざっくり 4 種類あります。フーリエ変換では元の信号を別の信号に変換するんですが、元の信号が周期信号だと変換後は離散信号（数列）になります」 ■「周期信号っていうのは、決まった
第4回 Asprova プログラミングコンテスト - Roy_Rの競プロ日記
2019/08/23~08/30にAtCoder上で開催されたマラソン型のプログラミングコンテスト『第4回Asprovaプログラミングコンテスト』に参加しました。 焼きなまし法が初めて成功して嬉しかったのと、ツカモさんにこう言われたので、記事を書いてみることにしました。 恐縮です…。 さぁ、ろいさんもブログ記事を書いて競プロ後継者erの糧となるのです！ — ツカモ (@tsukammo) August 30, 2019 ということで、この記事は、自分(Roy_R)がコンテスト期間中にやったことを時系列にまとめて、他の人の役に立つといいなっていうのとともに、マラソンマッチ楽しい！ と主張するものです。(あと、自分の復習のため) やったことを簡潔に列挙するのが本当はいいのかもしれませんが、このブログのタイトルは『競プロ日記』ですし、僕は日記調の文章しか書けないので、日記的な感じで考えたこととか
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Data Structure for Disjoint Sets
10秒で衝突するUUIDの作り方
Lionel Page on Twitter: "Such a cool way to explain logic gates. https://t.co/6Wgu2ZKFCx"
data-structures
近似最近傍探索の最前線
