ABC 312 F — Cans and Openers

考察

缶切りも品物一個分の選択枠を使うので、満足度の高い缶だけを選んでも開けられるとは限らない。そこで、缶切りが不要な缶と、缶切りが必要な缶・缶切りの組とに選択枠を分ける。後者では、開けられる間は価値の高い缶を取り、開けられなくなったときだけ容量の大きい缶切りを追加すると、各枠数での最大満足度を一度の走査で求められる。

以下、缶切りが不要な缶を type0、必要な缶を type1、缶切りを type2 と呼ぶ。type0・type1 の価値は満足度、type2 の容量は開けられる缶の個数である。缶の単品価値だけで上位を選ぶ方針では、缶切りのためにどの缶を何個諦めるかを決められない。まず同種類の品物同士を比較し、選択の自由度を減らそう。

同種類の選択個数を固定すると、缶は満足度が高いものへ交換しても必要な選択枠数は変わらず、缶切りは容量が大きいものへ交換しても開けられる缶を失わない。三種類をそれぞれ降順に並べた配列を A,B,CA,B,C、その要素数を n0,n1,n2n_0,n_1,n_2 とする。配列の添字は1始まりで、各種類では先頭から何個取るかだけを考えればよい。

ここで、品物不足を扱うため、選択個数を「高々」として考える。高々 MM 個を選ぶ最適値は、ちょうど MM 個を選ぶ元の問題の最適値と等しい。実際、N≥MN\geq M なので、足りない個数だけ未選択の品物を追加できる。缶切りや開けない缶は満足度0として追加でき、type0 の満足度も非負なので、既に得た満足度を失わない。

0≤t≤M0\leq t\leq M に対して、type0 に高々 tt 枠を使うときの最大満足度を P[t]P[t] と置く。初期値は P[0]=0P[0]=0 で、

P[t]=∑i=1min⁡(t,n0)AiP[t]=\sum_{i=1}^{\min(t,n_0)} A_i

である。type0 が尽きたら末尾の値をそのまま延長する。したがって P[t]P[t] は、実在する缶の個数を超える添字でも定義される。

同様に、type1 と type2 に合わせて高々 ss 枠を使うときの最大満足度を Q[s]Q[s] と置く。開けない type1 は価値0なので、この側の最適値を求める間は選ばずに済む。Q[s]Q[s] を求めるには、これまで選んだ缶切りでまだ開けられる缶の個数 capacity に注目する。

  • capacity > 0 で type1 が残っているなら、次の type1 を取る。開封の準備は既にできているので、満足度を直ちに増やせる。追加の缶切りを先に取る必要はない。
  • capacity = 0 で type1 が残っているなら、次の type2 を取る。より多くの缶を開けられるものほど、以後の選択を妨げない。

前者で缶を先に選べる理由を、固定した枠数の最適解から考える。既に選んだ品物を含む最適解が次の缶を含まないとする。そこに別の未確定の缶があれば、最大満足度の次の缶へ交換できる。未確定の缶がなく追加の缶切りだけがあれば、その一個を次の缶へ交換できる。既に確保した容量だけでこの缶まで開けられるため、満足度は下がらない。選択枠が余っていれば、そのまま缶を追加できる。こうして、使える容量がある間は缶を先に確定してよい。

具体的には Q[0]=0Q[0]=0、capacity = 0、B,CB,C の未使用先頭を指す添字 b=c=1b=c=1 から始め、s=1,…,Ms=1,\ldots,M の順に次を行う。

  1. まず Q[s]=Q[s−1]Q[s]=Q[s-1] とする。
  2. b>n1b>n_1 なら値を変えずに進む。缶が残っていないので追加の缶切りは不要である。
  3. そうでなく capacity > 0 なら、BbB_b を Q[s]Q[s] に加え、bb を1増やし、capacity を1減らす。
  4. そうでなく c≤n2c\leq n_2 なら、CcC_c を capacity に加え、cc を1増やす。缶切りにも一枠を使うので、この回には缶を取らず、満足度は増えない。
  5. capacity = 0 で未使用の缶切りも残っていなければ、以後も値を変えない。開けられない缶を選んでも満足度は増えない。

例えば B=(9,5),C=(3)B=(9,5), C=(3) なら、Q[0],…,Q[5]Q[0],\ldots,Q[5] は 0,0,9,14,14,140,0,9,14,14,14 となる。一枠目で最後の缶切りを選んでも、開封容量は3残っているので、二枠目・三枠目では缶を選んで満足度を増やせる。三枠を使った後は缶が尽きるため、容量が1余っても、それ以降の値は14のままである。最後の二枠では、実際に品物を追加したと解釈する必要はない。

最後に、type1・type2 側へ渡す枠数 ss をすべて試し、

max⁡0≤s≤M(P[M−s]+Q[s])\max_{0\leq s\leq M}\bigl(P[M-s]+Q[s]\bigr)

を答えとする。二つの配列はともに「高々その枠数での最適値」なので、どちらかの品物が足りなくても同じ式で評価できる。

典型の発動条件

種類別 sort と個数固定

発動条件: 同種類の品を一対一で交換しても必要な枠数が変わらず、価値または能力の大きい品へ替えても他の選択を妨げないとき。

種類ごとに降順の先頭部分へ圧縮し、残った種類間の枠の配分を探索する。品物が不足する場合は、配列の添字が「ちょうど選ぶ個数」か「使ってよい枠数」かを区別する。

resource 解禁型の貪欲

発動条件: 報酬品には容量が必要で、容量を与える補助品も同じ選択枠を消費するとき。

