ABC197 E Traveler
まず貪欲解法が思いつくが, すぐに反例が見つかる. そこで, 貪欲がダメな時はDPという典型を用いてDPを考えてみると上手くいく.色ごとに分けて考えると最後に訪れるのは最適な行動をすると左端か右端のどちらかしかないことに注目する. $ dp_{i, j} := ボールの色を$ iまで見て, 色$ iの最終到着地点を$ j ? 左端 : 右端 としたときの時間の最小値 としてDPをしていく. これは各色について左端と右端を前計算しておくことによって各色について$ O(1)で遷移でき, 全体として$ O(N)となって十分高速.