上限値(Work Plan)

問題

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

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

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

🔹条件 i LiRi 日目について、最も多く働いた日でも労働時間を Hi 時間以下にする

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

[制約]
🔹1D365
🔹0N10000
🔹1LiRiD
🔹9Hi24

解き方・ソースコード

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

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

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

🔹手順1:1日は24時間なので、LIM[d]=24 に初期化する。
🔹手順2i=1,2,,N 日目に対して以下の処理を行う。
 ・LidRiに対して、LIM[d]min(LIM[d],Hi) に更新する。

上記で求めた上限値は 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

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