問題 解法 解答 問題 C - アットコーダー王国の交通事情 全ての頂点が連結であるグラフがあり，この全頂点間の最短距離の和を S とする．「頂点 X と Y の間にコスト Z の辺を追加」というクエリが K 回与えられるので，K 回それぞれに対して S を求める問題…

問題 解法 解答 問題 C - 仕事計画 a_i と b_i を始点・終点とする区間が N 個あり，それらからいくつか両端以外で重ならないように選ぶとき，最大でいくつ選べるかを求め，辞書順最小の組み合わせを求める問題． 解法 区間をソートし，時間を後ろから見てい…