ひらめの日常

日常のメモをつらつらと

codeforces

Codeforces Round #582 (Div. 3) G. Path Queries

問題はこちら codeforces.com 頂点数 の木が与えられる(木なので辺の数は )。 以下のような 個のクエリ が投げられるので、それぞれに対する答えを出力せよ。 求めるものは以下を満たす頂点 , , のペアの個数。 頂点 と を結ぶパスの中で、辺の最大の重み…

Codeforces Round #582 (Div. 3) D. Equalizing by Division

問題はこちら codeforces.com 長さ の 配列 が与えられる。一回の操作によって任意の要素一つ、 を2で割って切り捨てることを行う。 (つまり、 ) 個の等しい要素を 中で得るには、何回操作を行えばいいか、その最小値を求めよ。 考え方 全ての を、0になる…

Educational Codeforces Round 63 D. Beautiful Array

Beautiful Array 問題はこちら codeforces.com 自分が気づいたところ まず最初に,xが負の時は最小区間和を選んできてそれをx倍する.xが正の時は最大区間和を選んできてそれをx倍する.とすれば最大値が求まると考えた.ここでセグ木とかをググり始める... …

Codeforces Round #552 (Div. 3) E. Two Teams

Two Teams 問題はこちら codeforces.com 自分が気づいたところ 愚直解は,毎回使っていない最大値を検索→幅 を探索し,使っていないものをk個チームに属させるというもの. 計算量としては, なのでそのまま実装すると になるので間に合わない. そこで,一…

Codeforces Round #551 (Div.2) C Serval and Parenthesis Sequence

Serval and Parenthesis Sequence 問題はこちら 問題文難しくないですか... codeforces.com 自分が気づいたところ 括弧を扱う問題では,stackを用いると綺麗に書けるなと思い実装.しかしコンテスト時間内に問題文を解読できなかった... 解説を読んで このブ…