行列木定理の証明 - blogoid
0. はじめに 今回は行列木定理(Kirchhoff's theorem)の証明を紹介してみようと思います。 行列木定理とは、全域木の個数の数え上げに関する定理です。証明方法はいくつかありますが、今回は漸化式を用いた全域木の個数の数え上げとの対応を見ることで定理を証明してみたいと思います。 1. 定理の内容 頂点数$n$のループを含まない多重無向グラフ$G$が与えられたとします。対角成分に頂点の次数を並べた行列から、隣接行列*1を引いたものをラプラシアン行列といいます。つまり、$G$に対する$n$×$n$ラプラシアン行列$L=(l_{ij})$は$$\begin{aligned}l_{ij}=\begin{cases}\text{頂点iの次数}&(i=j)\\ \text{頂点iと頂点jの間の辺の数}\times (-1)&(\mathrm{otherwise}) \end{cases}
コーディングインタビューの対策とその意義 (2/2)：インタビュー本番中に何を考えるか - 16bitのメモランダム
前回の記事（下のリンクを参照）では、コーディングインタビュー前日までに役立つ知識とインタビューの意義を考察した。 en9.hatenablog.com この記事では、コーディングインタビュー当日の思考過程について考えてみる。 コーディングインタビュー最中の思考 あなたがGoogleやFacebookといった、競争の激しいテック企業のコーディングインタビューを受ける状況を想像してほしい。 何ヶ月にも及ぶ練習を乗り越え、準備は万端だ。 だが、面接官が問題の設定を説明し始めると、自分の鼓動が速まっていくのを感じる。 なんてことだ、今までやったことない問題だ。 あれだけ解いたのに。 いったいどうアプローチすればよいのだろう？ どのデータ構造を使えば解けるのかも分からない。 動的計画法のような気も、単なる分割統治法の気もする。 それともgreedyに解けるのか？ どんな境界例が考えられるのか頭に思い
Atcoder ABC32 D - ナップザック問題を分岐限定法で爆速で解く - Qiita
概要 ナップザック問題を分岐限定法で爆速（$n<2000, v_i<10^{12}, w_i<10^{12}$を$1$秒）で解きます。実行時間ベースで今のところ3位です。提出はこちら これは競技プログラミング 解説 Advent Calendar 2017の16日目の記事です。 ナップザック問題 ナップザック問題とは、重さ制約$W$と$n$個の荷物価値ペア($v_i, w_i$)が与えられて、$\displaystyle \max_{S \in 2^n, \sum_S w_i \le W} \sum_S v_i$を求める問題です。Atcoder ABC 32 - D - ナップザック問題は、様々な$n$, $v_i$, $w_i$の制約のもとで、この問題を解くという趣旨でした。 この問題は、以下の3つのDP解を、テストケースごとに作成することで通すことができます（提出）。 (1) $n$が
Splay Treeの可視化Webページを簡易的に作った - 日々ｄｒｄｒする人のメモ
この記事は IQ1アドベントカレンダー2019 の 5日目の記事です。 adventar.org 今回はちょっとした小ネタ記事として、splay treeのvisualizationを簡易的に作った話を書きます。 はじめに Splay Treeとは? bottom-up top-down visualizationの実装 参考 はじめに 最近、Splay Treeがぬるぬる動く様子を眺めて癒やされたい(?)、という気持ちになり自作したくなったのでさくっと作りました。 作成期間はこのアドベントカレンダー記事を書こうとしてからの直近1週間です。 Splay Treeとは? スプレー木 - Wikipedia Splay tree - Wikipedia 平衝二分探索木の1つであり、参照したノードを回転しながらrootに持ってくるsplay操作によって平衝を保つ。 splay操作では zig,
ゲーム理論の講義ノート
結構頑張って作ってるのに授業用ウェブサイトに置いているだけではあまり読まれることもなさそうなので，授業で作った資料の中で公開することに多少の価値がありそうなものについては定期的にこちらで公開してみることにします． 授業に関するよりup-to-dateな情報や資料は私のteaching関係websiteをご覧ください． Advanced Microeconomics II の講義ノート（英語）（2019/12/04掲載） 西南財経大学の大学院向けのミクロ経済学の授業でゲーム理論を教えるにあたって作成した講義資料です（授業ではノートのメインな部分はほとんどカバーしていますが，いくつかの理論的なトピックはスキップしています）．理論研究自体というよりも，実証・応用研究の研究者になることを目指す学生にどのように動機づけを与えるか，そして「理論の人たちの興味」がどのように応用に結びついているかをなんと
Proximity search：列挙アルゴリズムの新たな構築手法 - Qiita
Deleted articles cannot be recovered. Draft of this article would be also deleted. Are you sure you want to delete this article? Proximity search：列挙アルゴリズムの新たな構築手法 本記事は「データ構造とアルゴリズム Advent Calendar 2019」３日目の記事です． 2 日目は @yurahunaさんによる「三角形分割の数え上げとランダムサンプリング」です． 4 日目は @ygussanyさんによる「群ラベル制約付き最短路問題」です． この記事の元ネタは，STOC 2019で発表されたProximity searchに関する論文です．証明等に関しては省略します．詳しく知りたい方は下記文献にあたってください．また，グラフアルゴリズムにおけ
データ構造とアルゴリズム - 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
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; みたいな感じで使えます。 つまり、大きな
スーパーマリオのジャンプのアルゴリズム - Qiita
先日、気持ちのいいジャンプを目指してというQiitaの記事を見かけました。記事中では、マリオのジャンプについても触れられています。マリオというと、マリオブラザースやスーパーマリオブラザース等々、色々あるのですが、これはおそらくスーパーマリオブラザースの事だと思われます。ジャンプアクションゲームといったらスーマリですね。 そのマリオのジャンプの仕組みは「マリオの速度ベクトルを保存しておいて座標を計算するんじゃなくて～」と書かれていて、別サイトのブログへのリンクが張られています。 マリオのジャンプ実装法とVerlet積分 ただ、この記述については不正確であるという別のブログもあったりします。 マリオの完コピvol.28 ジャンプの解析と修正 ホントのところはどうなんでしょうか？世界で最も有名なゲームのジャンプがどのように処理されているのか気になったので調べてみることにしました。 原典にあたる
動的計画法によるDVDのディスク分割の改善
こんにちは。「家族アルバム みてね」の開発チームに所属している黒川と申します。今回は、その「みてね」の機能の1つで、写真や動画をDVDにして注文できる機能を動的計画法を使って改善した話をします。 「みてね」では家族の写真や動画をアップロードし、アプリ上で月ごとに振り返ることが可能になっています。一方、たとえば自宅のテレビやパソコンでまとめて振り返りたいという要望もあり、「みてね」では最長過去1年間の写真や動画をDVDにまとめて注文することができます。 このときに問題となるのがDVDのディスク分割です。1年分の写真や動画はともすると1枚のディスクに収まりきらず、複数のディスクに分割する必要があります。いままでは、動画を月ごとに分けて各ディスクに入れていく、というシンプルなアルゴリズムで分割を行っていました。しかし、ユーザーさんからは「1枚のディスクにすこしの動画しかないがどうなっているのか」
【画像処理超入門】アルゴリズムの仕組みと実装方法を簡単に解説
画像処理とは 画像処理（Image Processing）とは、コンピュータを用いて画像に対して様々な処理を行う技術の総称です。 画像処理には大きく分けて以下2つの目的があります。 画像から画像への変換 画像の編集や加工、見やすさの改善を行うことです。 例えば、画像の拡大・縮小、高画質化、ノイズ除去などが含まれます。 画像から情報の取得 画像を分析し、有用な情報を抽出することです。 例えば、顔検出、自動運転技術における障害物認識、医療機器でのCT画像の分析などが含まれます。 「画像から画像への変換」を画像処理、「画像から情報の取得」をコンピュータビジョンと区別する場合もあります。 画像処理技術を活用した分析は、自動運転技術における障害物認識、医療機器でのCT画像の分析など多方面で活躍しています。 画像センサ（カメラ）は、他のセンサーと比較しても多くの情報を取得できるため、対応できる課題分野
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
Private Presentation
pakencamp_slide.pdf
AtCoder灰・茶・緑色の方必見！二分探索を絶対にバグらせないで書く方法
Data Structure for Disjoint Sets
10秒で衝突するUUIDの作り方
Lionel Page on Twitter: "Such a cool way to explain logic gates. https://t.co/6Wgu2ZKFCx"