読者です 読者をやめる 読者になる 読者になる

Lilliput Steps

小さな一歩から着実に. 数学やプログラミングのことを書きます.

Codeforces 472D - Design Tutorial: Inverse the Problem

問題文 Design Tutorial: Inverse the Problem 概要 $n$ 頂点の有向グラフの隣接行列 $A$ が与えられる. この行列が各辺に重みがついた無向グラフであり, 木を表していれば YES を, そうでなければ NO を出力せよ. 制約 $n \leqq 2000$

HackerRank 101 Hack February - Coloring Tree

問題 : Coloring Tree概要 : $n$ 頂点からなる根付き木のそれぞれのノードに色がついている. 頂点$v$ を根とする部分木にある, 異なる色の個数を数えるクエリに$m $ 個答えよ.$1 \leqq n \leqq 10^5$ $0 \leqq m \leqq 10^5$ $1 \leqq v \leqq n$ $1 \leqq$ …

AOJ 2170 - Marked Ancestor (ふたたび)

問題 : Marked Ancestor問題概要 : 大きさ$N$ の木が与えられる. 最初頂点$0$ は赤色で, その他の頂点は青色である. 次の$Q$ 個のクエリに答えよ :・頂点$v$ の色を赤色に変える. ・頂点$v$ から赤色の先祖ノードのうち, もっとも近いものの番号をこたえる.$…

AOJ 2170 - Marked Ancestor

問題 : Marked Ancestor問題概要 : 大きさ$N$ の木が与えられる. 最初頂点$0$ は赤色で, その他の頂点は青色である. 次の$Q$ 個のクエリに答えよ :・頂点$v$ の色を赤色に変える. ・頂点$v$ から赤色の先祖ノードのうち, もっとも近いものの番号をこたえる.$…

Codeforces 342E - Xenia and Tree

問題文 : Xenia and Tree概要 : 大きさ$n$ の木が与えられる. 最初頂点0 は赤色で, その他の頂点は青色である. 次の$m$ 個のクエリに答えよ :・頂点$v$ の色を赤色に変える. ・頂点$v$ から赤色のノードまでの最短距離を求める.$1 \leqq n,\ m \leqq 10^5$

Japan Alumni Group Spring Contest 2013 E - Minimum Spanning Tree

問題文 : Minimum Spanning Tree概要 : 無向重み付きグラフ$G(V, E)$ が与えられる. すべての$e \in E$ について, $G - e$ の最小全域木の重さを求めよ.$1 \leqq n \leqq 10^5$ (頂点数) $1 \leqq m \leqq 2 \times 10^5$ (辺数)

Codeforces 283C - World Eater Brothers

問題文 : World Eater Brothers問題概要 :$N$ 頂点からなる有向全域木$G$ が与えられる. 高々2 つの頂点を選んで, この頂点から他の頂点への有向パスが存在するようにするために変えなければならない辺の向きの最小値を求めよ.$N \leqq 3000$

Codeforces 338B - Book of Evil

問題文 : Book of Evil 問題概要 : 大きさ$N$ の木で, $M $個の印をつけた頂点すべてからの距離が$d$ 以内であるものの個数を求めよ.$N , M \leqq 10^5$

USACO 2012 December Gold - Running Away from the Barn

問題文 : Running Away from the Barn問題概要 : 大きさ$N$ の木が与えられる. 距離が$L$ 以内の自分の子孫に当たるノードの個数を, すべてのノードについて求めよ. $N \leqq 200000$

JOI 春合宿 2012-day3 Sokoban

問題文 : 倉庫番解法 : 「倉庫番の逆」を考える. すなわち, 目標地点から箱を引っ張りまわすBFS を考える. 箱の置き方がO(MN) 個, 隣接する頂点がたかだか4 個であるため, 状態数はO(MN) である.各状態に遷移したら, 答えには連結成分の大きさを足してやれば…

IOI 2008-day1 Type Printer

問題文 : 活字印刷機解法 : Trie 木上の探索を行う. 最も長い文字を最後にたどれば, その文字の文の型を回収しなくていいため最短ですべての文字を打ち終えることが出来る. (他の文字はどのみち回収しないといけないため). コード : #include <cstdio> #include <cstdlib> #in</cstdlib></cstdio>…

JOI春合宿 2007-day2 SALT TREE XV

