問題 atcoder.jp 解法 街がN、経路がN-1であることから木構造であることがわかる。 木構造の頂点間の最短距離が奇数なら道で。 偶数なら街で出会う。 最短距離の偶奇を求めるために、各頂点の深さを計算。 深さから、頂点間の距離がわかる。 途中に共通の祖…

問題 atcoder.jp 難しい問題。 解法 動的計画法で解く。 線路のコスト計算はC x (|i - i'| + |j - j'|)円。 この計算式から絶対値を外していく。 i' <= i, J' <= jとすれば C x i - C x i' + C x j - C x j' = C x i + C x j - C x i' - C x j' = C ( i + j …

問題 atcoder.jp 解法 いわゆる「しゃくとり法」で解ける問題。 数列cの中からK個の連続した数値を選び、その種類が最大になる範囲を総当たりで調べる。 わけだけど、ベタに作ると計算量が多すぎる。 範囲の左端と右端を決定し、色数を計算。 色数が最大か？…