利用可能な容量があるなら報酬品を先に取れることと、容量不足なら最大容量の補助品を選んでよいことを別々に示す。この二つの交換が成立すれば、一方向に選択を伸ばして各枠数の最適値を作れる。

問題固有の要素

開封容量が余ることと、選択枠が余ることは異なる。缶切り一個で何缶でも選べるわけではなく、選ぶ缶にも一枠ずつ必要である。type1・type2 側では、type1 が尽きた場合、または capacity = 0 で未使用の type2 も尽きた場合に、以後の選択枠を増やしても満足度は増えない。未使用の type2 が尽きても、開封容量と type1 が残っていれば、枠を増やして缶を選び、満足度を増やせる。

「高々」の最適値へ緩められる理由は、余った選択枠を無価値の品物でも埋められる点にある。ちょうどの個数が要求される別問題へ持ち帰る際は、追加できる品物の数と、追加して目的値が悪化しないことを確認する。

正当性

種類内の交換により、type0 は満足度降順の先頭から選べばよく、品物が尽きた後も P[t]P[t] は高々 tt 枠の最適値を表す。

type1・type2 側について、任意の上限 ss を固定する。満足度に寄与しない未開封缶は取り除けるので、選んだ缶をすべて開ける最適解を考えてよい。貪欲法が選んだ品物を含む最適解が存在することを、選択を進めながら保つ。容量が正で缶が残る場合は、考察で示した交換または追加により、次の最大満足度の缶を含む最適解へ移れる。

容量が0の場合、まだ選択枠が残っていても、現在の品物だけでは新たな缶を開けられない。最適解がこの先に缶を選んで満足度を増やすなら、未選択の缶切りを少なくとも一個含む。その缶切りを未選択の最大容量のものへ交換しても、選択枠数は変わらず開封能力は下がらない。最適値が既に達成されている場合も、一枠を使って缶切りを追加してよい。よって、この選択を含む最適解が存在する。缶が尽きた場合、または容量0で缶切りが尽きた場合は、これ以上満足度を増やせない。以後の値を据え置けば、すべての 0≤s≤M0\leq s\leq M で Q[s]Q[s] が求まる。

各 P[M−s]+Q[s]P[M-s]+Q[s] は、異なる種類の品物を合わせて高々 MM 個選ぶことで実現できる。一方、任意の高々 MM 個の選び方で、type1・type2 の選択個数を ss とすれば、満足度はこの和以下になる。従って全 ss での最大値が高々 MM 個の最適値であり、未選択品の追加によりちょうど MM 個へ拡張できるので、元の問題の答えでもある。

実装上の注意

  • P,QP,Q は長さ M+1M+1 で作り、初期値をともに0とする。各側でこれ以上満足度を増やせなくなっても、配列の構築を打ち切らず、直前の値を末尾までコピーする。
  • type1 がなければ Q[s]=0Q[s]=0 が続く。type2 がなければ、type1 があっても Q[s]=0Q[s]=0 が続く。公式サンプル2は全品が type1、M=N=5M=N=5 なので、P,QP,Q がともに全要素0となり、答えも0である。
  • type0 が不足しても P[t]P[t] の値を延長する。M=NM=N や容量余りにも同じ手順を使い、実際には選んでいない品物を配列外から参照しない。
  • 缶切りを追加した回も一枠を使う。capacity は選択可能な残り品数ではなく、まだ開けられる缶数である。
  • 満足度の合計には64 bit整数を使う。上限は Nmax⁡iXi≤2×1014N\max_i X_i\leq 2\times10^{14} であり、32 bit整数には収まらない。

復習の核

  • 補助品も選択枠を使うときは、種類内の支配関係と種類間の枠配分を分けて考える。
  • 貪欲では「次の選択を含む最適解へ交換できるか」を問う。容量が余っているときと不足しているときでは、交換する対象が異なる。
  • 添字を「使ってよい枠数」と定義すれば、品物枯渇後も最適値を延長できる。「ちょうど」の問題へ戻すには、余った枠を悪化なく埋められる根拠が必要である。

計算量と制約

時間

三種類のソートに合計 O(Nlog⁡N)O(N\log N) 時間、P,QP,Q の構築と枠配分の全列挙に O(M)O(M) 時間を使う。M≤NM\leq N より、全体で O(Nlog⁡N)O(N\log N) 時間。

空間

三種類の配列に合計 O(N)O(N)、最適値の配列 P,QP,Q に O(M)O(M) を使い、全体で O(N)O(N) 空間。

制約との対応

公式制約は 1≤M≤N≤2×1051\leq M\leq N\leq 2\times10^5、Ti∈{0,1,2}T_i\in\{0,1,2\}、1≤Xi≤1091\leq X_i\leq10^9 で、入力はすべて整数である。この規模では部分集合の全探索は使えないが、ソート後に各品物を高々一度選ぶ上記の手順なら処理できる。満足度が非負であることは、「高々」の解をちょうど MM 個へ拡張する際にも使っている。

出典

分類・前提・執筆情報

掲載状態: 収録済み

Cans and Openers の公式問題ページ(外部リンク)

最終確認:

学習上の位置付け

主題の単元: 交換論から選択順を導く

主題
追加で学ぶ技能
    なし
    既習技能
      なし

      主タグ: 貪欲法と交換論

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

      学習の位置

      体系上の位置: 交換論から選択順を導く

      • 局所選択の交換または候補の支配関係を示し、安全な順序・候補・caseを確定できる。

      この解説で扱わないこと:

      • 対称操作による状態の正規化。

      学習記録

      状況更新: 更新記録なし

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

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

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

      同じ単元の問題