ABC 363 G — Dynamic Scheduling

考察

更新のたびに仕事を選び直す代わりに、仕事を一つ追加したときの最適集合の変化を考える。追加だけなら、「そのまま採用」「選択済みの一仕事と交換」「棄却」の三通りで最適報酬を保てる。さらに各仕事の有効期間を時間方向に分割すれば、入力の変更を追加とその取り消しだけに変換できる。

まず、更新のない場合を理解する。報酬を得る仕事だけを選び、それらを期限内の日へ割り当てればよい。残りの仕事は空いた日に行えばよく、期限内に終わる仕事の報酬はすべて正なので、最大化では期限内に実行できる集合の最大報酬を求めれば十分である。毎回、期限順の貪欲法をやり直すと、全仕事を調べるだけでも O(NQ)O(NQ) かかる。以下では、選択済み集合が満たす条件を式にして、一仕事分の変化を扱う。

期限までの空き枠を数える

期限内に実行する集合を XX とする。期限が tt 以下の仕事は、いずれも最初の tt 日に収めなければならない。従って、余裕を

f(t)=t−∣{i∈X∣Di≤t}∣(1≤t≤N)f(t)=t-\bigl|\{i\in X\mid D_i\leq t\}\bigr|\qquad(1\leq t\leq N)

と置くと、すべての f(t)f(t) が非負であることが必要になる。これは十分条件でもある。選んだ仕事を期限の昇順に並べ、kk 番目を kk 日目に行う。もしその期限 dkd_k が kk 未満なら、期限 dkd_k 以下の仕事が少なくとも k>dkk>d_k 個あるため条件に反する。従って全仕事を期限内に終えられる。

この条件は、仕事と実行日の二部マッチングに対する Hall 条件を、入れ子になった期限の範囲へ絞った形でもある。ここでは具体的な割当で必要十分性を確認できたので、以後は日ごとの割当自体を持たず、余裕だけを管理する。

期限 DD の仕事を採用すると、t≥Dt\geq D の個数だけが一つ増える。従って f(D),…,f(N)f(D),\ldots,f(N) へ −1-1 を加算する。選択から外す操作は同じ範囲への +1+1 である。区間加算と区間最小値を扱う遅延セグメント木が、この変化に合っている。

最初に埋まる期限が交換候補を決める

ここからは、これまで挿入した全仕事に対して XX が最大報酬の集合であるとする。新仕事 e=(D,P)e=(D,P) を入れる前に、区間 [D,N][D,N] で余裕が初めてゼロになる位置を探す。見つかればそれを t∗t^* とする。

  • ゼロがなければ、この範囲の余裕は整数で少なくとも1ある。そのまま ee を採用できる。
  • ゼロがあれば、採用した直後の f(t∗)f(t^*) は −1-1 になる。これを直すには、期限が t∗t^* 以下の選択済み仕事を一つ外す必要がある。

後者では、この条件がほかの期限の違反もすべて直す。挿入で負になるのは、挿入前に t≥Dt\geq D かつ f(t)=0f(t)=0 だった位置だけである。それらはすべて t∗t^* 以上にあり、期限が t∗t^* 以下の仕事を外すと、その全位置に +1+1 が入る。もともと正の余裕は挿入後も非負であり、DD 未満では余裕が増えるだけである。

従って、交換できる仕事は正確に「XX のうち期限が t∗t^* 以下のもの」。その中で最小の報酬を pmin⁡p_{\min} とすると、P>pmin⁡P>p_{\min} の場合だけその一仕事と交換する。同報酬なら現在の集合を保ち、ee を棄却する。ここまでで交換後の実行可能性は分かるが、複数仕事を選び直すとさらに報酬が増えないかは別の問題である。一回の交換で最適性まで保てる理由は「正当性」で示す。

小さく追ってみよう。N=6N=6 とし、表の順に六仕事を挿入する。各仕事は「期限、報酬」で表す。採用集合の括弧内は総報酬である。

