子から異なる2つを選ぶ感じの木DPを解くアレ - よすぽの日記
子から異なる2つを選ぶ感じの木DPを解くアレを解くテクニックを紹介します。 D: Longest Path - Indeedなう（オープンコンテスト） | AtCoder とかが簡単に解けたりします 頂点0を根とする根付き木について 頂点iはa[i]を持つ(a[i] >= 0) 頂点iそれぞれについて、b[i] = a[i] + max(0, max(b[x] ただしxはiの子), max(b[x] + b[y] ただしx, yはどちらもiの子でかつx != y)) b[0]を求めよ という問題を考えます つまり、b[i]は子供から0, 1, 2個選んだ時のb[選んだ頂点]のsumのmaxにa[i]を足したものですね vector<int> g[MAX_V]; //g[p]は頂点pの子供を入れたvectorとする int a[MAX_V], b[MAX_V]; void dfs(int p
競技プログラミングにおける全方位木DP問題まとめ - はまやんはまやんはまやん
全方位木DP よく分かる解説 問題 CSA Connected Tree Subgraphs [解説 CF397 Tree Folding CF405 Bear and Tree Jumps AtCoder Driving on a Tree CSA Root Change EDPC Subtree 解説 CF Centroids 解説1 解説2 解説3 CF395 Timofey and a flat tree CF302 Road Improvement 解説 yukicoder No.768 Tapris and Noel play the game on Treeone 解説 違うけど方針が似ている問題 CF Nearest Leaf
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(
木の直径を求めるアルゴリズム - ペケンペイのブログ
注意：議論が洗練されておらず、真面目に読むべき記事ではありません。信頼できそうなグラフ理論の書籍を読んだほうが良いと思います。ウェブ上で閲覧できる資料としては以下があり、そこの 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. がそれです。頻繁に参照される記事ではありませんので、この記事を改訂する予定は今の所ありませんが、幾らか思うところがあるので希望があれば
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
Engadget | Technology News & Reviews
Grok claimed the Charlie Kirk assassination video was a 'meme edit'In several bizarre exchanges, Grok repeatedly claimed that Charlie Kirk was "fine" and that gruesome videos of his assassination was a "meme edit." Senators demand ICE cease use of facial recognition appA handful of United States Senators have written a letter to the acting ICE Director regarding agency use of a facial recognition
蟻本シリーズ 3 スライド最小値 - StatModeling Memorandum
今回は以下の問題を考えます。 長さNの数列x[1], x[2], ..., x[N]と数Kが与えられます。y[i] = min{x[i], x[i+1], ..., x[i+K-1]} (i = 1, ..., N-K+1)として定義される数列y[i]を計算しなさい。 この問題は両端キュー（デック, deque）を用いることで、なんとのオーダーで解けます。詳しくは蟻本の4-4節（p.300）を読んでください。 プログラミングコンテストチャレンジブック [第2版] ～問題解決のアルゴリズム活用力とコーディングテクニックを鍛える～ 作者:秋葉拓哉,岩田陽一,北川宜稔発売日: 2012/01/28メディア: 単行本（ソフトカバー） ここでは蟻本から例題を引用してN = 5, K = 3, x = {1, 3, 5, 4, 2}, y = {1, 3, 2}の場合について簡単に説明します。 まずd
蟻本シリーズ 2 ランダムウォーク - StatModeling Memorandum
今回は以下のランダムウォークの問題を考えます。 I×Jの大きさのグリッドがあります。(1,1)からスタートして、1ターンに上下左右4マスのうち移動できる方向にそれぞれ確率p1,p2,p3,p4で移動します。いくつかのマスには石が置いてあり、通行不可能になっています。(I,J)にはじめて辿り着くまでにかかるターン数の期待値を求めなさい。ただし、(1,1)から(I,J)に移動するパスが少なくとも1つは存在すると仮定します。 例：I = 3, J = 10 [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10] [1,] 1 0 1 1 1 0 1 1 1 0 [2,] 1 0 1 0 1 0 1 0 1 0 [3,] 1 1 1 0 1 1 1 0 1 1 0が石があるマスで、1が移動できるマスです。以降ではこのグリッドを「グリッドA」と呼びます。
JPEG画像をロスレスで22％も圧縮できるオープンソースソフト「Lepton」をDropboxがリリース
大量に保存しがちな画像データは、なるべくなら保存するファイルサイズを小さくしておきたいところです。クラウドサービスDropboxが、JPEG画像データを無劣化で平均22％も圧縮できる無料ソフト「Lepton」をリリースしました。Leptonなら「JPEG画像のファイルサイズを小さくしておいて、実際に使うときだけ素早く解凍する」という使い方が可能です。 Lepton image compression: saving 22% losslessly from images at 15MB/s | Dropbox Tech Blog https://blogs.dropbox.com/tech/2016/07/lepton-image-compression-saving-22-losslessly-from-images-at-15mbs/ クラウドストレージサービスを提供するDropboxは
リリース、障害情報などのサービスのお知らせ
最新の人気エントリーの配信
j次のブックマーク
k前のブックマーク
lあとで読む
eコメント一覧を開く
oページを開く
ダイクストラ法典型問題集
tmnghryk on Twitter: "最大公約数を求めるのに、ユークリッドの互除法より速いとも言えるのが、ニコマコスの算法を拡張したブレントの算法。ビットシフトを用いる。a,bがともに偶数なら割り続け、回数を記録。一方が偶数なら割り続け、大から小を引く(奇ー奇＝偶がポイント)。これを繰り返して、一致したらGCD。"
Michael Garland - QSlim 2.0
SAT ソルバー入門
かど on Twitter: "(再掲)SATソルバを使った問題の解き方はsemiexpさんのhttps://t.co/HCtwwFaDCP …とhttps://t.co/iGJvhXamZd がおすすめです。あとはアルゴリズム自体はhttps://t.co/j6YEWUNCNR …がおすすめです。"
講義資料
東京大学理学部情報科学科のCPU実験