問題文 : SALT TREE XV解法 : (qnighy さんのものをチラッと見てしまったので, 考えながら書いた所をまとめる.)まず, ある状態から, 辺の数が0 で頂点の数が0 に出来れば自分の勝利であることを確認する. また, 辺の数が0 の状態への遷移は, 頂点が1 個の時…

JOI春合宿 2011-day3 report

問題文 : 報告解法 :まず, 問題文の例を解析する. 報告先でサイクルになっている頂点達について, サイクル内の頂点v に仕事の報告が来れば, 必ず他の頂点でも仕事の報告が来ることがわかるので, 閉路を潰す.次に, 閉路を潰して出来たグラフの逆辺からなるグ…

APIO 2012-1 - Dispatching

問題文 : 忍者の派遣解法 : 各頂点でpriority queueを持ち, dfs を行い, 給料のコストが大きい頂点から予算を超える分だけqueueから取り除く.これだけではO(N * NlogN) = O(N^2 log N) の計算量となってしまうが, 頂点を併合する際に, 短い方のqueueを併合す…

SPOJ 913 - Query on a tree II

問題文 : Query on a tree II解法 :複数テストケースなので初期化する位置に気をつけないと死んでしまう問題 (ぼく死んでしまいました).距離を求めるところはeuler-tourっぽくやるのも, doubling でやるのもよしです. k 番目の頂点は, 根からの深さとlca(u, …

PKU 1986 - Distance Queries

問題文 : Distance Queries解法 : Highwayの, 渋滞情報変更が無いだけのSimple LCAの問題.(その前に最小全域木化しなければならないが) Euler-Tour をしたが, これはDoubling でも普通に解けそう.全体でO((N+K)logN) くらいの計算量となる. 何も見ないで書け…

Left-Leaning 赤黒木

平衡2分探索木, いつか実装したいなあと思っていたので書いてみた. 疲れた.手元のアルゴリズムイントロダクションとか、ネットの資料を色々漁って書いた. やべえ.2-3-4木という木を2分探索木で表現すると赤黒木になるらしい. ただ、普通の赤黒木だと実装が結…

AOJ 2269 - Traveling Salesman Problem

問題 : 巡回セールスマン問題解法 : 与えられたグラフは,(validなものであれば) 問題の制約通り, 有向木に辺をいくつか(最大501本)足したものとなる. また, 枝分かれや併合・子がある(となる)頂点が, 述べ 1000 個程度より多くあると, validなグラフが構成で…

JOI春合宿 2008-day1 committee

問題文 : 委員会(pdf注意, 1-2ページ目)解法 : 各頂点ごとに, やる気の最大値をメモする. 答えは, やる気の最大値が最も大きい頂点となる. ある頂点のやる気の最大値は, 自分自身のやる気+自分の子までのやる気の最大値のうち, 負で無いものの和, として求…

JOI春合宿 2010-day4 highway

問題文 : 高速道路解法 : 次のように, 2つの木を考える. 辺の更新のクエリが来た時は, euler-tourを行った時に、それぞれの辺が上りだったか、下りだったかを覚えておき処理する.頂点uからvへ行くクエリが来た際は, u->lca(u, v)に行くときは逆辺の木, lca(u…

PKU 2763 : Housewife Wind

問題文 : Housewife Wind解法 : 頂点u, vの最小共通祖先をpとすると, cost(u, v) = cost(u, p) + cost(v, p) = cost(root, u) + cost(root, v) - 2 * cost(root, p)となる. rootからある頂点への距離は, 通った辺を相殺する形で, BITで管理することでO(log N…

Codeforces #143 Div.2 E - Cactus

問題文 : Cactus解法 : 答えは2^(パスs -> tまでの中にあるサイクルの数)になる(図を描いて考察すると分かる.) よって、サイクルを検出して、それを1つの頂点に圧縮する.頂点に圧縮する際に、根付き木にグラフを再構築すると, sとtのLCAをpとしておき s->pの…

JOI春合宿 2010-day2 Regions

問題文 : 地域解法 : C(x) : 距離x以下でM個の地域に分割できるか、とすると C(x)が成立すればC(x - 1)も成立するので、xについて二分探索を行う. 実際に距離xを超えるかは, 与えられたグラフを根付き木にし, 2つの辺によって結ばれる地域のコストの和を距離…