Hatena::Grouptopcoder

hotpepsiの練習帳

2017-01-06

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

トラックバック - http://topcoder.g.hatena.ne.jp/firewood/20170106