新仕事操作採用集合(報酬和)
初期状態空集合なし(0)
a=(2,5)a=(2,5)採用aa(5)
b=(1,7)b=(1,7)採用a,ba,b(12)
c=(2,4)c=(2,4)棄却a,ba,b(12)
d=(2,9)d=(2,9)aa と交換b,db,d(16)
e=(3,2)e=(3,2)採用b,d,eb,d,e(18)
f=(1,6)f=(1,6)棄却b,d,eb,d,e(18)

最初の3日分の余裕は、初期状態の (1,2,3)(1,2,3) から、aa の採用で (1,1,2)(1,1,2)、bb の採用で (0,0,1)(0,0,1) になる。次の cc と dd はともに期限2なので、追加前の最初のゼロは t∗=2t^*=2、候補は a,ba,b である。最小報酬は aa の5。cc の報酬4では増えないため棄却し、dd の報酬9では aa と交換する。期限が同じ仕事同士の交換なので余裕は変わらない。

ee の期限3以後にはまだ余裕があるため、そのまま採用できる。余裕は (0,0,0)(0,0,0) になる。最後の ff は期限1で、t∗=1t^*=1、候補は bb だけである。報酬6は bb の7より低いので棄却する。

最後の行では、集合全体の最小報酬は ee の2だが、これを外しても1日目の不足は直らない。報酬だけで最小を探さず、まず交換できる期限の範囲を絞る必要がある。

余裕の木と、期限別の最小報酬を組み合わせる

選択集合を更新するために、次を持つ。ここで版とは、ある仕事が更新されるまで同じ期限・報酬を持つ期間であり、各版に固有IDを付ける。

  • 余裕の木: 葉 tt に f(t)f(t) を置く。区間加算・最小値と、[D,N][D,N] の最初のゼロを探索する。初期値は f(t)=tf(t)=t。
  • 期限別の集合: 期限 dd ごとに、選択中の仕事の組「報酬、版ID」を昇順に保持する multiset を置く。初期状態はすべて空。同報酬でも版IDが違えば別要素として残す。
  • 報酬の木: 葉 dd に、その期限の集合の最小の組を置く。空なら無限大を置く。[1,t∗][1,t^*] の最小値を取ると、交換する仕事とその報酬が分かる。
  • 総報酬 SS: 選択中の仕事の報酬和。初期値は0で、葉時刻での答えになる。

余裕は挿入前には非負なので、最小値が正の区間にゼロはない。DD 未満と最小値が正の区間を除外し、左の子から探索すれば最初のゼロを O(log⁡(N+1))O(\log(N+1)) で見つけられる。遅延加算は探索中も考慮する。二分探索の各点で区間最小値を問い合わせる必要はない。

採用では、余裕の接尾区間へ −1-1 を加え、期限別集合へ新仕事を入れ、その期限の報酬の木を更新して、SS に報酬を加える。交換では、まず旧仕事を外す操作(接尾区間へ +1+1、集合から削除、報酬の木を更新、SS から減算)を行い、その後に新仕事を採用する。棄却ならどれも変更しない。

入力の変更を、版の有効区間に直す

オンラインで仕事を削除すると、それまで棄却していた別の仕事を復活させる必要がある。挿入時の交換則だけではこの削除を処理できない。一方、クエリはすべて先に読めるので、各版が有効な時刻区間を求め、時間セグメント木で追加と取り消しへ変える。

葉時刻 qq は、0始まりのクエリ qq を適用した直後とする。葉は 0,…,Q−10,\ldots,Q-1 の QQ 個である。各仕事について、初期版の開始時刻を0としておく。時刻 qq にその仕事を更新したら、旧版の区間を [l,q)[l,q) で閉じ、新版の開始を qq にする。最後まで残る版は [l,Q)[l,Q) で閉じる。空区間は登録しない。

例えば Q=4Q=4 で、ある仕事を時刻1と2に連続して更新すると、初期版は [0,1)[0,1)、次の版は [1,2)[1,2)、最後の版は [2,4)[2,4) に存在する。時刻0に更新する仕事の初期版は [0,0)[0,0) となり、一度も有効でない。Q=1Q=1 でも、更新後の版だけが唯一の葉に届く。

