問題ページ E - Antennas on Tree 考えたこと 次数が大きい頂点にアンテナを置いても同じ距離の頂点が大量にできるだけなので次数が小さい頂点に置いた方がよさそう 次数が大きいウニみたいなグラフがあったときどうするか考える ウニの中央の頂点に置くのは…

問題ページ D - Forest 考えたこと グラフのつながれている形によってある頂点が使えなくなるといったことはないので形は関係なさそう 各連結成分についてa[i]の集合として考えられそう vectorをマージしていく感じに思えたのでマージテクを調べ始める 小さ…

問題ページ C - Vacant Seat 考えたこと 頂点数が奇数で円環状になっているグラフが2部グラフなわけはないので空席があるのはそれはそう クエリ回数が20回なのでlogオーダーの計算量しかありえなさそう 空席が絶対にある範囲をもって二分探索っぽいことをす…

問題ページ B - Two Arrays 考えたこと 考えるのはa[i]とb[i]の差だけでよい a[i] < b[i] だとすれば a[i]+2, b[i]+1とすれば差が1縮まるので周りの状況にかかわらず絶対に等しく出来る a[i] > b[i] のときは a[j]+2, b[i]+1 (a[j] < b[j]) とする必要がある…