上限値（Work Plan）

問題

Ａ君は今後 $ D $ 日間の労働計画を立てることにしました。

Ａ君はとにかくより多く働きたいと思っています。

しかし、働きすぎると怒られてしまうため $ i=1,2,…,N $ 日目に対して以下の条件満たす必要があります。

🔹条件 $ i $ ：$ L_i ～ R_i $ 日目について、最も多く働いた日でも労働時間を $ H_i $ 時間以下にする

Ａ君の $ D $ 日間の合計労働時間として考えられる最大値は何時間でしょうか。

[制約]
🔹$ 1 \leqq D \leqq 365 $
🔹$ 0 \leqq N \leqq 10000 $
🔹$ 1 \leqq L_i \leqq R_i \leqq D $
🔹$ 9 \leqq H_i \leqq 24 $

解き方・ソースコード

この問題では「$ L ～ R $日目について最も多く働いた日でも$ H $時間以下」という条件が与えられます。

この条件は「$ L ～ R $日目の労働時間はすべて $ H $ 時間以下」と言い換えることができます。

$ d $ 日目の労働時間の上限を $ LIM[d] $ とすると、この値は次のように計算することができます。

🔹手順１：1日は24時間なので、$ LIM[d]=24 $ に初期化する。
🔹手順２：$ i=1,2,…,N $ 日目に対して以下の処理を行う。
　・$ L_i \leqq d \leqq R_i $に対して、$ LIM[d] $ を $ min(LIM[d], H_i) $ に更新する。

上記で求めた上限値は $ N $ 個すべての条件を満たします。

したがって$ LIM[1] $ から $ LIM[D] $ までの総和を出力すると、正解となります。

計算量は $ O(ND) $ となります。

[Google Colaboratory]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#--------- 入力例 -----------
D = 5           # 労働計画を立てる日数
# 労働条件
COND = [
    {'L':1, 'R':2, 'H':22}, # 1日目から2日目について最も多く働いた時間は22時間以下
    {'L':2, 'R':3, 'H':16}, # 2日目から3日目について最も多く働いた時間は16時間以下
    {'L':3, 'R':5, 'H':9}   # 3日目から5日目について最も多く働いた時間は9時間以下
]

#----------------------------
# 配列の初期化（1 日は 24 時間）
LIM = [ 24 ] * (D + 1)

# 上限値を求める
for i, cond in enumerate(COND):
    for j in range(cond['L'], cond['R'] + 1):
        LIM[j] = min(LIM[j], cond['H'])

# 答えを出力
Answer = 0
for i in range(1, D + 1):
    print('{}日目に働ける最大時間数：{}'.format(i, LIM[i]))
    Answer += LIM[i]
print('解：', Answer)

[実行結果]

1日目に働ける最大時間数：22

2日目に働ける最大時間数：16

3日目に働ける最大時間数：9

4日目に働ける最大時間数：9

5日目に働ける最大時間数：9

解： 65

Ａ君が働ける最大時間数は65時間であることが分かりました。