2017-05-03から1日間の記事一覧

Subsequence Queries | CS Academy #24

コメントつきコード /* 解法 漸化式で解を表して行列を作ってみる。 行列は添字ごとに異なるので累乗では解けない。 [l, r)の積 A[r-1]A[r-2]...A[l] の求め方 (1) セグメント木を使って求める http://yukicoder.me/problems/no/510 の解法 今回の問題ではTL…

Counting Perfect Subsequences | HourRank 20

sに含まれる文字xの数をn(x)とする。c, dが無いものと見做してsがa, bだけから成り立つと考えてみよう。f[i]を文字a, bをちょうどi個ずつ含む部分列の数とする。i>min(n(a), n(b))のときaまたはbの数が足りないからf[i] = 0i<=min(n(a), n(b))のときn(a)個の…

Birjik and Nicole's Tree Game | HourRank 20

復習用コメント付きコード /* 思いつき方 頂点を黒く塗る その黒い頂点を含む部分木は? 根まで行く距離が長過ぎる HL分解する */ /* HL分解 Heavy-Light Decomposition 木の構築 O(|V|+|E|) あらかじめ与えられた木について、頂点u,v間のパスをセグメント木…