Lilliput Steps

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

深さ優先探索

Codeforces 472D - Design Tutorial: Inverse the Problem

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

AOJ 2170 - Marked Ancestor (ふたたび)

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

AOJ 0132 - Jigsaw Puzzle

問題文 : ジグソーパズル

AOJ 2170 - Marked Ancestor

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

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$ (辺数)

橋と関節点, lowlink

lowlink という概念について説明しています. 実装は簡単ですが, いろいろと応用が効いて面白いです.

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$

AOJ 0236 - Alien Messages

問題文 : 宇宙人のきまぐれメッセージ解法 : 6 つの接続可能性をすべてのマスについて試すO(6^(W*H)) 通りの探索と, それが終わったあとに接続関係が適切であるかをWF で確かめるO((W*H)^3)を掛け合わせてO(6^(W*H)*(W*H)^3) という絶望的な最悪計算量だが,…

AOJ 0091 - Blur

問題文 : Blur解法 : 基本的に枝刈り探索である. ・矛盾する状態(そこにインクを落とすと明らかに歪なインクの塊が残ってしまう)になったら探索をやめる ・インクの数を確定することが出来たら無闇にインクを落とすのをやめる ・探索に失敗したインクの集合…

JOI 春合宿 2008-day1 Sheet

問題文 : 色紙解法 :各矩形のとりうる領域の最大値を計算し, その上にある別の色紙から自分に向かった辺をはったグラフを考える. このトポロジカル順序が答えとなる. 計算量は, 矩形の操作にO(NWH) 時間, トポロジカルソートにO(N) 時間で, 全体としてO(NWH)…

JOI 春合宿 2012-day3 Sokoban

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

Croatia OI 2007 - policija

問題文 : POLICIJA問題概要 :無向連結グラフが与えられる. 以下のようなクエリに答えよ. 頂点 $u, v$ と辺 $e$ に対し, $e$ を取り除いたとき $u$ から $v$ へ辿り着けるか? 頂点 $u,\ v,\ w$ に対し, $w$ を取り除いたとき $u$ から $v$ へ辿り着けるか? …

IOI 2008-day1 Type Printer

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

AOJ 0519 - Worst Sportswriter

問題文 : 最悪の記者解法 : トポロジカルソートをすればよい. トポロジカル順序が複数あるかどうかは, 隣り合う2 つの順位について, 互いへ直接たどり着けるかどうかを判定すれば良い. (隣り合う順位へ直接辿りつけないのであれば, その2 つを仲介する順位が…

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) くらいの計算量となる. 何も見ないで書け…

JOI春合宿 2011-day4 orienteering

問題文 : オリエンテーリング解法 : 同じ高さの点が無いので, 前もって標高順で, チェックポイントについてトポロジカルソートを行う. その後は全点対の最短経路をO(N^2logN)程度で求め, dp[i][j] : 1人目がチェックポイントi, 2人目がチェックポイントj に…

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…

JOI春合宿 2010-day2 Regions

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

AOJ 0235 - Sergeant Rian

問題文 : サージェント・ライアン解法 : 最後に訪れる島を根とした木を作ると, 爆破する橋が必然的に決まる. ゆえに, 全ての島について最後の島としたときの爆破する時間を考え, その最小値を答えとする.コード : #include <cstdio> #include <cstring> #include <vector> #define INF</vector></cstring></cstdio>…

JOI春合宿 2012-day1 JOI Flag

問題文 : 日本情報オリンピック旗解法 : 旗を4つに分解し, それぞれに何を割り振るのかが最適なのかを深さ優先探索で決めていく. ここで, 旗の大きさに対して最初から書かれている文字の個数が少ないので, 見ている範囲に文字が無い or 旗のレベルが0のとき…

AOJ 0214 - Autumnal Illumination

問題文 : 秋のイルミネーション解説 : 各四角形の交差判定ができれば, 各四角形を頂点とみて, 連結成分の個数を数える問題となる.連結成分の個数を求める方法は, union-find木を使う方法などもあるが, ここでは深さ優先探索で同等な事をしている.ここで, 四…

AOJ 0247 - Ice Maze

問題文 : AOJ 0247解法 : 基本的には深さ優先探索を行う. ただし, それだけでは時間制限に間に合わないので, 反復深化深さ優先探索(IDDFS)を行う. 具体的には, 下界uを決めて, uよりコストがかかることがわかればuを増やすという事を行う. 下界から決めてい…