各区間を時間セグメント木の標準的な区間分解でノードへ登録し、根から DFS する。ノードに入ったら登録された版を順に挿入し、葉なら SS を出力する。退場時には入場前へ戻す。このとき「その枝で扱う全仕事」と「報酬を得るために選択した集合 XX」は異なる。棄却した版を選択集合へ入れ直す必要がないのは、枝を戻る際に、交換も含めて挿入前の最適集合そのものを復元するからである。

典型の発動条件

時間segment treeとrollback

一点変更をオフラインで扱え、要素の追加は速いが任意削除は難しいときに使う。要素の有効区間を時間の木へ載せると、任意削除を直前の変更の取り消しに変えられる。兄弟の区間へ進む前に、答えに関係するすべての補助構造を復元できることが条件である。

Hall条件のprefix slack管理

一仕事が単位時間で、実行できる日が1日目から期限までの接頭区間であるとき、実行可能性を各期限までの個数と容量の比較へ圧縮できる。仕事の増減は余裕への接尾区間加算になる。開始可能日も指定されるなど、実行できる日の集合が入れ子でなければ、この条件だけでは十分でなくなる。

問題固有の要素

交換可能性を決めるのは、追加前に見つかる最初の余裕ゼロの期限である。期限の範囲で候補を絞ってから報酬を最小化することで、実行可能性と目的関数を分けて処理できる。

個別公式解説は、費用流の負閉路を高々一回解消すればよいことから交換則を導く。本稿では同じ交換則を、次節の二つの割当の比較で証明する。期限順による条件の導出、交換候補の具体化、復元手順もここで補っている。

正当性

交換できる範囲と、報酬の最適性を分ける

期限順の割当で示した通り、全余裕が非負であることが実行可能性の必要十分条件である。また、追加前の [D,N][D,N] に最初のゼロ t∗t^* がある場合、選択済みの一仕事 jj を外して新仕事 ee を入れられる必要十分条件は Dj≤t∗D_j\leq t^* である。必要性は t∗t^* の不足から、十分性はそれ以後の全不足を同時に直せることから従う。従って報酬の木は、一回交換の中で最良の候補を返す。

残る核心は、旧集合 XX が最適なら、新仕事を追加した後の最適値は、何もしない・単純追加・一回交換のいずれかで達成できることである。これを次の割当の比較で示す。

仕事と日を二部グラフの頂点とし、期限内に実行できる組に辺を張る。XX を実行するマッチングを MM とする。新仕事 ee を含む任意の実行可能集合 YY を取り、そのマッチングを M′M' とする。両者の共通辺を除いて重ねると、各頂点の次数は高々2で、MM の辺と M′M' の辺が交互に現れる道と閉路に分かれる。

ee は M′M' だけで使われるため、そこから始まる成分は一本の道である。道に沿って MM の辺を M′M' の辺へ入れ替えてもマッチングを保つ。途中の仕事は実行日が変わるだけで、選択されるかどうかは変わらない。もう一方の端点は次のどちらかになる。

  • MM では空いていた日。この成分だけ入れ替えると、XX に ee が加わる。
  • MM だけで使われる仕事 jj。この成分だけ入れ替えると、XX から jj を外して ee が加わる。

ほかの各成分も、単独で辺を入れ替えて実行可能な割当を作れる。しかしそこには新仕事がないので、報酬を増やす成分があれば、旧入力に対する XX の最適性に反する。従って、それらの報酬差はすべて非正である。YY の報酬増分は、ee の成分だけを入れ替えた増分以下になる。ee を含まない集合も旧最適値を超えないので、上記三通りから最良を選べば新しい最適値を得られる。

単純追加できる場合の増分は PP。全報酬が正なので、仕事を一つ外す交換の増分より大きい。単純追加できない場合の最大増分は、交換可能な仕事の最小報酬を使った P−pmin⁡P-p_{\min} であり、それが正のときだけ交換すればよい。等しければ棄却しても最適値は同じである。これで挿入順によらず最適報酬を保てる。

各葉の入力と復元の対応

一版の有効半開区間を互いに重ならないノード区間へ分けると、その区間に含まれる葉では、根からの経路上にその版がちょうど一回現れる。含まれない葉の経路には現れない。さらに同じ仕事の各版の区間は重複しないので、葉の経路に現れる全版は、ちょうどそのクエリを適用した直後の入力である。

