上限値（Work Plan）

問題

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

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

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

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

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

[制約]
🔹1≦D≦365
🔹0≦N≦10000
🔹1≦Li≦Ri≦D
🔹9≦Hi≦24

解き方・ソースコード

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

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

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

🔹手順１：1日は24時間なので、LIM[d]=24 に初期化する。
🔹手順２：i=1,2,…,N 日目に対して以下の処理を行う。
　・Li≦d≦Riに対して、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

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