tookunn’s diary

主に競技プログラミング関係

AGC

AtCoderGrandContest 005 B

AGC

問題文 agc005.contest.atcoder.jp解説見ました。 考察 愚直に個の区間ごとに最小値を計算しても計算量がになるのでTLEになる。ここで最小値になる値に注目して区間を考える。具体的な例として問題文の入力例2で考える。 i0123 a1324 の値を見ると最小値がに…

AtCoder Grand Contest 001 C Shorten Diameter

AGC

問題 agc001.contest.atcoder.jp 考察 ・直径がとなる木を考えた時の、中心となる木の頂点を中心点と呼ぶ。・中心点から距離が以下となる頂点の数を最大になるような中心点を選べば、削除する点が少なくて済む。・が奇数の時は、中心点の隣接する頂点一つを…