ABC 285 E — Work or Rest

考察

曜日は円環だが休日を少なくとも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

出典

分類・前提・執筆情報

掲載状態: 収録済み

Work or Rest の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: prefix分割DP

主題
  • prefix分割DP: 列の最後のブロックを固定し、処理済みprefixの答えから次の切れ目へ遷移する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: prefix分割DP

      執筆: abc-explanation-author1.1.1 / revision 1

      学習の位置

      体系上の位置: prefix分割DP

      • 列の最後のブロックを固定し、処理済みprefixの答えから次の切れ目へ遷移する。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

      先に読む単元:

      学習記録

      状況更新: 更新記録なし

      復習設定更新: 更新記録なし

      端末内の保存状態を確認しています。

      要復習一覧 / 学習記録のバックアップ / 解説に戻る

      同じ単元の問題