問題概要 リンク 略 解法 ある車xに着目する時、あるエッジの両端u,vについて、min(u,v) >= xの時、その道にまだ車が止まっていないため通行可能である 通行可能な道をUnion Findでマージし、same(S, x)がtrueとなれば到達可能である この制約はxが大きくな…

問題概要 リンク 木 ノードとノードの単純パスの距離は通ったエッジの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は回文となっていなけれ…

問題概要 リンク 1 ~ Nまでの数字が書かれたせんべいがランダムな順番で与えられる シカは1枚目から順にせんべいを食べるか、食べないか選ぶ シカは全部でK枚のせんべいを食べられる シカはn枚目のせんべいを見ている時, 1 ~ n枚目のせんべいの大小関係がわ…

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