問題概要 リンク 木 ノードとノードの単純パスの距離は通ったエッジのXOR和 XOR和がXになるのは何通りか 解法 あるノードを根とした時、aとbの単純パスはa-LCA(a,b)-bである。 ※LCAはLowest Common Ancestor すなわちその距離L(a,b)は、 L(a,b) = L(a,LCA(a,…

問題概要 (リンク)http://arc048.contest.atcoder.jp/tasks/arc048_c 高橋君はN本の足がある N本の足はLi本のパーツに分かれている Li本の足に0か1を書き込む 任意の2本の足A,Bを選んだ時、Aのつま先-胴体-Bのつま先と辿った時、0、1は回文となっていなけれ…

頂点が有向グラフである意味がない… 問題概要 (リンク)http://arc049.contest.atcoder.jp/tasks/arc049_c N頂点の有向グラフがある 頂点に色を塗る その際以下の制約つける 頂点xに色をぬるとき、頂点yに色が塗られていなければならない 頂点uに色を塗るとき…

問題概要 リンク 文字列Sに対して S=A+B+C+A+C となるような部分文字列A, B, Cがいくつ考えうる数え上げる。 解法 部分点 AとCの文字数を決める O(N2) 条件を満たすかはローリングハッシュでO(1) 満点 SをABCとACに分ける境目を探索する その際、Z algorithm…