問題
考察
まず始めに,
- 人数の合計 sum が のときは .
- sum が島の数 で割り切れなかったら .
までは分かった.その後解法が思いつかなかっのでとりあえずサンプルを紙に書き出してみたら解法が分かった.分けた後の各島の人数は であるため,その人数と初期値の差分ベクトルを計算し,累積和を求め,それがゼロになったところを グループとして橋をかければいいんじゃないかと考えた.考察は以下の通り.
解法
abc027 from AtCoder Inc.
www.slideshare.net
解法は上の考察をそのまま実装すれば良い.
「累積和が になったらグループ化して橋をかける」という考察が上手くできて嬉しかったのでついついブログに書いてしまいました.ここまで読んでくださりありがとうございます.