E - Subsequence Path DPできます。 長さ$N$のDP配列(これは頂点 $1$ からの最短距離を表します)を $dp[1]=0,dp[i]=inf(i > 1)$ で初期化します。そして、各 $E_i$ に対して、$chmin(dp[A_{E_i}], dp[B_{E_i}] + C_{E_i})$ と遷移していきます。これにより、…

E - Traveler 各色ごとに回収する順番を考えます。色 $i$ に対して、最も座標が小さいものを $Min_i$ 、最も座標が大きいものを $Max_i$ とすると、簡単に言えば $Max_i$ までまっすぐ行ってから $Min_i$ に行く、または $Min_i$ までまっすぐ行ってから $Ma…

D - Flipping and Bonus DPをします。$dp[$(0-indexedで)$i$回目のコイントスで$][j$回連続で表が出ているとき$]$のこれまでもらったお金の最大値 というDPができます。遷移は、$i$連続の連続ボーナスを$Bonus[i]$(なければ$0$)とすると、 $dp[i][0]=max(dp[…