LoginSignup
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

@o_chan_t(おー ちゃん)

【競技プログラミング】AtCoder Beginner Contest 285_E問題

Last updated at Posted at 2024-12-07

問題

要約

  1. 高橋君の世界の1週間はN日間。
  2. 各曜日（1からNまで）に「平日」か「休日」を割り当てる。
  3. 少なくとも1つの曜日は「休日」にする必要がある。
  4. 曜日iの生産量は以下のように定義される：
    • 休日の場合：0
    • 平日の場合：A_min(x,y)
      ここで、xは直前の休日までの日数、yは直後の休日までの日数
  5. 割り当ては毎週同じで、週をまたいで直前・直後の休日を考慮する。

目標：
一週間あたりの総生産量（曜日1からNまでの生産量の合計）が最大になるように曜日を割り当てる。

変数情報：

  • N: 1週間の日数
  • A: 長さNの数列で、生産量を計算するために使用

既存投稿一覧ページへのリンク

一覧ページ

アプローチ

動的計画法（DP）を使用して、効率的に最適な休日の割り当てを見つける。
DPテーブルを作成し、各段階で最大の生産量を記録する。
各段階で最適な休日の配置を考慮し、それまでの最大生産量に基づいて新しい最大生産量を計算する。
最終的に、dp[N]が1週間の最大総生産量を表すことになる。

