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:全人口/島の数