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

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

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

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

問題文 : Trailing little cats解法 : a_{ij} = i回目のセットでj番目のネコが持っているピーナッツの数, とすると, a_{ij}は以下の2つのいずれかとなる :・a_{i-1σ(j)} + a_{i-1j} ・a_{i-1j}ここで, f(i)を ベクトルa_{i-1}からベクトルa_iを作る操作とす…

問題文 : Milking Time解法 : dp[N] : 時間Nまでに得られるミルクの最大量, とすると,dp[N] = max(i = 1 ... M, e[i] ≦ N | dp[s[i]] + v[i] where s[i] = i番目の仕事が始まる時間, e[i] = i番目の仕事が終わる時間)となる. ここで, 区間の端以外の時間はい…

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

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

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

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