読者です 読者をやめる 読者になる 読者になる

B - 島と橋

AtCoder C++

B: 島と橋 - AtCoder Beginner Contest 027 | AtCoder が解けない.ので考察を書きます.
2016/09/29 ACしました//そもそも,すべての島に同じ人数の住人が住んでいないか?の出力が人口になっていて,WAしていました.

 

  1. 全部の橋掛けのパターンを行列か何かにしてグループ分けしようとする
    →サンプルケースを書き出してみたけれど,規則性が分からないし,
{\displaystyle
\sum_{k=0}^{N} {}_{N}\mathrm{C}_{k}
}

の計算で死にそう.

  1. 一度すべての島を橋掛けて,最も人口が多い島で分割統治する
    再帰で求められる? コーディングが難しくて挫折.

  2. 一度すべての島を橋掛けて,最も人口が多い島から最も人口が少ない島へ流す →コーディングが難しそう.

  3. 人口が負数になるのを許して(最終的に合う),右端の島から目標人口*1にする
    →採用.結果WA

 

*1:全人口/島の数