解法手順

  1. 入力を受け取る：

    • Nを整数として読み込む
    • Aを長さNの整数リストとして読み込む

  2. 累積和を計算する：

    • Bという新しいリストを作成し、Aの累積和を格納する
    • Bの要素は、A[0]からA[i//2]までの和となる

  3. DPテーブルを初期化する：

    • 長さN+1の配列dpを作成し、全ての要素を0で初期化する

  4. DPを実行する：

    • 1からNまでの各iについて以下を行う：
      • 0からi-1までの各jについて：
        • dp[i]を、dp[j] + B[i - j - 1]と現在のdp[i]の大きい方で更新する

  5. 結果を出力する：

    • dp[N]を出力する（これが最大の総生産量となる）

ACコード

ac.py

def solve(N, A):
    # 2. 累積和を計算する
    B = [0]  # Bという新しいリストを作成し、最初の要素を0とする
    for i in range(N + 1):
        B.append(B[-1] + A[i//2])  # Bの要素は、A[0]からA[i//2]までの和となる

    # 3. DPテーブルを初期化する
    dp = [0] * (N + 1)  # 長さN+1の配列dpを作成し、全ての要素を0で初期化する

    # 4. DPを実行する
    for i in range(1, N + 1):  # 1からNまでの各iについて以下を行う
        for j in range(i):  # 0からi-1までの各jについて
            dp[i] = max(dp[i], dp[j] + B[i - j - 1])  # dp[i]を、dp[j] + B[i - j - 1]と現在のdp[i]の大きい方で更新する

    # 5. 結果を出力する
    print(dp[N])  # dp[N]を出力する（これが最大の総生産量となる）

if __name__=="__main__":
    # 1. 入力を受け取る
    N = int(input())  # Nを整数として読み込む
    A = [int(x) for x in input().split()]  # Aを長さNの整数リストとして読み込む
    solve(N, A)

考察

  • 「巡回セールスマン問題」の変種。
  • 区間DP（Interval DP）と呼ばれる動的計画法の一種。

この動的計画法が最適解を与える理由

この方法は、全ての可能な休日の配置を考慮している。
各ステップで、それまでの最適解（dp[j]）と新たに追加される期間の生産量（B[i-j-1]）の和を計算し、その最大値を選択している。
これにより、全ての可能な組み合わせの中から最大の総生産量を持つものを選択することができる。

数学的帰納法による証明

全ての可能な休日の配置を考慮する。
各ステップで、それまでの最適解（dp[j]）と新たに追加される期間の生産量（B[i-j-1]）の和を計算し、その最大値を選択する。
これにより、全ての可能な組み合わせの中から最大の総生産量を持つものを選択することができる。

n=1

n=1のとき、dp[1] = B[0] = 0 となる。
なぜなら、1日だけの場合は必ず休日となり、生産量は0になるため。

帰納仮定

n=kのとき、dp[k]が正しい値（k日間の最大総生産量）を持つと仮定する。

n=k+1の証明

n=k+1のとき、dp[k+1]が正しい値を持つことを証明する。

dp[k+1]の計算式は以下のようになっている

dp[k+1] = \max_{0 \leq j \leq k} (dp[j] + B[k+1-j-1])

この式の意味を説明する：

  • dp[j]は、最初のj日間の最大総生産量を表す。
  • B[k+1-j-1]は、j+1日目からk+1日目までの累積生産量を表す。
  • jを0からkまで変化させることで、k+1日目の直前に休日を置く全てのパターンを考慮している。

B[i]の定義から、B[k+1-j-1]は以下のように表される：

B[k+1-j-1] = \sum_{l=0}^{\lfloor (k-j)/2 \rfloor} A[l]

これは、j+1日目からk+1日目までの間に、最大で(k-j)/2個の平日が存在することを意味する。

帰納仮定により、dp[j]は正しい値を持つ。
また、B[k+1-j-1]は正しく累積和を表している。
したがって、dp[k+1]は k+1 日間の最大総生産量を正しく計算している。

補足

累積和Bの役割

Bは連続する平日の生産量の和を効率的に計算するために使用されている。
これにより、計算量を削減される。

max関数の使用

全ての可能な分割点（休日の位置）を考慮し、その中で最大の値を選択することで、最適解を保証している。

ループ変数の説明

  • 外側のループ変数i（1からN）：現在計算している日数を表す。
  • 内側のループ変数j（0からi-1）：最後の休日の位置を表す。

結論

以上より、すべてのnに対して、dp[n]が正しい値（n日間の最大総生産量）を持つことが証明された。

最終的な解答

dp[N]に格納される。
これは、N日間の最大総生産量を表す。

机上トレース

例01

N = 11
A = [10, 3, 8, 3, 6, 3, 8, 7, 8, 6, 6]

2. 累積和を計算する

  • B: [0, 10] -> B[-1](=10) + A[0](=10)

  • B: [0, 10, 20] -> B[-1](=20) + A[0](=10)

  • B: [0, 10, 20, 23] -> B[-1](=23) + A[1](=3)

  • B: [0, 10, 20, 23, 26] -> B[-1](=26) + A[1](=3)

  • B: [0, 10, 20, 23, 26, 34] -> B[-1](=34) + A[2](=8)

  • B: [0, 10, 20, 23, 26, 34, 42] -> B[-1](=42) + A[2](=8)

  • B: [0, 10, 20, 23, 26, 34, 42, 45] -> B[-1](=45) + A[3](=3)

  • B: [0, 10, 20, 23, 26, 34, 42, 45, 48] -> B[-1](=48) + A[3](=3)

  • B: [0, 10, 20, 23, 26, 34, 42, 45, 48, 54] -> B[-1](=54) + A[4](=6)

  • B: [0, 10, 20, 23, 26, 34, 42, 45, 48, 54, 60] -> B[-1](=60) + A[4](=6)

  • B: [0, 10, 20, 23, 26, 34, 42, 45, 48, 54, 60, 63] -> B[-1](=63) + A[5](=3)

  • B: [0, 10, 20, 23, 26, 34, 42, 45, 48, 54, 60, 63, 66]

3. DPテーブルを初期化する

dp = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]

4. DPを実行する

  • 曜日1までの最大生産量【0】と曜日0までの最大生産量【0+B[1-0-1](=B[0]=0)】の大きい方で更新する
    dp[1]=0
    dp = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
  • 曜日2までの最大生産量【10】と曜日0までの最大生産量【0+B[2-0-1](=B[1]=10)】の大きい方で更新する
    dp[2]=10
    dp = [0, 0, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0]
  • 曜日2までの最大生産量【10】と曜日1までの最大生産量【0+B[2-1-1](=B[0]=0)】の大きい方で更新する
    dp[2]=10
    dp = [0, 0, 10, 0, 0, 0, 0, 0, 0, 0, 0, 0]
  • 曜日3までの最大生産量【20】と曜日0までの最大生産量【0+B[3-0-1](=B[2]=20)】の大きい方で更新する
    dp[3]=20
    dp = [0, 0, 10, 20, 0, 0, 0, 0, 0, 0, 0, 0]
  • 曜日3までの最大生産量【20】と曜日1までの最大生産量【0+B[3-1-1](=B[1]=10)】の大きい方で更新する
    dp[3]=20
    dp = [0, 0, 10, 20, 0, 0, 0, 0, 0, 0, 0, 0]
  • 曜日3までの最大生産量【20】と曜日2までの最大生産量【10+B[3-2-1](=B[0]=0)】の大きい方で更新する
    dp[3]=20
    dp = [0, 0, 10, 20, 0, 0, 0, 0, 0, 0, 0, 0]
  • 曜日4までの最大生産量【23】と曜日0までの最大生産量【0+B[4-0-1](=B[3]=23)】の大きい方で更新する
    dp[4]=23
    dp = [0, 0, 10, 20, 23, 0, 0, 0, 0, 0, 0, 0]
  • 曜日4までの最大生産量【23】と曜日1までの最大生産量【0+B[4-1-1](=B[2]=20)】の大きい方で更新する
    dp[4]=23
    dp = [0, 0, 10, 20, 23, 0, 0, 0, 0, 0, 0, 0]
  • 曜日4までの最大生産量【23】と曜日2までの最大生産量【10+B[4-2-1](=B[1]=10)】の大きい方で更新する
    dp[4]=23
    dp = [0, 0, 10, 20, 23, 0, 0, 0, 0, 0, 0, 0]
  • 曜日4までの最大生産量【23】と曜日3までの最大生産量【20+B[4-3-1](=B[0]=0)】の大きい方で更新する
    dp[4]=23
    dp = [0, 0, 10, 20, 23, 0, 0, 0, 0, 0, 0, 0]
  • 曜日5までの最大生産量【26】と曜日0までの最大生産量【0+B[5-0-1](=B[4]=26)】の大きい方で更新する
    dp[5]=26
    dp = [0, 0, 10, 20, 23, 26, 0, 0, 0, 0, 0, 0]
  • 曜日5までの最大生産量【26】と曜日1までの最大生産量【0+B[5-1-1](=B[3]=23)】の大きい方で更新する
    dp[5]=26
    dp = [0, 0, 10, 20, 23, 26, 0, 0, 0, 0, 0, 0]
  • 曜日5までの最大生産量【30】と曜日2までの最大生産量【10+B[5-2-1](=B[2]=20)】の大きい方で更新する
    dp[5]=30
    dp = [0, 0, 10, 20, 23, 30, 0, 0, 0, 0, 0, 0]
  • 曜日5までの最大生産量【30】と曜日3までの最大生産量【20+B[5-3-1](=B[1]=10)】の大きい方で更新する
    dp[5]=30
    dp = [0, 0, 10, 20, 23, 30, 0, 0, 0, 0, 0, 0]
  • 曜日5までの最大生産量【30】と曜日4までの最大生産量【23+B[5-4-1](=B[0]=0)】の大きい方で更新する
    dp[5]=30
    dp = [0, 0, 10, 20, 23, 30, 0, 0, 0, 0, 0, 0]
  • 曜日6までの最大生産量【34】と曜日0までの最大生産量【0+B[6-0-1](=B[5]=34)】の大きい方で更新する
    dp[6]=34
    dp = [0, 0, 10, 20, 23, 30, 34, 0, 0, 0, 0, 0]
  • 曜日6までの最大生産量【34】と曜日1までの最大生産量【0+B[6-1-1](=B[4]=26)】の大きい方で更新する
    dp[6]=34
    dp = [0, 0, 10, 20, 23, 30, 34, 0, 0, 0, 0, 0]
  • 曜日6までの最大生産量【34】と曜日2までの最大生産量【10+B[6-2-1](=B[3]=23)】の大きい方で更新する
    dp[6]=34
    dp = [0, 0, 10, 20, 23, 30, 34, 0, 0, 0, 0, 0]
  • 曜日6までの最大生産量【40】と曜日3までの最大生産量【20+B[6-3-1](=B[2]=20)】の大きい方で更新する
    dp[6]=40
    dp = [0, 0, 10, 20, 23, 30, 40, 0, 0, 0, 0, 0]
  • 曜日6までの最大生産量【40】と曜日4までの最大生産量【23+B[6-4-1](=B[1]=10)】の大きい方で更新する
    dp[6]=40
    dp = [0, 0, 10, 20, 23, 30, 40, 0, 0, 0, 0, 0]
  • 曜日6までの最大生産量【40】と曜日5までの最大生産量【30+B[6-5-1](=B[0]=0)】の大きい方で更新する
    dp[6]=40
    dp = [0, 0, 10, 20, 23, 30, 40, 0, 0, 0, 0, 0]
  • 曜日7までの最大生産量【42】と曜日0までの最大生産量【0+B[7-0-1](=B[6]=42)】の大きい方で更新する
    dp[7]=42
    dp = [0, 0, 10, 20, 23, 30, 40, 42, 0, 0, 0, 0]
  • 曜日7までの最大生産量【42】と曜日1までの最大生産量【0+B[7-1-1](=B[5]=34)】の大きい方で更新する
    dp[7]=42
    dp = [0, 0, 10, 20, 23, 30, 40, 42, 0, 0, 0, 0]
  • 曜日7までの最大生産量【42】と曜日2までの最大生産量【10+B[7-2-1](=B[4]=26)】の大きい方で更新する
    dp[7]=42
    dp = [0, 0, 10, 20, 23, 30, 40, 42, 0, 0, 0, 0]
  • 曜日7までの最大生産量【43】と曜日3までの最大生産量【20+B[7-3-1](=B[3]=23)】の大きい方で更新する
    dp[7]=43
    dp = [0, 0, 10, 20, 23, 30, 40, 43, 0, 0, 0, 0]
  • 曜日7までの最大生産量【43】と曜日4までの最大生産量【23+B[7-4-1](=B[2]=20)】の大きい方で更新する
    dp[7]=43
    dp = [0, 0, 10, 20, 23, 30, 40, 43, 0, 0, 0, 0]
  • 曜日7までの最大生産量【43】と曜日5までの最大生産量【30+B[7-5-1](=B[1]=10)】の大きい方で更新する
    dp[7]=43
    dp = [0, 0, 10, 20, 23, 30, 40, 43, 0, 0, 0, 0]
  • 曜日7までの最大生産量【43】と曜日6までの最大生産量【40+B[7-6-1](=B[0]=0)】の大きい方で更新する
    dp[7]=43
    dp = [0, 0, 10, 20, 23, 30, 40, 43, 0, 0, 0, 0]
  • 曜日8までの最大生産量【45】と曜日0までの最大生産量【0+B[8-0-1](=B[7]=45)】の大きい方で更新する
    dp[8]=45
    dp = [0, 0, 10, 20, 23, 30, 40, 43, 45, 0, 0, 0]
  • 曜日8までの最大生産量【45】と曜日1までの最大生産量【0+B[8-1-1](=B[6]=42)】の大きい方で更新する
    dp[8]=45
    dp = [0, 0, 10, 20, 23, 30, 40, 43, 45, 0, 0, 0]
  • 曜日8までの最大生産量【45】と曜日2までの最大生産量【10+B[8-2-1](=B[5]=34)】の大きい方で更新する
    dp[8]=45
    dp = [0, 0, 10, 20, 23, 30, 40, 43, 45, 0, 0, 0]
  • 曜日8までの最大生産量【46】と曜日3までの最大生産量【20+B[8-3-1](=B[4]=26)】の大きい方で更新する
    dp[8]=46
    dp = [0, 0, 10, 20, 23, 30, 40, 43, 46, 0, 0, 0]
  • 曜日8までの最大生産量【46】と曜日4までの最大生産量【23+B[8-4-1](=B[3]=23)】の大きい方で更新する
    dp[8]=46
    dp = [0, 0, 10, 20, 23, 30, 40, 43, 46, 0, 0, 0]
  • 曜日8までの最大生産量【50】と曜日5までの最大生産量【30+B[8-5-1](=B[2]=20)】の大きい方で更新する
    dp[8]=50
    dp = [0, 0, 10, 20, 23, 30, 40, 43, 50, 0, 0, 0]
  • 曜日8までの最大生産量【50】と曜日6までの最大生産量【40+B[8-6-1](=B[1]=10)】の大きい方で更新する
    dp[8]=50
    dp = [0, 0, 10, 20, 23, 30, 40, 43, 50, 0, 0, 0]
  • 曜日8までの最大生産量【50】と曜日7までの最大生産量【43+B[8-7-1](=B[0]=0)】の大きい方で更新する
    dp[8]=50
    dp = [0, 0, 10, 20, 23, 30, 40, 43, 50, 0, 0, 0]
  • 曜日9までの最大生産量【48】と曜日0までの最大生産量【0+B[9-0-1](=B[8]=48)】の大きい方で更新する
    dp[9]=48
    dp = [0, 0, 10, 20, 23, 30, 40, 43, 50, 48, 0, 0]
  • 曜日9までの最大生産量【48】と曜日1までの最大生産量【0+B[9-1-1](=B[7]=45)】の大きい方で更新する
    dp[9]=48
    dp = [0, 0, 10, 20, 23, 30, 40, 43, 50, 48, 0, 0]
  • 曜日9までの最大生産量【52】と曜日2までの最大生産量【10+B[9-2-1](=B[6]=42)】の大きい方で更新する
    dp[9]=52
    dp = [0, 0, 10, 20, 23, 30, 40, 43, 50, 52, 0, 0]
  • 曜日9までの最大生産量【54】と曜日3までの最大生産量【20+B[9-3-1](=B[5]=34)】の大きい方で更新する
    dp[9]=54
    dp = [0, 0, 10, 20, 23, 30, 40, 43, 50, 54, 0, 0]
  • 曜日9までの最大生産量【54】と曜日4までの最大生産量【23+B[9-4-1](=B[4]=26)】の大きい方で更新する
    dp[9]=54
    dp = [0, 0, 10, 20, 23, 30, 40, 43, 50, 54, 0, 0]
  • 曜日9までの最大生産量【54】と曜日5までの最大生産量【30+B[9-5-1](=B[3]=23)】の大きい方で更新する
    dp[9]=54
    dp = [0, 0, 10, 20, 23, 30, 40, 43, 50, 54, 0, 0]
  • 曜日9までの最大生産量【60】と曜日6までの最大生産量【40+B[9-6-1](=B[2]=20)】の大きい方で更新する
    dp[9]=60
    dp = [0, 0, 10, 20, 23, 30, 40, 43, 50, 60, 0, 0]
  • 曜日9までの最大生産量【60】と曜日7までの最大生産量【43+B[9-7-1](=B[1]=10)】の大きい方で更新する
    dp[9]=60
    dp = [0, 0, 10, 20, 23, 30, 40, 43, 50, 60, 0, 0]
  • 曜日9までの最大生産量【60】と曜日8までの最大生産量【50+B[9-8-1](=B[0]=0)】の大きい方で更新する
    dp[9]=60
    dp = [0, 0, 10, 20, 23, 30, 40, 43, 50, 60, 0, 0]
  • 曜日10までの最大生産量【54】と曜日0までの最大生産量【0+B[10-0-1](=B[9]=54)】の大きい方で更新する
    dp[10]=54
    dp = [0, 0, 10, 20, 23, 30, 40, 43, 50, 60, 54, 0]
  • 曜日10までの最大生産量【54】と曜日1までの最大生産量【0+B[10-1-1](=B[8]=48)】の大きい方で更新する
    dp[10]=54
    dp = [0, 0, 10, 20, 23, 30, 40, 43, 50, 60, 54, 0]
  • 曜日10までの最大生産量【55】と曜日2までの最大生産量【10+B[10-2-1](=B[7]=45)】の大きい方で更新する
    dp[10]=55
    dp = [0, 0, 10, 20, 23, 30, 40, 43, 50, 60, 55, 0]
  • 曜日10までの最大生産量【62】と曜日3までの最大生産量【20+B[10-3-1](=B[6]=42)】の大きい方で更新する
    dp[10]=62
    dp = [0, 0, 10, 20, 23, 30, 40, 43, 50, 60, 62, 0]
  • 曜日10までの最大生産量【62】と曜日4までの最大生産量【23+B[10-4-1](=B[5]=34)】の大きい方で更新する
    dp[10]=62
    dp = [0, 0, 10, 20, 23, 30, 40, 43, 50, 60, 62, 0]
  • 曜日10までの最大生産量【62】と曜日5までの最大生産量【30+B[10-5-1](=B[4]=26)】の大きい方で更新する
    dp[10]=62
    dp = [0, 0, 10, 20, 23, 30, 40, 43, 50, 60, 62, 0]
  • 曜日10までの最大生産量【63】と曜日6までの最大生産量【40+B[10-6-1](=B[3]=23)】の大きい方で更新する
    dp[10]=63
    dp = [0, 0, 10, 20, 23, 30, 40, 43, 50, 60, 63, 0]
  • 曜日10までの最大生産量【63】と曜日7までの最大生産量【43+B[10-7-1](=B[2]=20)】の大きい方で更新する
    dp[10]=63
    dp = [0, 0, 10, 20, 23, 30, 40, 43, 50, 60, 63, 0]
  • 曜日10までの最大生産量【63】と曜日8までの最大生産量【50+B[10-8-1](=B[1]=10)】の大きい方で更新する
    dp[10]=63
    dp = [0, 0, 10, 20, 23, 30, 40, 43, 50, 60, 63, 0]
  • 曜日10までの最大生産量【63】と曜日9までの最大生産量【60+B[10-9-1](=B[0]=0)】の大きい方で更新する
    dp[10]=63
    dp = [0, 0, 10, 20, 23, 30, 40, 43, 50, 60, 63, 0]
  • 曜日11までの最大生産量【60】と曜日0までの最大生産量【0+B[11-0-1](=B[10]=60)】の大きい方で更新する
    dp[11]=60
    dp = [0, 0, 10, 20, 23, 30, 40, 43, 50, 60, 63, 60]
  • 曜日11までの最大生産量【60】と曜日1までの最大生産量【0+B[11-1-1](=B[9]=54)】の大きい方で更新する
    dp[11]=60
    dp = [0, 0, 10, 20, 23, 30, 40, 43, 50, 60, 63, 60]
  • 曜日11までの最大生産量【60】と曜日2までの最大生産量【10+B[11-2-1](=B[8]=48)】の大きい方で更新する
    dp[11]=60
    dp = [0, 0, 10, 20, 23, 30, 40, 43, 50, 60, 63, 60]
  • 曜日11までの最大生産量【65】と曜日3までの最大生産量【20+B[11-3-1](=B[7]=45)】の大きい方で更新する
    dp[11]=65
    dp = [0, 0, 10, 20, 23, 30, 40, 43, 50, 60, 63, 65]
  • 曜日11までの最大生産量【65】と曜日4までの最大生産量【23+B[11-4-1](=B[6]=42)】の大きい方で更新する
    dp[11]=65
    dp = [0, 0, 10, 20, 23, 30, 40, 43, 50, 60, 63, 65]
  • 曜日11までの最大生産量【65】と曜日5までの最大生産量【30+B[11-5-1](=B[5]=34)】の大きい方で更新する
    dp[11]=65
    dp = [0, 0, 10, 20, 23, 30, 40, 43, 50, 60, 63, 65]
  • 曜日11までの最大生産量【66】と曜日6までの最大生産量【40+B[11-6-1](=B[4]=26)】の大きい方で更新する
    dp[11]=66
    dp = [0, 0, 10, 20, 23, 30, 40, 43, 50, 60, 63, 66]
  • 曜日11までの最大生産量【66】と曜日7までの最大生産量【43+B[11-7-1](=B[3]=23)】の大きい方で更新する
    dp[11]=66
    dp = [0, 0, 10, 20, 23, 30, 40, 43, 50, 60, 63, 66]
  • 曜日11までの最大生産量【70】と曜日8までの最大生産量【50+B[11-8-1](=B[2]=20)】の大きい方で更新する
    dp[11]=70
    dp = [0, 0, 10, 20, 23, 30, 40, 43, 50, 60, 63, 70]
  • 曜日11までの最大生産量【70】と曜日9までの最大生産量【60+B[11-9-1](=B[1]=10)】の大きい方で更新する
    dp[11]=70
    dp = [0, 0, 10, 20, 23, 30, 40, 43, 50, 60, 63, 70]
  • 曜日11までの最大生産量【70】と曜日10までの最大生産量【63+B[11-10-1](=B[0]=0)】の大きい方で更新する
    dp[11]=70
    dp = [0, 0, 10, 20, 23, 30, 40, 43, 50, 60, 63, 70]

5. 結果を出力する

70

2024年12月20日：追記

ステップ1: 週の構造を理解する

  • 週は4日間 (1, 2, 3, 4) で構成されている。
  • 4日目の後は、また1日目に戻りる。

ステップ2: 休日と平日の割り当て

  • 各日を「休日」か「平日」に割り当てる必要がある。
  • 少なくとも1日は休日にする必要がある。
def generate_assignments(N):
    def backtrack(day, assignment):
        if day == N:
            if 0 in assignment:  # 少なくとも1日は休日（0）
                yield assignment
            return
        
        # 0 = 休日, 1 = 平日
        for work_day in [0, 1]:
            yield from backtrack(day + 1, assignment + [work_day])

    return list(backtrack(0, []))

# 使用例
N = 4
assignments = generate_assignments(N)

print(f"{N}日間の週の全ての有効な割り当て:")
for i, assignment in enumerate(assignments, 1):
    print(f"{i}. {assignment}")
  1. generate_assignments(N) 関数は、N日間の週に対する全ての有効な割り当てを生成する。
  2. 内部の backtrack 関数は再帰的に全ての可能な組み合わせを生成する。
  3. 各日を0（休日）か1（平日）で表現する。
  4. 完全な割り当て（N日分）が生成されたら、少なくとも1つの休日（0）が含まれているかチェックする。
  5. 有効な割り当てのみを yield する。
  6. 最後に、全ての有効な割り当てのリストを返す。

補足1

  • generate_assignments関数は、可能な全ての休日と平日の割り当てを生成する。
  • 動的計画法（DP）を使用して、これらの割り当ての中から最適なものを効率的に見つける。

補足2

generate_assignments関数は全ての可能な割り当てを列挙するため、小さなNに対しては動作する。
しかし、Nが大きくなると計算量が指数関数的に増加します（2^N）。
DPを使用するとO(N^2)の計算量で最適解を見つけられる。

補足3

  • B配列は累積和を計算し、任意の連続した日数の生産量の合計を効率的に取得できるようにしている。
  • dp[i]は、最初のi日間で得られる最大の生産量を表す。
  • DPの遷移では、i日目を休日にするか平日にするかを全ての可能性について試し、最大値を選ぶ。

ステップ3: 生産量の計算方法

  • 休日の生産量は常に0。
  • 平日の生産量は、直前と直後の休日までの距離の短い方によって決まる。

ステップ4: 最適な割り当てを見つける

0
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
0
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?