hotpepsiの練習帳

SRM 704

02:51

https://competitiveprogramming.info/topcoder/srm/round/16849/div/1

Div1 Easy (300) TreeDistanceConstruction

問題

• 木において、距離d(u,v)は、uからvへ到達するために経由する辺の数の最小値である
• 頂点uのd(u,v)の最大値を、頂点uの偏心とする
• 各頂点iについて、偏心がd[i]となる木を構築せよ

方針

• 考察
  • 最長のものを考えると、A->B->C->D->Eのように一直線に連鎖しているものになる
  • 一番長いものを構築済であること仮定する
  • 中間地点にあるものが最短になる
  • 最短のものは、最長の辺の長さが偶数であれば1、奇数なら2つだけ存在できる
  • 最短以外の頂点は2つ以上存在する必要がある
  • 最短の頂点に葉を増やすと、距離がひとつ増えるので、最短の数を増やすことはできない
  • 最長の頂点に葉を増やすと、最長がのびることになるので、制約を満たさなくなる
  • つまり、最短と最長以外の頂点は増やすことができる
• 構築手順
  • 頂点を距離毎に分類する
  • 左右方向に構築することを考える
  • 左右それぞれの端(dが一番大きい)から、中心に向かってひとつずつのばしていき、3つ以上の頂点は葉として追加していく
  • 左の頂点はひとつ右(dが1小さい)に、右の頂点はひとつ左(dが1小さい)につなぐ。つなぐものがなければ失敗
  • 奇数の場合は最後の2つの頂点同士をつなぐ
• Passed System Test
• https://github.com/firewood/topcoder/blob/master/srm_7xx/srm_704/TreeDistanceConstruction.cpp

結果

o-- 117.61pt 184th/373 rating 1370 -> 1414 (+44)

紙に書いてそのまま実装したら通ってよかった。

AGCで既出だったらしい。

https://togetter.com/li/1064723