問題
A君は今後 日間の労働計画を立てることにしました。
A君はとにかくより多く働きたいと思っています。
しかし、働きすぎると怒られてしまうため 日目に対して以下の条件満たす必要があります。
🔹条件 : 日目について、最も多く働いた日でも労働時間を 時間以下にする
A君の 日間の合計労働時間として考えられる最大値は何時間でしょうか。
[制約]
🔹
🔹
🔹
🔹
解き方・ソースコード
この問題では「日目について最も多く働いた日でも時間以下」という条件が与えられます。
この条件は「日目の労働時間はすべて 時間以下」と言い換えることができます。
日目の労働時間の上限を とすると、この値は次のように計算することができます。
🔹手順1:1日は24時間なので、 に初期化する。
🔹手順2: 日目に対して以下の処理を行う。
・に対して、 を に更新する。
上記で求めた上限値は 個すべての条件を満たします。
したがって から までの総和を出力すると、正解となります。
計算量は となります。
[Google Colaboratory]
1 | #--------- 入力例 ----------- |
[実行結果]
1日目に働ける最大時間数:22 2日目に働ける最大時間数:16 3日目に働ける最大時間数:9 4日目に働ける最大時間数:9 5日目に働ける最大時間数:9 解: 65
A君が働ける最大時間数は65時間であることが分かりました。