問題概要 りんごさんは1秒で1枚クッキーを焼ける りんごさんはA秒かけて今あるクッキーT枚を全て食べることができ、それによって1秒でT枚クッキーを焼けるようになる N枚以上のクッキーを最短何秒で焼けるか リンク 部分点解法 N <= 106なので、O(N)かO(N lo…

問題概要 リンク 木 ノードとノードの単純パスの距離は通ったエッジの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に色を塗るとき…

問題概要 (リンク)http://abc040.contest.atcoder.jp/tasks/abc040_d y_i年に作られた道は都市a_iと都市b_iを結ぶ 住民jはv_jに住んでいてw_j以前に作られた道を通りたくない 全ての住人が移動できる都市の数を求める 解法 UnionFindを使う 少し拡張してUnio…

ABCのBなのに、難しいと感じた人が多かった問題。 1回REでWAを出してしまった。 問題概要 (リンク)http://abc040.contest.atcoder.jp/tasks/abc040_b n枚のタイルを敷き詰めて、長方形を作る。 その時、短辺と長辺の差 + 余ったタイルが最小になるようにする…

問題概要 リンク 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…