hotpepsiの練習帳

TCO16 Algorithm Round 2C

19:19

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

Easy (250) BearBall

問題

• 2次元平面上にN匹の熊がいて、それぞれの座標が与えられる
• 1ターン毎に熊から熊へボールを投げるゲームを行う
• ボールの軌跡は直線である
• ボールの軌跡上にいて、ボールをさわったことのない熊がキャッチする
• 熊iからはじめて、熊jがボールをキャッチするまで行う
• iとjの全ての組み合わせについて、最短ターン数の合計を求める

方針

• (終了後)
• 全ての点が一直線上にあるか、そうでないかで場合分け
• 全てが一直線上にあるときは、途中の点をスキップできないので、全ての点同士の距離の組み合わせになる
• Σi×(i+1) = (N-1)×N×(N+1)÷6×2
• 全てが一直線上にないとき
• 始点からゴールまでの一直線上に他の熊がいなければ、1
• それ以外の場合、始点とゴールをさえぎらずに直接結ぶ1点が必ず存在するので、2
• https://github.com/firewood/topcoder/blob/master/tco_2016/BearBall.cpp

結果

--- 0pt 215th/510 rating 1467 -> 1429 (-38)

AM2時からの回。

二つくらい気づかないといけないので難しかった。

http://togetter.com/li/989152