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

問題文 : 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…

こんにちは, kagamiz(@kagamiz) です! この記事は, Competitive Programming Advent Calendar Div2012 18日目の記事として書かれました. この記事では, ぼくが気に入っているデータ構造であるセグメント木について, 説明と問題演習・問題紹介を交えながら紹…

問題文 : Circular RMQ解法 : Starry Sky木をそのまま実装すれば良い問題です. ちなみに, Starry Sky木とは, ・区間[a, b]に値を加算する. ・区間[a, b]の(最大・最小)値を求める の操作が同時に出来るようなデータ構造を指します.この問題特有の「Circular…

問題文 : Crazy Thairs解法 : dp[i][j] = j番目を終点とする長さi + 1のLISの総数, とするとすべてのjについてdp[0][j] = 1,dp[i + 1][j] = Σ[k = 1...j - 1 | a[k] となります. Σの部分の計算をBITを使うと, O(nlogn)時間でこの問題を解くことができます.あ…

問題文 : 台風(pdf注意, 2ページ目~3ページ目)解法 : 昔解いた気もするのですが, そのときはセグメント木を使っていました.基本的には昔と方針はいっしょなのですが, 今回はReactive型の問題として出題されたときに対応できるよう, オンライン風に書いてみま…

問題文 : DNAの合成解法 : dp[M] = M番目の文字までを構成するのに必要なDNA素数の最小値, とすると, M + 1 ~ M + kまでの部分文字列s_kがあるとするとdp[M + i] (1 ≦ i ≦ k) = min(dp[M + i], dp[M] + 1) となる. DNA素を全て確かめるとO(strlen(合成したい…

問題文 : 占い解法 : あるカードを奇数回ひっくり返せばそのカードは裏で, 偶数回ひっくり返せばそのカードは表である.これは, カードをひっくり返す順序によらないので, y1 ≦ y ≦ y2 行 x1 ≦ x ≦ x2列のカード をひっくり返す, という命令を x1 ≦ x ≦ x2と…

問題文 : MooFest解法 : 2匹の牛について、離れている距離*Max(牛iの聴力, 牛jの聴力)が必要な声のレベルなので、 (全ての声の大きさの総和) = 最も聴力が必要な牛 * 離れている距離の総和 + 次に聴力が必要な牛 * 離れている距離の総和 + ... となる.ゆえに…

問題文 : かくれんぼ解法 : 障害物の左上の座標についてそれらを昇順ソートし, 各x座標について障害物の重なりの大きさを持つ. そして、実際に障害物をフィールドに挿入していく. その過程で武器を防げるだけの大きさになれば、その座標を出力する.ここで、…

問題文 : スコーン配達計画(pdf注意, 28枚目-30枚目)解法 : 部分列 mod Mの最大値を求める問題である. 区間[i, j]の和 mod Mをすべて確かめると, 累積和を用いてもO(N^2)となってしまうため、セグメント木を使ってこの計算を高速化する. i jについてはループ…

問題文 : Buses解法 : 各バスの出発する地点をs[i], 到着する地点をt[i]とすると バスをt[i]について昇順にソートし、その順に番号をつけます.i番目のバスで乗れる地点は, s[i] ≦ x このjたちは明らかに連続しているので、これらの範囲を満たすjたちを二分探…

問題文 : ダンジョン解法 : 各階で回復出来る量を記録しながら, 実際にダンジョンを潜っていく. 体力が負になってしまった場合, 最も回復出来る地点で回復する.体力をセグメント木として持っておき, 区間に加算するクエリと区間の最大値を求めるクエリを実装…

問題文 : 本棚解法 : にかいどうさんの言うとおり, 昨日解いた「House Moving」と同じ問題でした.(重さがそれぞれ違いますが, あまり関係ない) ということで, 解説は昨日のもの参照です. BITでも解けるみたいなので, あとでBITで実装してみます.コード : #in…

問題文 : 引越し解法 : 荷物を動かすために使う体力を最小化する、ということは 動かさない荷物の重量を最大化する、ということと等しい. ゆえに, 増加する部分列のうち, 重さが最大のものを総重量から引いたものが答えとなる.荷物の重さをkとし, dp[k] -> …

問題文 : Cleaning Shifts解法 : dp[Ei] -> Ei秒まで掃除するのに必要な時間, とし, 牛iが時間Si秒からEi秒まで掃除でき, 雇うのに給料がMiかかるとすると dp[Ei] = min(dp[Ei], min(dp[Si] ~ dp[Ei]) + Mi) となる. dpテーブルはINFなどで初期化しておく. …

問題文 : タコヤキオイシクナール解法 : Nに対してMが小さいので, Nの座標圧縮を前もって行なっておく. (こうしても正しい結果が得られることは, 美味しさrのたこ焼きが(1, 0)と書かれたタコヤキオイシクナールを通っても美味しさrが保たれることから分かる.…

問題文 : Frequent values解法 : 各ノードは昇順になっているため、各数字の出現頻度をノードとして持つセグメント木を構築する. 各クエリについて, a[s] = a[t]であればt - s + 1を, そうでなければa[s]とa[t]を適切なだけ削り, RMQの処理を行う.コード : #…