ABC 401-500/ABC435F - Cat exercise - 競技プログラミング用 知識集積所

---

問題

ABC435F

必要知識

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

• 貪欲法（アルゴリズム系）※
• 動的計画法
• バックトレース

考え方

タワーの撤去順序が多すぎるので、まずは貪欲法※で考えるべきパターン数を減らす。
結論から言ってしまえば、「そのタワーより左右いずれかのタワーを全て取り除いてからそのタワーを取り除く」という操作のみ考えればよい。

仮に、全部で7本のタワー（0番から6番）があって、最も高い（猫がいる）タワーが3番、2番目に高いタワーが5番、3番より左側で最も高いタワーを1番とする。
この場合、

• 次に0番に行かせるのはそもそも不可能
• 次に1番に行かせるのは、二度と4番から6番に行けなくなるので、右を全部取り除いても問題ない
• 次に2番に行かせるのは、一度1番に行かせてから2番に行かせる方が評価が高いので考えなくてよい
• 次に4番に行かせるのは、一度5番に行かせてから4番に行かせる方が評価が高いので考えなくてよい
• 次に5番に行かせるのは、二度と0番から2番に行けなくなるので、左を全部取り除いても問題ない
• 次に6番に行かせるのはそもそも不可能

となる。
同様に、どんなタワー配置でのどんな選択に対しても「そのタワーより左右いずれかのタワーを全て取り除いてからそのタワーを取り除く」が同等以上の操作になっている。

さて、そうなると、低い順にタワーを追加しながら、「その連続タワー区間内で最大何ステップになるか」を管理しながらバックトレースをする動的計画法で解ける。
すなわち、今追加したタワーに猫がいる状況から、

• 左側の最も高いタワーまでの距離+左側区間での最大ステップ数
• 右側の最も高いタワーまでの距離+右側区間での最大ステップ数

の大きい方を管理すればよい。

区間が持っている値は、区間の両端のタワーに

• 左端のタワー位置
• 右端のタワー位置
• その区間の最も高いタワー位置（-1でまだ未設置という判定を兼ねる）
• その区間で、それ以降の最高ステップ数

持たせておけば、その隣にタワーを追加するときのデータ参照/更新に困らない。

解答例

解答例

注意点

解答はlong long型にする

全体がV字型になっていて猫がものすごく左右に往復する場合、int型に収まらない場合がある。

別解