現時点で正しいと思う理解の仕方を書いたので、間違いや気になるところがあればぜひ教えてください。 問題 C: Shorten Diameter - AtCoder Grand Contest 001 | AtCoder 頂点の木がある。この木の直径を 以下にするために削除する必要のある最小の頂点数を求…

問題 N個の都市がM本の道路でつながれている。i本目の道路は都市a_iとb_iを結び、y_i年に造られたものである。 Q人の国民がいる。国民jは都市v_jに住んでおり、作られた都市がw_jより大きな道路しか使わない。 各国民について、自身が住んでいる都市から条件…

問題 i 個の数の組 (w_i, h_i) が与えられる。これらから自由に選んで並べてw, hともに狭義単調増加な列を作るとき、その最大の長さは？ 制約 1 <= N <= 105 1 <= w_i <= 105 1 <= h_i <= 105 解法1: LIS まず、入力をwの昇順にソートします。すると、以下の…

BITの使い方を勉強しなおした。 問題 1, 2, ..., Nの順列がある。この順列の隣り合う2つの要素を並び替えるという操作により数字を山型に並び替えるには最小何回の操作が必要か。 制約 1 <= N <= 105 解法 Nをどこに持ってくるかの全通りに対して、左側の反…

問題 H: Counting 1's - square869120Contest #2 | AtCoder N個の0が並んでいる。 以下のクエリを処理せよ。 クエリ1: 区間[l, r)のビットを反転させる。 クエリ2: 区間[l, r)内の1の数を答える。 解法 遅延セグメント木。区間の問題なのでセグ木という発想…