Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2012-03-10SRM380,SRM381,SRM382 (Practice)

SRM 382 PointsOnACircle

|  SRM 382 PointsOnACircle - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 382 PointsOnACircle - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=8238

  • 方針を検討
    • とりあえず、1度から359度回してみて一番いいのを選べばいいだろう
    • グラフにしてみるとフローで解けるかな?
      • 0〜359までのノードを考え、赤と青のノードに分割して考える
  • サンプル合わない・・・
    • 同じノードを2回使ってしまっていることに気づく。
    • フローじゃ解けない
    • いやそもそもフローなんて高等なもの使わなくていい気がする。
      • 一つの点からは高々一つの点にしかいかないんだし・・・
  • しばらく唸って時間切れ。

その後

  • 単純に、連結してるノードを数えてやればいいだけだった
    • ノードは単純に分割せず考える
    • ループが発生する場合に注意する
oolean