cafelier@SRM

SRM610 Div1 550

SRM | 20:03 |

• 入力
  • 初期燃料 F
  • タスクの集合 T = (d[0],r[0]), (d[1],r[1]), ... (d[N-1],r[N-1])
• 求めるもの
  1. 初期値 f = F
  2. Tから d<=f であるような一組(d,r)を取り除き、f=f-d+r とする
  3. ステップ2を繰り返す
  4. できるだけ多くステップ2を繰り返せるように頑張ったら何回できますか

解くときに考えたこと。

• Tから取り出す順番がフリーダムだとパターンが多すぎて考えにくい。
• 固定の順番で試してみれば十分ということはないだろうか？
  • たとえば、d が小さいタスクは後の方に回しても実行できるから、必ず d が大きい順に実行する方がお得とか
  • たとえば、d-r が小さい方が燃料の減りがトータルで少なくて後のタスクに差し支えにくいので、こういうのを先にやった方が絶対お得とか
  • なんかそんな感じの。

• そもそも順番固定したら解けるのかっていうと謎だけど。
• それは未来の自分が頑張って格好良く解いてくれる！頑張れ未来の自分！

• ということで試す順序の固定の仕方を考える。
  • タスク T1=(d1,r1) と T2=(d2,r2) があるとき、どっちを先に実行するべきか？
  • 「先にやっても損がない」方を先にやるべき。
    • 先にやると損というのは、"T1をやった後でもT2はできるのに、T2をやった後は燃料不足でT1ができない" みたいな状況。これはT2を先にやるのは損。
    • 逆にいうと「T1を先にやっても損がない」とは
    • 「T2→T1 の順でできるなら T1→T2 の順でもできる」ことと同値。
    • なぜならT1を先にやってもT2ができる可能性を狭めないから損がない。

• 「T2→T1 の順でできるなら T1→T2 の順でもできる」とは何か。
  • T2→T1の順でやると燃料は (-d2, -d2+r2, -d2+r2-d1, -d2+r2-d1+r1) の順に移り変わる。
  • この時、燃料がもっとも少なくなるのは min(-d2, -d2+r2-d1) のとき。
  • T1→T2 の時の燃料の底は min(-d1, -d1+r1-d2)
  • 燃料が一番少ない瞬間に余裕があるタスク順の方が実行しやすいので
• 「T2→T1 の順でできるなら T1→T2 の順でもできる」 とはすなわち
• 後者の方が燃料の底が大ということなので
  • min(-d1, -d1+r1-d2) >= min(-d2, -d2+r2-d1)
  • のことである。

• 問題は、この謎の条件式が全順序関係になっているかどうか。
• じゃんけんの勝ち負けみたいに「こっちを先にした方が損がない」関係が輪になっているとソートして先頭から順に試すとかができないので困る。
• 何とかして全順序になっているかどうかを見抜きたい。わからん。

• min(-d1, -d1+r1-d2) >= min(-d2, -d2+r2-d1)
  • の何がわからんかというと、dとrが色々混ざっててわからん。
  • 分解しましょう。
  • 「x >= min(y,z)」 は 「x>=y または x>=z」と同値。つまり
• min(-d1, -d1+r1-d2) >= -d2 または min(-d1, -d1+r1-d2) >= -d2+r2-d1
  • さらに「min(a,b)>=c」は「a>=c かつ b>=c」と同値。つまり
• 「-d1>=-d2 かつ -d1+r1-d2>=-d2」または「-d1>=-d2+r2-d1 かつ -d1+r1-d2>=-d2+r2-d1」

• さて
  • 問題文の条件で、d>r と書いてある。
  • つまり -d1+r1 < 0
  • つまり２個目の論理式 -d1+r1-d2>=-d2 は絶対に成り立たない
• 「-d1>=-d2 かつ False」または「-d1>=-d2+r2-d1 かつ -d1+r1-d2>=-d2+r2-d1」
  • つまり
• 「False」または「-d1>=-d2+r2-d1 かつ -d1+r1-d2>=-d2+r2-d1」
  • つまり
• 「-d1>=-d2+r2-d1 かつ -d1+r1-d2>=-d2+r2-d1」

• 同様に
  • -d2+r2 < 0 なので「-d1>=-d2+r2-d1」これは絶対にTrue。
• 「True かつ -d1+r1-d2>=-d2+r2-d1」
  • つまり
• -d1+r1-d2>=-d2+r2-d1
  • なにか両辺に-d1とか-d2とか同じ物がある。消そう。
• r1 >= r2。

• まとめよう。
  • 「T1 を T2 より先にやった方が損がない」iff
  • 「T2→T1 の順でできるなら T1→T2 の順でもできる」iff
  • 「min(-d1, -d1+r1-d2) >= min(-d2, -d2+r2-d1)」iff
  • 「r1 >= r2」
• つまり r の大きいタスクから先に試すべき。

• あとは未来の自分が頑張った。