けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

LCA

AOJ 2894 01 文字列と窓 (AUPC 2018 day3 F)

丁寧に考えれば解ける感じ 問題へのリンク 問題概要 0 と 1 のみかならなる長さ N のビット列 S, T が与えられる。S に以下の操作を好きな回数だけ行って T にするのに必要な最小回数を求めよ。 (というクエリが Q 回投げられる) S の最も右にある 1 を含む…

AtCoder ARC 039 D - 旅行会社高橋君

二重辺連結成分分解ライブラリを整えた。 問題へのリンク 問題概要 N 頂点, M 辺の無向単純グラフにおいて、以下の Q 個のクエリに答えよ。 A B C: A から出発して B に行くウォークと、B から出発して C に行くウォークの組のうち、辺を共有しないものがあ…

NJPC 2017 H - 白黒ツリー

オイラーツアー練習第二弾。 そして、これにて一応、ツリーの辺に重みがある場合にも対応できることとなった。 問題へのリンク 問題概要 頂点 1 を根とした頂点数 N の根付き木が与えられる。初期状態では各頂点に 0 か 1 の値が割り当てられている。以下の …

天下一 2015 本戦 F - 根付き木のみさわさん

オイラーツアーの練習に解いたけど、発想も面白いん!!! 問題へのリンク 問題概要 頂点 1 を根とする、頂点数 N の根付き木がある。以下の Q 個のクエリに答えよ: M 個の頂点 v1, v2, ..., vM に実をつける。「その頂点を根とする部分木に含まれる実の個数…