問題 N頂点N-1辺からなる木が与えられる。 頂点には1からNまで番号がつけられている。整数1 Sを番号がL以上R以下の頂点からなる集合とする 頂点集合Sと両端がSに属する辺からなる部分グラフにおける連結成分の個数をf(L, R)とする このとき、Σ_{L=1}^N Σ_{R=…

問題 N人の社員をいくつかの部門に分ける。 社員iと社員jの間には、信頼度w_ijがあり、部門に分けたときのスコアを「(部門の数)*K - 異なる部門に属する2人の間の信頼度の合計」とする。スコアが最大になるように部門分けをした場合のスコアを返せ。 制約 1 …

問題 現在、各飛行機が(X_i, Y_i)を飛行しており、x,y座標を正か負の方向に進んでいる。 すべての飛行機は秒速0.1で進んでおり、同時刻に同じ座標に来てしまうと衝突してしまう。飛行機の中で、一番早く衝突してしまう飛行機が衝突までの何秒かを求めよ。 衝…

問題 グリッド上に、N個の都市があり、i番目の都市は、(X_i, Y_i)に位置する。また、都市の人工はP_iで与えられる。今、x=0とy=0に鉄道が走っており、x軸またはy軸に平行なK本の鉄道を追加で建設できる。 各都市の人々は、一番近い鉄道まで、グリッドに沿っ…

問題 N日間の株価の1株あたりの金額A_i円がわかっている。 最初、1000円の所持金から、毎日株の売買(所持金や持っている株数までで)が可能な時、最終日の所持金を最大化せよ。 制約 2 100 解法1 No.664 超能力者Aと株価予測 - yukicoder を思い出した。。。…