ABC 401-500/ABC404E - Bowls and Beans - 競技プログラミング用 知識集積所

---

問題

ABC404E

必要知識

B以下レベルの内容は省略

• 貪欲法（アルゴリズム系）（未作成）

考え方

損しないように手順の自由度を減らすことを考える。

まず、拾った豆を自由に分散して移動できるが、これは実は何もメリットがない。
まとめて茶碗に入れたとして、その先でその一団を一度に運べなくなる事態が起こりえない。
したがって、分散することは考えなくてよい、というか同じ茶碗に2つ以上豆が入っていても1個に減らしてしまってよい。

また、同じ理由で、別の豆を跳び越すような移動にはメリットがない。
跳び越すことが可能なのであれば合流させることができるはずで、跳び越すのが合流より得する場合は絶対にない。

ということは、「最も遠い豆を、全ての豆入り茶碗を途中経由して0番まで移動させる方法」を考えればよい。
一度の移動距離は任意に短くできるので、

• 次の豆入り茶碗（または0番）まで移動できる場合は、そこへ移動
• 次の豆入り茶碗（または0番）まで移動できない場合は、2回先で最も遠くまで行けるところへ移動

を繰り返すのが最短手順の一例となる。

追加で0番に豆を入れておくと処理が楽になる。

解答例

解答例

注意点

別解