提出課題を効率的に片付けよう！

はじめに

皆さん、人生に一度はこう思ったことがありませんか？
「たくさん課題が出されたが、何から手を付けてよいかわからない」
今回は、この問題をコンピュータで解決していきます。

問題設定

以下のような問題を考えます。

$N$ 個の課題がある。 $i$ 個目の課題(課題$i$) は、時刻 $(0 \le) L_i$ に出題され、時刻 $(L_i <) R_i$ に締め切られる。また、この課題を片付けるためには時間 $R_i-L_i$ を要し、時間内に片付けることができれば成績に $S_i$ 点が加算される。現在時刻が $0$ であるとき、課題を適切に取捨選択すると最大で何点を獲得できるか。

いきなりこの問題を考えるのは難しいので、いくつかのステップに分けて考えてみましょう。

ステップ	課題
0	-
1	$N = 10^5,L_i=L_j, R_i = R_j\ (1 \le i < j \le N)$
2	$N = 10,S_i = 1\ (1 \le i \le N)$
3	$N = 10^5,S_i = 1\ (1 \le i \le N)$
4	$N = 10^5$

ステップ0 計算量

今回は、コンピュータを利用して解く事を考えます。
細かい話は色々とありますが、一般的な家庭用コンピュータでは $1$ 秒間におよそ $10^8$ 回の計算が出来ると言われています。¹なので、このコンピュータで $1$ 秒以内、すなわち $10^8$ 回以内の計算で収めることを考えていきます。

ステップ1

ウォーミングアップとして、全ての課題が重複している場合を考えてみましょう。

この場合は、 $S_i$ の一番大きいものを片付けるのが明らかに最適です。よって、このステップを解くことが出来ました。

ステップ2

いきなり、$L_i$ と $R_i$ がバラバラの状況を考えてみます。

とはいっても、 $N=10$ と、$N$ が先程より小さめです。このことを利用して、以下のような戦略が考えられます。

課題を片付ける優先順位を決め、順番に課題を片付けていく。時間に間に合わない課題は無視する。

課題を片付ける優先順位の決め方は $10!$ 通りで、それを順番に片付けることに $10$ 回の計算を要します。
$10! \times 10 = 36288000 \le 10^8$ より、このステップを解くことが出来ました。

ステップ3

このステップでは、 $N=10^5$ と大きめです。先程と同じように解くと、$10^5! \times 10^5 \risingdotseq 2.82 \times 10^{456578} > 10^8$ となり、到底 $1$ 秒に間に合いません。
それでは、どのように解決すれば良いのでしょうか。

実は、以下のようにすれば上手くいくことが分かります。

「課題の中で、提出期限が一番早いものから順に片付ける」

なぜこの戦略が上手くいくのでしょうか。

直感的な証明
「終了時刻が一番早い課題以外」を選ぶことは、「終了時刻が一番早い課題」を選ぶことに比べて明らかに損である。
(数学的な証明)

これを利用して解きます。すべての課題をその提出期限順に並び替えた後、それぞれの課題を片付けられるかを判定することで解くことが出来ます。

課題の並び替えにおよそ $10^6$ 回の計算²を、片付けられるかの判定に合計 $10^5$ 回の計算を要するので、 $10^6+10^5 \le 10^8$ より、この問題を解くことが出来ました。

ステップ4

いよいよ最後のステップです。

このステップでは、それぞれの課題に点数のバラツキがあり、更に課題が出される期間もバラバラという、より一層現実に近い設定となっています。

この問題では、先程のような戦略は通用しません。なぜなら、それぞれの課題を片付ける価値が異なるからです。

それでは、どのように解けば良いのでしょうか。ここで、このステップの問題を言い換えてみましょう。

$N$ 個のマシンがある。 $i$ 番目のマシンは時刻 $L_i$ に乗り込むことが出来、乗り込むと $S_i$ 円が手に入った後時刻 $R_i$ にタイムワープする。最大で何円手に入るか。

ここで、以下の事柄が成り立つことが分かります。

時刻 $t$ において、(その時までに獲得できるお金の最大値)円持っていなければ、時刻 $t'(\ge t)$ において、(その時までに獲得できるお金の最大値)円所持することは出来ない。

これを利用して、この問題を帰納的に解くことを考えます。

まず、 $L_i,R_i$ に含まれる以外の時刻には興味がないため、時刻を圧縮します。
その後、 $f(t) = $ (その時までに獲得できるお金の最大値) と定め、 $t$ の小さい方から $$f(t) = \mathrm{max}[f(t-1),f(L_i) + S_i{ \lbrace t = R_i} \rbrace]$$ と帰納的に更新していくことで、この問題を解くことが出来ます。³

時刻の圧縮におよそ $10^6$ 回⁴、 $f(t)$ の更新に最大で $3 \times 10^5$ 回⁵の計算を要するため、 $10^6 + 3 \times 10^5 \le 10^8$ より、この問題を解くことが出来ました。

おわりに

いかがだったでしょうか。特に最後のステップは難しかったかもしれません。

ステップ3で扱った問題は一般に「区間スケジューリング問題」と呼ばれ、
ステップ4で扱った問題は一般に「重み付き区間スケジューリング問題」と呼ばれています。

今回扱った問題は日常の中でよくあるシーンでの問題で、これ以外にも、「グーグルマップの最短経路の計算」や、「適切な買い物をしたい時」などの問題があり、それぞれに適当な手法を用いることで解くことが出来ます。

競技プログラミング⁶ではこのような課題をたくさん解決することが出来ます。また、今回は扱わなかった、コンピュータでの実装も体験することが出来ます。

興味を持った方はぜひ取り組んでみてください。きっと見ている世界の幅が広がることでしょう。

最後まで読んでいただき、ありがとうございました。

参考文献

https://qiita.com/e869120/items/5d9d0fcbb6dc7dbf87f9
https://algo-method.com/tasks/363/editorial
https://take44444.github.io/Algorithm-Book/range/isp/main.html
https://qiita.com/rMJ2pwyc4U/items/cbc05c0068d2c6126bf2

1. この値は、コンピュータの状況やプログラムの処理の内容によって変動します。なので、あくまでも一つの指標として認識しておいてください。 ↩

2. 現時点で一番効率の良い方法を利用した時の計算量です。詳しくは「ソートアルゴリズム 最速」で検索してみてください。 ↩

3. この手法は、一般に「動的計画法」と呼ばれています。 ↩

4. 「座標圧縮」と呼ばれる手法を利用した時の計算量です。 ↩

5. $\mathrm{max}(t)$ としてあり得る値が $2N$ 個($L_i$ と $R_i$ の値の種類数が高々 $2N$ 通り)、 $f(R_i)$ の更新は合計 $N$ 回なので、合わせて $3N$ 回の計算を要します。 ↩

6. Atcoder などのことです。 ↩