CS Academy: Connected Tree Subgraphs - pekempey's blog
問題ページ modified 2018年12月21日 map を使ったこれはあやまりですので、キをつけてください。 modified 2018年12月17日 map を使うと書きやすいらしい。たとえば height を求めるには次のように書けばよい。 map<int, int> dp[100000]; vector<int> g[100000]; void dfs(int u, int p) { if (dp[u].count(p)) return; dp[u][p] = 0; for (int v : g[u]) if (v != p) { dfs(v, u); dp[u][p] = max(dp[u][p], dp[v][u] + 1); } } 解法 $O(n^2)$ 解法は TDPC の木という問題と同じ。 dp[v]:=vの部分木の番号の振り方を計算する。子が a,b,c,d だ
拡張ユークリッドの互除法 - 唯物是真 @Scaled_Wurm
\(a, b\)の2つの正の整数が与えられたときに\(ax+by=\gcd(a, b)\)となるような整数\(x, y\)のうちの1つの組を計算するアルゴリズム たとえば5リットルの入れ物と7リットルの入れ物を使って11リットルの水を汲む方法などが計算できる 昔こんなツイートをしてたようですがようやく理解できた気がします(遅すぎ。中国の剰余定理の方はまだ) 中国の剰余定理とか拡張ユークリッドの互除法とかわかってない(´・ω・｀)— 無限猿(id:sucrose)@39月病 (@Scaled_Wurm) 2014年12月23日 Wikipediaの説明を読んだらよくわからなくて？？？となったがいろいろググってなんとか理解した \(a, b\)の2つの整数についてユークリッドの互除法をやるときに、\(ax_1+by_1=a\)と\(ax_2+by_2=b\)みたいに両辺がある形で考えて\(a(
グラフとネットワーク - okamoto7の日記
明日から『グラフとネットワーク』という講義が始まるので，いろいろと思うことを書いておく． まず，このような授業をやることを依頼されて，それでシラバスとか考えて，立ち上がったわけだけども，この講義の名前が『グラフ理論』になりそうだったが，それは避けられた．もっとも，『グラフ理論』をやってもよいわけだし，私が『グラフ理論』の講義をすることもできるし，実際『グラフ理論』の講義もやったことがあるのだけれども，この『グラフとネットワーク』は「グラフ理論」の講義ではない．実際依頼された内容を考えれば『グラフ理論』などという名前を付けることは，学生に対して間違った印象を与えるだけで，害悪であるとさえ思える． よく大学の講義名に「○○」のあとに「理論」をつけて『○○理論』としてしまうものがあるが，それが本当に「○○理論」なのかどうかということを反省する必要がある．日本の大学において『グラフ理論』という名前
初心者でもOK！レベル別・アルゴリズムをすぐに学べる書籍とサイト12選 - paiza times
Photo by Tim Samoff 秋山です。 皆さんはアルゴリズムについてどれくらい知っていますか？というか勉強したことありますか？ 私はもともと情報系だったので学校でも習いましたが、paizaのプログラミングスキルチェック問題を作るときなどはいまだにいろいろ調べることもあります。 アルゴリズムについて勉強したことがない人の中には「ずっと気になってはいるものの、各プログラミング言語の書き方やフレームワークの使い方などを学ぶことに手一杯で、アルゴリズムはつい後回しになっている…」という方も多いと思います。 ただ、アルゴリズムを知らないままプログラミングを続けていると、少し複雑な処理を考えなければならなくなったときなどに、力技のやり方しか考えつかなくて「すごい人だったらもっとスマートな書き方ができるんだろうな……」と悶々としてしまうことがあるはずです。 今回はそんな方に向けて、アルゴリズ
木の直径を求めるアルゴリズム - ペケンペイのブログ
注意：議論が洗練されておらず、真面目に読むべき記事ではありません。信頼できそうなグラフ理論の書籍を読んだほうが良いと思います。ウェブ上で閲覧できる資料としては以下があり、そこの References を辿ると良いでしょう。 http://mathworld.wolfram.com/GraphCenter.html 中心が高々 2 個であることと、2 個あるならばそれらは隣接していることは F. Harary の ''Graph Theory'' に証明があります。p. 35 の Theorem 4.2 Every tree has a center consisting of either one point or two adjacent points. がそれです。頻繁に参照される記事ではありませんので、この記事を改訂する予定は今の所ありませんが、幾らか思うところがあるので希望があれば
クリントン陣営が選挙運動のデータ分析に使っていた「Ada」アルゴリズムが敗北の原因か？
by Kristopher Harris 世論調査では優勢だったヒラリー・クリントン氏がなぜ選挙戦で負けたのか？ということについては、さまざまな分析がなされています。クリントン氏は選挙戦においてデータ分析を重視していたのですが、このとき分析に使われていたのが「Ada（エイダ）」によるアルゴリズム。Adaとは何なのか、なぜ正しい分析を出せなかったのかについて、The Washington Postが考察しています。 Clinton’s data-driven campaign relied heavily on an algorithm named Ada. What didn’t she see? - The Washington Post https://www.washingtonpost.com/news/post-politics/wp/2016/11/09/clintons-da
[アルゴリズム]木の回転が不要な二分探索木 | 株式会社ケイズ・ソフトウェア
二分探索木とはデータ構造の一つです。 平衡を保った二分探索木は、二分探索を最も効率よく行う事ができます。 しかし、どんな場合でも平衡を保つとは限りません。 最悪なのはキー値の出現順序が１、２、３…となっている場合で、 図のように平衡を保てず、リスト構造と同様な探索効率になってしまいます。 常に平衡を保つ為には、木の回転という操作が必要になります。 ただ、この操作にも当然ながら処理時間が必要で、 タイムクリティカルな局面では、こういった処理すらケチりたくなってきます。 （処理時間そのものより、処理を挟む事による処理時間のばらつきが問題になる） もし、キー値を自由に割り振る事が可能なら、ランダム値を割り振る事で 木の回転をしなくても、二分探索木は常に平衡を保つようになります。 しかししかしタイムクリティカルな局面では、乱数計算すらケチりたくなってきます。 乱数計算不要で、二分探索木が平衡を保つ
![[アルゴリズム]木の回転が不要な二分探索木 | 株式会社ケイズ・ソフトウェア](https://cdn-ak-scissors.b.st-hatena.com/image/square/c4c0041fe14fc80e4a29b645e86748ca8526c8d8/height=288;version=1;width=512/https%3A%2F%2Fkeis-software.com%2Fwp-content%2Fuploads%2F2014%2F05%2F1234.gif)
Bit Twiddling Hacks
By Sean Eron Anderson seander@cs.stanford.edu Individually, the code snippets here are in the public domain (unless otherwise noted) — feel free to use them however you please. The aggregate collection and descriptions are © 1997-2005 Sean Eron Anderson. The code and descriptions are distributed in the hope that they will be useful, but WITHOUT ANY WARRANTY and without even the implied warranty of
Googleの旅行アプリで使われている280年前のアルゴリズムとは？
By Celeste RC Googleが2016年9月20日にリリースした「Google Trips」は旅行に関する情報をまとめて管理できるアプリで、目的地までの移動方法や行き方、移動時間、観光地の場所や付近にあるレストランなど、さまざまな情報を元にして旅行の計画表を自動で作ることができます。Googleによれば、このGoogle Tripsに使用しているアルゴリズムは280年前のものを元にしているとのことで、その詳細をGoogleが公式ブログで明かしています。 Research Blog: The 280-Year-Old Algorithm Inside Google Trips https://research.googleblog.com/2016/09/the-280-year-old-algorithm-inside.html Google Trips - Google Pl
凸包の頂点数の話 - notブログ
まとめ のグリッドに収まる格子点を頂点とする凸多角形の頂点数は。 詳しい話は論文を読んでください。 On the maximal number of edges of convex digital polygons included into an m × m-grid はじめに 凸包を取ると考慮すべき点の数が減って嬉しい、という問題が競プロでたまに出題されます。 この類の問題の解説で頂点数のオーダーがと書いてあることがある*1のですが、実際はだよという話です。*2 方針 頂点数を大きくするにはマンハッタン距離が短い辺から使うのが最適です。 マンハッタン距離が以下の辺を使うと、頂点数がの凸多角形がのグリッドに収まります。 計算 めんどうなので、成分が正の部分だけ考えます。*3 そうすると使う辺は(1,1),(1,2),(2,1),(1,3),(2,2),(3,1),...となります。 これ
焼きなまし法の真実 – システム工房コルン
はじめに 焼きなまし法はベター山登りなのか？ 探索空間は本当に高次元なのか？ 採択確率式の正当性 メトロポリス・ヘイスティングス法がうまくいく条件 メトロポリス・ヘイスティングス法と温度 おまけ1 … 遷移先候補をどう提案するか？ おまけ2 … 温度管理について 終わりに 謝辞 はじめに 著者は、TopCoder Marathon Matchesで世界大会決勝へとアメリカに3度招待された。 その3度ともが、予選では強文脈ゲームによる通過であり、焼きなまし法の使えない問題分類だった。 近年、文脈のない探索の出題が増えてきており、焼きなまし法が正解方針であることが多くなっている。 焼きなまし法へと苦手意識を持った著者であったが、出題の傾向がそうであるのなら避けて通れるものでもなく、焼きなまし法の出題であっても単純な殴り合いで1位をもぎ取れるまでになりたいと2年前に決意して、七転八倒を繰り返しな
Interpolation - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ
多項式補間に関して教えてもらったのでまとめておきます。 何らかのN次関数P(x)があったとします。xが小さい場合は簡単に計算できる時、それを利用して大きなxに対しても求めたいです。 連立方程式を解くと各項の係数が求められますが、O(N^3)掛かってしまいます。 それをO(N^2)にする方法の１つとして、ラグランジュ補間があります。 Qi(x) = (x-0)*(x-1)*...*(x-N) / (x-i) という関数を考えると、N次多項式は必ず、 P(x) = c0*Q0(x) + c1*Q1(x) + ... + cN*QN(x) という形で書けるそうです。 この関数Qの嬉しい所は、xにiを代入すると、Qi以外は全部0になって除去できる所です。 xにiを代入して考えると、係数ciはP(i)/Qi(i)となっており、簡単に計算できます。 各Qを求めるためにO(N)で、項がN個なので、O(N
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
cakes（ケイクス）
tmnghryk on Twitter: "最大公約数を求めるのに、ユークリッドの互除法より速いとも言えるのが、ニコマコスの算法を拡張したブレントの算法。ビットシフトを用いる。a,bがともに偶数なら割り続け、回数を記録。一方が偶数なら割り続け、大から小を引く(奇ー奇＝偶がポイント)。これを繰り返して、一致したらGCD。"
ビット演算テクニック Advent Calendar 2016 - Adventar
Michael Garland - QSlim 2.0
SAT ソルバー入門
かど on Twitter: "(再掲)SATソルバを使った問題の解き方はsemiexpさんのhttps://t.co/HCtwwFaDCP …とhttps://t.co/iGJvhXamZd がおすすめです。あとはアルゴリズム自体はhttps://t.co/j6YEWUNCNR …がおすすめです。"
講義資料
東京大学理学部情報科学科のCPU実験
