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

Lilliput Steps

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

JOI Open Contest 2015 - Sterilizing Spray ふたたび

kagamiz.hatenablog.comこの問題、さすがに実装も定数倍も重い解法を書いてしまっていたので、別のアプローチで解き直してみました。

AOJ 2382 - King Slime

問題文 : King Slime解いている人数が少ない問題はなんかドキドキする(小並)

AOJ 1068 - School of Killifish

問題 : めだかの学校

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$ …

IJPC #1 A - Innocent Animals and Destruction of Forests

問題文 : むこのどうぶつたち と しんりんのはかい

AOJ 2207 - Consistet Unit System

問題文 : 無矛盾な単位系

Codeforces 359D - Pair of Numbers

問題文Pair of Numbers概要長さ$n$ の列が与えられる. 次の性質を満たす最長の部分列をすべて求めよ. $a_l,\ a_{l+1},\ \cdots,\ a_r$ を全て割り切る$a_j\ (l \leqq j \leqq r)$ が存在する. $1 \leqq n \leqq 3 \times 10^5,\ 1 \leqq a_i \leqq 10^6$

AOJ 2170 - Marked Ancestor

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

Codeforces 314C - Sereja and Subsequences

問題文 : Sereja and Subsequences概要 :数列${a_n}$ がある. ${a_n}$ の相異なる全ての非減少部分列${b_n}$ について, $b_1b_2\cdots b_n$ を求め, その和をmod $10^9+7$ で求めよ.$n \leqq 10^5$

PKU 3784 - Running Median

問題 : Running Median数が$N$ 個与えられる. 奇数個毎に, それまでの数の中央値を出力せよ.テストケース数$T \leqq 1000$ $N \leqq 9999$ $N$ は奇数

USACO 2012 December Gold - Running Away from the Barn

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

Skew Heap

