Google Kickstart 2020 RoundA -Workout問題の解説

Workoutの問題について、公式の解説と、Youtubeで見つけた有志の方の解説動画を見て実装しました。
コードは、こちらに置いています。

問題

問題文を要約すると、次のようなことです。
各要素がトレーニングセッションの時間（Mi）を表すN個のリストが与えられます。
このリストにおいて、隣り合う二つのセッション間の時間差のうち、最大のものを
このトレーニングの「困難さ」として定義、セッション間に最大でK個までセッションを追加した時、最も小さい「困難さ」を求める。
またこの時、トレーニングセッション時間は単調増加するものとする（Mi < Mi+1）。

アルゴリズム1(WA)

Test set1ではK＝1なのですが、この場合だと最大の時間差を半分にするというアルゴリズムでうまく行きます。サンプルとして提供されているテストケースを使って確かめてみます。

N=3 K=1
100 200 230 -> max(|100-200|, |200-230|) = 100
(K=1)
100 150 200 230 -> max(|100-150|, |150-200|, |200-230|) = 50
ans = 50

サンプルのアウトプットは「50」ということで、出力が一致します。
しかし、最大の差分を求めて、差分を二分割したセッションを追加するアルゴリズムだと、例えばK＝2で[2, 12]という入力では[2, 7, 12]→[2, 7, 9, 12]となって「５」が出力となるけれど、[2, 5, 12]→[2, 5, 8, 12]と追加すれば「４」が最小値となって、WAとなってしまいます。Test set2ではK=2以上なので、別のアルゴリズムが必要です。

アルゴリズム２(Passed)

セッション追加を繰り返して最適な$${d_{optimal}}$$を求めるのではなく、$${d_{optimal}}$$となるようにセッション追加した場合にK以下となるかを判定するというアルゴリズムを考えます。