空集合は最適であり、一挿入ごとに上の交換則が最適性を保つ。退場時に、余裕の木・期限別集合・報酬の木・総報酬をすべて入場前へ復元すれば、兄弟の探索も同じ前提から始まる。従って各葉で出力する SS は、その更新後入力に対する最適報酬である。

実装上の注意

変更前の値を保存して完全に戻す

履歴スタックを一本用意し、ノード入場時の長さを h とする。以下の実装方針では、木の配列の変更前の値も記録する。問い合わせは祖先の遅延値を引き継いで読み、木を書き換えないようにする。

変更するもの変更直前に積む記録取り消し
余裕の木ノード番号、旧最小値、旧遅延加算値そのノードの両値を旧値へ戻す
期限別集合への挿入期限と挿入した組「報酬、版ID」その組だけを削除する
期限別集合からの削除期限と削除した組「報酬、版ID」その組を再挿入する
報酬の木書き換えるノード番号と旧最小の組旧値へ戻す
総報酬旧値旧値へ戻す

余裕の木の遅延値を子へ押し下げるときは、子の値の変更だけでなく、親の遅延値を消す変更も記録する。同じノードを何度書き換えても、その都度、変更前を積めばよい。選択中かどうかの配列を別途持つなら、その変更も記録する。

例えば交換では、「旧仕事の接尾加算、旧組の削除、報酬の木の更新、総報酬の減算」に続けて「新仕事の接尾加算、新組の挿入、報酬の木の更新、総報酬の加算」を行う。取り消しでは、この全記録を逆順にたどる。新仕事側の総報酬、報酬の木、集合、余裕を戻してから、旧仕事側の変更も戻す。復元中は通常の更新関数で新たな履歴を積まず、記録の旧値を直接代入し、集合の逆操作を行う。

子の探索も終えたら、長さが h になるまで記録を取り出す。親ノードの途中で棄却した仕事、交換で追い出した仕事も含めて、入場時の状態へ戻る。問い合わせで変更せず、棄却時にも何も書き換えない方針なら、棄却の記録は不要である。ノードごとの checkpoint まで戻す規約と、一挿入につき一記録を取り消す規約を混ぜない。

報酬が同じ仕事も個別の版IDで消す。報酬値をキーに erase して同報酬の全仕事を削除してはならない。報酬の木の無限大は有効な報酬より大きくし、候補の版IDから期限も取り出せるようにしておく。総報酬は最大 101410^{14} なので64 bit整数を使う。

復習の核

  • 動的な選択問題では、まず静的な実行可能性を容量の式にする。単位時間と入れ子の期限が、個数の条件を必要十分にしている。
  • 「違反を直せる」と「報酬まで最適」は別々に証明する。最初の不足で交換範囲を絞り、二つの割当の交互の道で一回交換が十分な理由を押さえる。
  • 任意削除で棄却済み要素の復活が難しければ、有効期間を時間の木へ分ける。戻すのは最後に追加した仕事だけでなく、その追加が引き起こした交換と全補助構造である。
  • 葉が更新前か更新後かを先に固定する。同じ仕事の連続更新と、最初のクエリで消える初期版を半開区間で確かめる。

計算量と制約

時間

LN=log⁡2(N+1)L_N=\log_2(N+1)、LQ=log⁡2(Q+1)L_Q=\log_2(Q+1) と置く。各仕事の初期版が NN 個、更新で作る版が QQ 個あり、空区間を除いた版数も高々 N+QN+Q である。一版を高々 O(LQ)O(L_Q) 個の時間ノードへ登録するので、登録総数を RR とすると R=O((N+Q)LQ)R=O((N+Q)L_Q) となる。

入力と区間の準備に O(N+Q)O(N+Q)、二つの木の初期化に O(N)O(N)、区間分解するノードの探索と登録に O((N+Q)LQ)O((N+Q)L_Q)、時間の木の走査・出力に O(Q)O(Q) かかる。各登録に対応する挿入では、最初のゼロの探索、報酬の区間最小、定数回の接尾加算・集合操作・点更新を行い、O(LN)O(L_N) 時間かかる。積む履歴も O(LN)O(L_N) 件で、集合の逆操作を含む復元も O(LN)O(L_N) 時間である。全体は

