ABC146-F Sugoroku
直線上のすごろくで踏んではいけないマス目があり、コマの目が１～Mの時、最短手数とその時の辞書順で一番小さい目の出方を求めよ、という問題。
前から貪欲にいけば最短手数はすぐ求まるなと思ったが辞書順最小がややネック。少しして貪欲をすると必然的に辞書順最大になるから、後ろから貪欲すればいいことに気付いた。配列の後ろから見るというのもよく使う手法だなと思った。
E-All you can eat
答えが時間の昇順になることを利用してknapsack dp
ABC146-F Sugoroku
直線上のすごろくで踏んではいけないマス目があり、コマの目が１～Mの時、最短手数とその時の辞書順で一番小さい目の出方を求めよ、という問題。
前から貪欲にいけば最短手数はすぐ求まるなと思ったが辞書順最小がややネック。少しして貪欲をすると必然的に辞書順最大になるから、後ろから貪欲すればいいことに気付いた。配列の後ろから見るというのもよく使う手法だなと思った。
E-All you can eat
答えが時間の昇順になることを利用してknapsack dp