Skew Heap は, meld (2 つのpriority queue をmerge する操作) ができるheapです. meld ができると, push は, 新しい要素をヒープとして親とmeld, pop は 親の子をmeldで実装できてしまいます. 計算量はならしO(log N) で便利です. (くわしくはhos さんのブ…

KOJ 0042 - Big Range Query

KOJ に載せている, (去年のAdvent Calendar に掲載していた)Big Range Query の問題文および解説です.

JOI 春合宿 2012-day2 Rotate

問題文 : 回転解法 :リストを使う. 右と下にいけるリストがあれば, 90 * n (0 ≦ n ローカルでは最大ケースに2.6sec かかり, AtCoder でも10 点分しか点数が得れないので, O(QN^2) 書いたのと同じ扱いで涙しかない...

JOI 春合宿 2013-day2 Construction

問題文 : 建設事業解法 : つなぐ辺は隣り合うものだけ(Modern Manshion), 長方形の交差判定は上から操作(Fortune Telling), 空港のコストの方が辺より良いときはそれを使う, というJOI 問題のテクニックを総動員する問題です.点のソートをするときに, x 座標…

Josephus Permutation

問題文 : Josephus Permutation解法 :アルゴリズムイントロダクションに乗っていた問題を実際にコードに起こしたもの. ヨセフスの芋の軌跡をたどったものを出力する問題. 愚直にm % n 個先までたどる線形リストなどではO(n^2) となり. TLE するだろう. そこ…

IOI 2005-day1 Mountains

問題文 : 山の遊園地問題概要 (問題文読みづらいので) : 長さ N の数列が与えられる. 次のクエリに答えよ. 区間 [l, r] の値を v に更新する. [I l r v] [1, x] の値がはじめてv を越えるようなx を求める. [Q v] 解法 :遅延評価をするセグメント木を用いる.…

JOI 本選 2013-5 Bubble Sort

問題文 : バブルソート解法 :与えられた配列Aを, (添字, 値) を座標として座標平面にプロットする. すると, この問題は長方形の中にできるだけ多くの数を含むようにするにはどうすれば良いかを考える問題となる.愚直に数え上げを行えばこれはO(N^2) 時間で最…

IOI 2008-day1 Type Printer

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

Codeforces 121E - Lucky Array

問題文 : Lucky Array解法 : いつぞや誰かから「"Lucky Array"はセグメント木で解けるよ」 と聞いて, 問題を見つけたので挑戦したらそのLucky Array は別の問題だったらしい. セグメント木じゃ解けなさそうなんだよなあと思いつつ, 解法をみて勉強しようとし…

Codeforces 226E - More Queries to Array...

問題文 : More Queries to Array問題概要: 配列 $ \normalsize a$ が与えられるので, 区間 $ \normalsize [l,\ r] $ の値を $ \normalsize x$ に変更する. $ \normalsize \displaystyle \sum_{i = l}^{r} a_{i} \cdot (i - l + 1)^k$ (ただし $\normalsize 0…

JOI春合宿 2011-day4 apples

問題文 : リンゴの出荷解法 : 濃さD のリンゴを, 区間[D, D + B + 1)に対応させて,・ある区間に値x を足す ・ある区間の和を求めることが出来れば, 出荷依頼に高速に答えることができる. これは, Starry Sky 木を改造することで実現することが可能である.た…

JOI春合宿 2012-day1 fish

問題文 : 魚解法 : 初めに, 尺取り法で, 起こりうる魚の組み合わせ(赤a 匹, 緑b 匹, 青c 匹 以下の組み合わせなら全て作成可能である) というものを列挙する. これをa * b * c の直方体として扱う. その後に, セグメント木で体積を, 以下の要領で求めていく.…

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 2823 - Sliding Window

問題文 : Sliding Window解法 :見た感じセグメント木でもよさそうだが, 蟻本でdequeを使うO(N) 解法が紹介されていたので, dequeの練習がてら書いてみた. dequeステキ, 便利. やはり書くと分かりやすい.dqでは, i dq2では, i a[j] となるようにdequeにデータ…

AOJ 1505 - Dungeon

問題文 : Dungeon (I)解法 : クエリでの求める距離fs_iと, スタートからの最短路についてソートし, BITで数え上げを行うと O(N log N)時間でこの問題を解くことが出来る. クエリや最短路は, 数に対し範囲が大きいので座標圧縮を行うと管理が楽になると考えら…

SPOJ 2211 - Mars Map

問題文 : Mars Map解法 : 座標において長方形が重なっている領域の面積を求める問題. 平面走査を行った.具体的には, ある長方形について, (x1, y1, y2)の間その領域を存在することにして, (x2, y1, y2)をその領域を消すタイミングとする.これをO(logN)で実現…

JOI春合宿 2009-day4 Starry Sky

問題文 : 星空解法 : N個ある各星のLについて, そのLで囲める星の最大値を求める.ここで, 走査をする際に, x軸のみを走査し, y軸はセグメント木で, "ある点に於いて観測できる星の最大値"を管理すると, x軸の走査がO(N), その過程でのセグメント木の走査がO(…

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…

Introduction to Segment Tree

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

Codeforces 52C : Circular RMQ

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

PKU 3378 - Crazy Thairs

問題文 : 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)時間でこの問題を解くことができます.あ…

JOI春合宿 2008-day4 typhoon

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

JOI春合宿 2010-day2 DNA synthesizer

問題文 : 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(合成したい…

JOI春合宿 2012-day3 fortune telling

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

PKU 1990 - MooFest

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

JOI春合宿 2010-day3 Hide-and-seek

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

PCK-2012 問9 - スコーン配達計画

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

Codeforces #79 Div.1 B - Buses

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

AOJ 0553 - Dungeon

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

JOI春合宿 2012-day4 Bookshelf

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

AOJ 2431 - House Moving

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

PKU 3171 - Cleaning Shifts

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

ARC #008 D - タコヤキオイシクナール

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

PKU 3368 - Frequent values

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