考察
曜日は円環だが休日を少なくとも1つ置くので、回転対称性を使って曜日1を休日に固定してよい。
2つの休日の間に平日がd日連続すると、その区間の生産量はB_d=Σ_{k=1..d} A_{floor((k+1)/2)}だけで決まり、他の区間と独立に加算できる。
採用する候補: 曜日1を休日に固定し、処理済み位置と直前の休日から続く平日数を状態にしたDPを行う。
円環の境界を最後の区間へのB加算だけに閉じ込め、休日で区間を閉じるたびに利益を確定できる。
棄却する候補: 休日のsubsetを全列挙して各曜日の最寄り休日を調べる。
候補が2^N通りあり、N≤5000では扱えない。
棄却する候補: 線形列として両端を独立に処理する。
週の末尾と先頭を跨ぐ最寄り休日を無視し、円環上の生産量を誤る。
長さdの平日列では両端から距離1の曜日が2つ、距離2が2つと並ぶため、B_dはA_1,A_1,A_2,A_2,…のprefix sumで前計算できる。
新しい休日を置く遷移で直前の平日列B_jを加え、最後に残った平日列も固定した曜日1の休日へ接続してB_jを加える。
B_0=0とし、d≥1についてB_d=B_{d-1}+A_{floor((d+1)/2)}を前計算する。dp[i][j]を曜日iまで決めて末尾に平日がj日続く最大値とし、dp[1][0]=0から、次を平日にするdp[i+1][j+1]、休日にしてdp[i+1][0]へdp[i][j]+B_jを遷移する。全曜日後にmax_j(dp[N][j]+B_j)を答える。
典型の発動条件
円環の基準点固定
発動条件: 円環上に必ず存在する特別な要素があり、回転で位置を固定できるとき。
休日1つを曜日1へ固定し、跨ぎ区間だけを終端処理する。
区間寄与DP
発動条件: 選んだseparator間の寄与が区間長だけで決まるとき。
休日をseparatorとして平日列を閉じるたびB_jを加算する。
問題固有の要素
各平日の価値は左右の休日までの短い方の距離なので、休日間の配置詳細は平日列長dだけへ圧縮される。
別の問題へ持ち帰る視点: 局所価値が左右の境界までの距離で決まる問題では、境界を選ぶDPとgap長の前計算へ分離する。
正当性
休日が一つ以上ある円環では、隣接休日の間が独立な平日runへ分かれる。長さdのrunの生産性は両端の近い休日までの距離からA_1,A_1,A_2,A_2,…の最初d項の和B_dになる。回転して曜日1を休日と固定しても、生産性が曜日名によらないので最適値は変わらない。新休日を置く際に直前runのBを確定し、最後のrunを曜日1へ閉じれば全曜日の寄与が一回ずつ入る。末尾run長だけを持つ最大化DPが全休日集合を覆う。
実装上の注意
- 不可能状態は十分小さい値で初期化し、A_iの和が32bitを超えるため64bit整数を使う。
- 曜日1は休日として固定済みなので、その生産量を加えず、最後のB_jで週跨ぎ区間を一度だけ精算する。
復習の核
- 休日間に平日が1〜5日ある場合のB列を手で並べ、DPで途中のgapと最終gapがそれぞれ一度だけ加算されるかを追う。
計算量と制約
時間
O(N²)、曜日×末尾平日run長。
空間
O(N)、rolling DPとrun利益B。
制約との対応
公式制約の確認範囲: Time limit: 2 sec; Memory limit: 1024 MiB; Constraints: All values in the input are integers.; 1 \le N \le 5000; 1 \le A_i \le 10^9
出典