hotpepsiの練習帳

TCO13 Algorithm Round2C

02:00

Easy (250) DancingFoxes

問題

• N人でダンスをする
• 共通の友達同士でダンスをすると友達になれる
• 友達かどうかが与えられる
• CielとJiroが友達になるための最小のダンスの回数を求める

方針

• Warshall-Floydで距離を求める
• 距離がダンスの回数?
• Challenge Succeeded
• (終了後)
• ダンスイベントの回数だったらしい
• editorialを読む
• 直接の友達の距離を1として、総距離Dを求める
• N=D+1人をフラットに並べて、左端と右端がCielとJiroと考える
• 連続した3人ずつを1グループとして、同じイベントでダンスをする
• 3人の両端の2人がダンスをして、終了後、直接友達になり、人数が1減る
• 3人に満たない人数ならダンスしない
• すなわち、Nが3以上のとき、人数がN/3ずつ減っていく
• https://github.com/firewood/topcoder/blob/master/tco_2013/DancingFoxes.cpp

結果

--- 0pt 519th/978 rating 1320 -> 1311 (-9)

イベントの回数という解釈ができたとしても解けなかった気がする。