7K12B blog

猫でも分かる何か

ABC145 C - Average Length

f:id:tkr987:20200707041745p:plain

https://atcoder.jp/contests/abc145/submissions/15054171

  • 順列はstd::next_permutationが使える
  • next_permutationに渡す数列はソート済みである必要がある
  • 三平方の定理はstd::hypotが使える

f:id:tkr987:20200707041826p:plain

Nが8以下と非常に小さいので8!通り全列挙してもTLEしない。std::next_permutationを使えば簡単に順列が得られるが、予めソートされた数列でないと機能しない。そのため、ソートした街のindex配列をxy座標と別に用意しておく。三平方はstd::hypotが使える。最後にN!で割った平均値にして小数点で出力することを忘れずに。