実務に現れる多くの事例が組合せ最適化問題にモデル化できることが再認識されるようになりました． しかし，その多くはNP困難問題と呼ばれる計算困難な組合せ最適化問題であり，どのようにアプローチすれば良いか悩んでいる人は少なくないと思います． 本講演では，実務に現れる組合せ最適化問題に対する実践的なアプロ…
How to tackle hard combinatorial optimization problems arising in real applications?
実務に現れる多くの事例が組合せ最適化問題にモデル化できることが再認識されるようになりました． しかし，その多くはNP困難問題と呼ばれる計算困難な組合せ最適化問題であり，どのようにアプローチすれば良いか悩んでいる人は少なくないと思います． 本講演では，実務に現れる組合せ最適化問題に対する実践的なアプロ…
Algorithms with Go
Algorithms with Go is free, but you need to provide a working email address to gain access. I won't spam you and unsubscribing is very easy. "I understand how basic algorithms work, but I can't actually implement them in code" Don't worry, you aren't alone! Not everyone will admit it, but many developers feel exactly what you are feeling when they get started with coding, algorithms, and more. Whe
Reservoir Sampling
Feedback on these posts is welcome and solicited. If you find mistakes, corrections can be made by pull request at GitHub. In my last post I covered a technique to infer distribution parameters from a sample taken from a system with the aim of calibrating a simulation. This post is about how to take samples, using reservoir sampling algorithms. This is not a subject I have ever had much exposure t
数学オリンピックの問題にプログラミングで挑戦！ ～数え上げから幾何問題まで～ - Qiita
1. はじめに はじめまして！高校 2 年生の square1001 です。 私は主に「競技プログラミング」に取り組んでいます。情報オリンピックの世界大会の日本代表になったり、TopCoder や AtCoder などのプログラミングコンテストにも出場したりしています。コンテストに出場するだけでなく、問題の作成も積極的にやっています。 ところで、みなさんは、「日本数学オリンピック」という大会を知っていますか？これは、日本全国の高校生以下を対象にした、数学の問題解決能力を競う、**全国的にとても有名な大会です。**本記事では、日本数学オリンピックの予選で出題される問題を、難しい数学的知識や数学的考察を使わずに、「コンピューターの高い計算能力」と「アルゴリズムの力」でチャレンジしてみます！ 導入 - コンピューターが世界を変えた！ プログラミングを実務などでやっている方の中には、「システムやア
Algorithm for Drawing Trees
I recently wanted to take a hierarchy of items and draw them in a nice tree structure. For example, a Family Tree. At the time, I thought “This will be easy, I’ll just Google for an algorithm to determine the X,Y position of each node, then do something to draw each node on the screen”. But it turns out Googling for a simple and easy-to-follow algorithm for drawing nice trees is very hard. My init
木構造を描くアルゴリズムについて（Reingold-Tilford Algorithm） - What is it, naokirin?
最近、UnityでPlayable APIというものを調べる機会がありました。 その際にそのPlayableの木構造をUnity上で表示できるEditor拡張としてPlayableGraphVisualizerというものがあると知ったので軽く見ていて、「Reingold Tilford」というものが出てきて調べていたので、それをまとめておきます。 （ちなみに、PlayableGraphVisualizer - https://bitbucket.org/Unity-Technologies/playablegraphvisualizer） 結論としてはこの「Reingold Tilford」は「Reingold Tilford アルゴリズム」と呼ばれるもので、木構造を階層的に“きれいに”表示するためのアルゴリズムです。木構造のグラフ表示の機能を持ったJavascriptのライブラリなどでは
最短経路問題総特集！！！～BFSから拡張ダイクストラまで～ - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? 基本的アルゴリズム（幅優先探索など）から応用（経路復元、拡張ダイクストラなど）まで、最短経路問題に関するアルゴリズムを総特集しました。 基本的なグラフ理論の用語については、次を参考にしてください。 グラフ理論 用語集 queueなどのデータ構造の用語については、次のスライドの後半を参考にしてください。 C++ STL講習会 by @e869120 最短経路問題とは 一般的に、次のような問題とされます。 $V$ 頂点と $E$ 辺からなるグラフが与えられる。頂点 $u$ と 頂点 $v$ を結ぶパスのうち、重みの総和が最も小さいものはどれ
Z-algorithm詳解と具体例 - Senの競技プログラミング備忘録
新ABCになって、6問制になってから、2020/1/6現在まで、Z-algorithmは二回(500, 600)出題されてます。これからも継続して出そうな「文字列照合」で強力なツールとなるZ-algorithmですが、既存資料たちは非常によく説明されていますが、どこか筆足らずのような印象を受けました。 そこで、この記事でZ-algorithmに絞った説明、実際の挙動の説明、実装例を紹介します。 以下のページ、PDFを参考にしてます。 snuke.hatenablog.com 文字列アルゴリズム from HCPC: 北海道大学競技プログラミングサークル www.slideshare.net Z-algorithmで何ができるか？ 文字列Sに対して、S[i : j]という記号を、Sのi番目からj番目(いずれも0-idx)までの連続部分文字列とします。 例えば、S="abcde"で S[1 :
[多項式・形式的べき級数]（１）数え上げとの対応付け | maspyのHP
概要 ある種の数え上げの計算は、多項式・形式的べき級数に対する計算と結び付けることができます。数え上げの問題を、多項式・形式的べき級数に対する計算と読み替えて、代数的な式変形により答を得る手法が、競技プログラミングにおいても注目され始めているようです。 さまざまな問題を文字式の問題に翻訳できるようになっておけば、文字式に対して理解を深めるだけで、幅広い問題に対する解決力を同時に伸ばしてしまうことができます。また、中高数学の学習で学んだ文字式や関数の式変形に対する能力が利用できることも魅力になると思います。 ここでは、数え上げの対象を多項式・形式的べき級数の問題に対応させる練習をしていきましょう。（逆に言うと、対応させた先の「多項式・形式的べき級数の問題を解く」方法の説明は、この記事では扱いません。） 多項式への言い換えは、経験がないうちは、唐突に感じてしまうことがあると思いますが、頻出のパ
![[多項式・形式的べき級数]（１）数え上げとの対応付け | maspyのHP](https://cdn-ak-scissors.b.st-hatena.com/image/square/d3b83cb0b151f85f4ab582d54745629884ec04db/height=288;version=1;width=512/https%3A%2F%2Fmaspypy.com%2Fwp-content%2Fuploads%2F2023%2F01%2F5Dth6Yjz_400x400.jpg)
LIS でも大活躍！ DP の配列使いまわしテクニックを特集 - Qiita
0. はじめに 動的計画法の解法に対しては、「一次元 DP」や「二次元 DP」といった呼称でよびたくなりがちです。たとえば ${\rm dp}[i] := i$ 番目の地点まで到達するまでの最小コスト というような DP テーブルを用いるような DP1 は一次元 DP であり、 ${\rm dp}[i][w] := N$ 個の品物のうち最初の $i$ 個の品物の中から、重さが $w$ を超えない範囲でいくつか選んだときの、選んだ品物の価値の総和の最大値 というような DP テーブルを用いるような DP2 は二次元 DP である、といった具合です。後者はいわゆるナップサック問題に対する DP として有名ですね！ 二次元 DP の配列を再利用して一次元へ しかし今回は、DP を一次元や二次元とよぶことにあまり意味がないかもしれない...という話をします。たとえばナップサック DP は、なんと実
乱数について本気出して考えてみる｜TechRacho by BPS株式会社
プログラミングをやっていると、様々な乱数に出会います。乱数に関しては大勢の研究者が色々な研究結果を出しているため、種類も増え、いったいどれを使えばいいのかと悩む原因にもなります。 大勢が研究し利用している分野ですから、私以外でも大勢が乱数に関する記事を書いているため、あえて新しい記事を書く価値は高くないかもしれません。まあ、既に理解している人はここで記事を閉じるか、暇つぶし程度の感覚で読んでいただくと良いかと思います。 真乱数と疑似乱数 プログラミングの世界の中でいわゆる "乱数" として扱われることが多いのは擬似乱数です。疑似、と付くからには、これは実のところ乱数ではないと言えます。とは言え、擬似乱数を乱数でないと言ってしまうと話が終わってしまうので、疑似乱数を含む乱数を広義の乱数とします。この記事で扱うのは広義の乱数です。逆に、狭義の乱数、本物の乱数は真乱数と言います。 本物と言いまし
pattirudon氏のアルゴリズムについて - oupoの日記
背景 ポケモンソード・シールドのレイドバトルと呼ばれるイベントではxoroshiro128+という疑似乱数を使ってモンスターを生成している。 これについて、セーブデータを抽出せず、ゲームのプレイから得られる情報からxoroshiro128+の乱数の種を復元できないかということが問題になっていた。 xoroshiro128+は状態遷移はF_2線形 *1であるが、状態から乱数値を得るのに算術和を使っており、それが非線形なため復元は難しいのではないかとされていた。 しかし、驚くべきことにpattirudon氏はそれを可能にした。 github.com ゲームでのxoroshiro128+の使われ方 ゲームのセーブデータにレイドバトルの各巣ごとの64bitのseedが格納されている。 seedはレイドバトルのイベントを起こしたり、日付が変わったりするごとに以下の式で更新される。 seed = (s
コーディングインタビューの対策とその意義 (1/2) - 16bitのメモランダム
１．コーディングインタビューとは何か コーディングインタビュー（Coding Interview、またはProgramming Interview）とは、1時間ほどの制限時間内に小さなプログラミング問題を解かせる面接形式のことをいう。プログラマー、またはデータサイエンティストなどの採用試験として、米国を含むいくつかの国で用いられている。「物理的なホワイトボード上にプログラムを書く」という形式で実施されることが多い。「オンライン上の共有エディタで書く」といった形式のこともある。Googleなどは自社のYoutubeチャンネル動画でも説明している。 出題される問題としては、例えば、「複数の数字numbersと整数kが与えられたとき、合計がkとなる数字の組を1つ出力せよ」といったものがある。この問題は有名なので通称が付いており、Two Sumと呼ばれる。 Two Sumの一例。与えられた数値の並
二分木 - Rustではじめるデータ構造とアルゴリズム（第1回）
Rustの特徴のひとつは、所有権(ownership)・移動(move)・借用(borrow)の概念です。これらがコンパイル時に厳格にチェックされることにより、古くから未定義挙動でプログラマを悩ませてきたダングリングポインタなどの問題がなくなり、メモリ安全性がもたらされます。 しかし一方で、自分で多少複雑なデータ構造を定義しようとする場合にはコンパイルを通すだけでもかなりの知識・力量が要求されます。 この（不定期）連載では、 Rustではじめるデータ構造とアルゴリズム と題し、プログラミングコンテストなどでよく見かける基礎的なデータ構造とアルゴリズムを、できるだけシンプルにRustで実装していきます。 &, &mut, Box, Rc, Cell, RefCell などの使い分けや、なぜそれを使う必要があるかの解説を、実例を通して行います。 第1回は、最もシンプルな木構造である 二分木 を
すごいTrie - Qiita
「to」がキーで「7」がバリューです。これを trie で表すと下図のようになります。 Trie - Wikipediaより引用 ノードの中に書かれている「tea」や「in」がキーであり、ノードの下に書かれている「3」や「5」がキーに対応する値です。 あるノードのキーは、その親ノードのキーに、親ノードから伸びる有向辺に書かれている文字を、付け足した文字列です。実際には、ノードには直接キーが保存されず、そのノードに到達するまでの辺のラベルの列がキーになってます。 接頭辞がノードと対応するので prefix tree とも呼ばれます。 計算量 計算量は色々な表現をすることが可能ですが、ノードの分岐は高々アルファベットの種類数なのでこれを定数とすれば、$ m $を文字列の長さとして以下の操作が$ O(m) $で出来ます。（アルファベットの種類数を考慮すると$\log$が付きます。） 文字列の検索
赤黒木の本質 - 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 2019 16日目の記事です。 15日目は@minaminaoさんによる「すごいTrie」です。 17日目は@takilogさんによる「Fréchet距離の計算アルゴリズム」です。 はじめに この記事では有名なデータ構造である赤黒木がなぜあのようなトリッキーな定義になっているのかその本質について解説します。 赤黒木の定義を見てトリッキーと思うかどうかは個人差あるかと思いますが、少なくとも僕が初めて赤黒木を学んだ時はなぜこのような定義になっているのか、そしてどうやって思い
データ構造とアルゴリズム - Qiita Advent Calendar 2019 - Qiita
データ構造とアルゴリズムに関する話題なら何でもOKです。 メジャーなものからマイナーなものまで様々なトピックを好きなように書きましょう！ カレンダーの愛称は「デーアルアドカレ」でお願いします！ 関連： 以下は「文字列アルゴリズム Advent Calendar」を含みますが、実態は何でもありで様々なデータ構造とアルゴリズムが紹介されています。 文字列アルゴリズム Advent Calendar 2016 - Qiita 文字列アルゴリズム Advent Calendar 2017 - Qiita データ構造とアルゴリズム Advent Calendar 2018 - Qiita データ構造とアルゴリズム #2 Advent Calendar 2018 - Qiita
群ラベル制約付き最短路問題 -
この記事は「データ構造とアルゴリズム Advent Calendar 2019」 日目の記事です．*1 日目は @921603 さんによる「Proximity search：列挙アルゴリズムの新たな構築手法」です． 日目は @TsuMakoto さんによる「IDA* with Pattern Databaseでパズルを解く」です． グラフにおける最短路問題は組合せ最適化の古典的な問題ですよね．今回は，その制約付きの変種に対する効率的なアルゴリズムを紹介したいと思います．元ネタは，来年 月に開催される SODA という離散アルゴリズムの国際会議に採択されている以下の論文です． Yutaro Yamaguchi: A Strongly Polynomial Algorithm for Finding a Shortest Non-zero Path in Group-Labeled Grap
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Xor Filters: Faster and Smaller Than Bloom Filters – Daniel Lemire's blog
Challenge: find Twitter memes with suffix arrays