2020JOI二次予選2 いちご解説

解説

難易度5の中では考察寄りな問題です。

結論から言うと、「座標と熟すまでの時間の和の最大値」と、「座標の最大値の2倍」のうち大きいほうが答えになります。以下に証明を示します。このような問題の証明を考えるのは、より難しい問題を解くのに必要なスキルの練習にもなるでしょう。

まず、この時間より時間が短くなることがないことを示します。

座標の最大値の位置のいちごを取りに行って帰ってくるまでの時間は座標の最大値の2倍なので、これより時間が短くなることはありません。

また、ある位置のいちごだけを取って帰ってくるまでの時間は、熟す時間になってそのいちごを取り、原点に戻る場合より短くなることはなく、この値は「座標と熟すまでの時間の和」となります。

これで、この時間より短い時間を達成することができないことが示せました。

次に、この時間での収穫が達成できることを示します。

まずどのいちごも収穫せずに座標が最大のいちごまで行って、いちごのある座標に来たら収穫できるようになるまで待ち、すぐに収穫してまた戻っていく、という方法を考えると、これに必要な時間は求めた時間に収まります。

よって、「座標と熟すまでの時間の和の最大値」と、「座標の最大値の2倍」のうち大きいほうが求める値となります。（証明終）