O((N+Q)log⁡(Q+1)log⁡(N+1))O\bigl((N+Q)\log(Q+1)\log(N+1)\bigr)

時間となる。N=1N=1 や Q=1Q=1 でも定数時間の処理が消えないよう、対数には +1+1 を付けている。

空間

入力・版の情報に O(N+Q)O(N+Q)、時間の木に O(Q+R)O(Q+R)、余裕の木・報酬の木・期限別集合に O(N)O(N) を使う。

履歴は、DFS 全体で発生したものを残し続けるのではなく、現在の根からの経路で発生したものだけを保持する。その経路で挿入する版は同じ仕事ごとに高々一つで、全部で高々 NN 個である。採用・交換の各挿入で木の旧値を O(LN)O(L_N) 件保存するため、現在の履歴は O(NLN)O(NL_N) 件。従って本稿の記録方式での全体空間は

O((N+Q)log⁡(Q+1)+Nlog⁡(N+1))O\bigl((N+Q)\log(Q+1)+N\log(N+1)\bigr)

である。論理的な採用・交換だけを記録して木を逆更新する方式とは、履歴の大きさが異なる。旧値を保存する方式に、木の履歴を含めない空間評価を流用しない。

制約との対応

公式問題では 1≤N,Q≤1051\leq N,Q\leq 10^5、1≤Di,x,c≤N1\leq D_i,x,c\leq N、1≤Pi,y≤1091\leq P_i,y\leq 10^9、制限は8秒・1024 MiBである。毎回全仕事を調べる方法から、各版につき時間の木と期限の木の対数回の処理へ減らせる。登録は版ID、履歴は変更先と旧値に絞って保持し、各ノードで配列全体をコピーしない。報酬が正、期限が1以上、所要時間が一日であることを、追加の優先・実行可能性・交換則に使っている。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Dynamic Scheduling の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: rollback・DFS入退場の状態復元

主題
  • rollback・DFS入退場の状態復元: 更新前の差分をstackへ記録し、分割統治・時間Segment Tree・DFSの退場時に状態を正確に巻き戻す。その発動条件、正当性、計算量を説明し、未知問へ実装できる。
追加で学ぶ技能
    なし
    既習技能
    • 二部matching・Hall・Kőnig: 二部割当が可能であることを近傍集合の大きさに関するHall条件で特徴付け、必要ならmin-cut条件と対応させられる。
    • Segment Treeのcanonical区間分解: 区間をO(log N)個のcanonical nodeへ分解してrange object・時間生存区間・range edgeを配置し、point queryではroot-to-leaf path上のobjectを集められる。
    • 区間更新を要約へ作用させる: 更新作用の合成順と要約への適用を定義し、遅延評価で保てる。

    主タグ: rollback・DFS入退場の状態復元

    補助タグ: 二部matching・Hall・Kőnig 遅延評価する区間作用 Segment Treeのcanonical区間分解

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

    学習の位置

    体系上の位置: rollback・DFS入退場の状態復元

    • 更新前の差分をstackへ記録し、分割統治・時間Segment Tree・DFSの退場時に状態を正確に巻き戻す。その発動条件、正当性、計算量を説明し、未知問へ実装できる。

    先に読む単元:

    • 二部matching・Hall・Kőnig — 二部グラフの彩色と成分構造で得た考え方と実装を再利用し、二部matching・Hall・Kőnigの発動条件・正当化・境界を重複なく学ぶ。
    • 区間更新を要約へ作用させる — 結合的な区間要約を設計した後、更新作用の合成順と要約への適用を遅延評価する。
    • Segment Treeのcanonical区間分解 — 区間monoid要約で得た考え方と実装を再利用し、Segment Treeのcanonical区間分解の発動条件・正当化・境界を重複なく学ぶ。

    学習記録

    状況更新: 更新記録なし

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

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

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

    同じ単元の問題