大和証券プログラミングコンテスト2024（AtCoder Beginner Contest 383）E,F,G問題メモ

大和証券プログラミングコンテスト2024（AtCoder Beginner Contest 383）

E - Sum of Max Matching

• 頂点に $1$ から $N$ の番号が、辺に $1$ から $M$ の番号が付いた $N$ 頂点 $M$ 辺の重み付き単純連結無向グラフが与えられます。辺 $i$ $(1 \leq i \leq M)$ は頂点 $u_i$ と頂点 $v_i$ を双方向に結び、重みは $w_i$ です。
• あるパスに対してその重みをそのパスに含まれる辺の重みの最大値とします。
• また、$f(x,y)$ を 頂点 $x$ から頂点 $y$ へのパスの重みとしてありえる最小値とします。
• 長さ $K$ の数列　$(A_1,A_2,\ldots,A_K)$ と $(B_1,B_2,\ldots,B_K)$ が与えられます。ここで、$A_i \neq B_j$ $(1 \leq i,j \leq K)$ が成り立つことが保証されます。
• 数列 $B$ を自由に並べ替えて、$\displaystyle\sum_{i=1}^{K}f(A_i,B_i)$ を最小化してください。

• $2 \leq N \leq 2 \times 10^5$
• $N-1 \leq M \leq \min(\frac{N \times (N-1)}{2},2 \times 10^5)$
• $1 \leq K \leq N$
• $1 \leq u_i \lt v_i \leq N$ $(1 \leq i \leq M)$
• $1 \leq w_i \leq 10^9$
• $1 \leq A_i,B_i \leq N$ $(1 \leq i \leq K)$
• $A_i \neq B_j$ $(1 \leq i,j \leq K)$
• 与えられるグラフは単純かつ連結
• 入力は全て整数

$(u,v)$ 間パスのコストが「通る辺の重みの最大値」で定義される問題は、 最初、全頂点がバラバラの状態から、重みが小さい辺から繋いでいき、連結になったら最後に繋いだ辺のコスト、 という解法がよくある。

本問題では、これをまとめておこなう。

まず確認すべき事として、$A,B$ 内でまだペアにならず残っている $A_i,B_j$ が、ある辺を繋いだときに連結になったら、 これを貪欲にペアにしてよい（今繋いだ辺を、1つのペアのコストとして確定させてよい）。

• Astral_氏による貪欲の証明

UnionFindで「具体的に連結となっている頂点グループ」を管理するのは、マージテクで全体 $O(N \log{N})$ でおこなえる。

今回は、率直な頂点グループではなく、 「① $A$ で残っている頂点グループ」「② $B$ で残っている頂点グループ」をそれぞれ管理しておく。

ある重さ $w$ の辺で連結成分がマージされたとき、同じ連結成分内の①と②にともに要素が存在すれば、 どちらかの要素がなくなるまで貪欲にペアにし、答えに $w$ を加算することを繰り返せば良い。

Python3

F - Diversity

• 店で $N$ 個の商品が売られています。 $i$ 個目の商品の価格は $P_i$ 円、効用は $U_i$ 、色は $C_i$ です。
• あなたは、これらの $N$ 個の商品から何個か( $0$ 個でもよい)を選んで購入します。
• このとき、購入した品物の合計価格は $X$ 円以下でなければなりません。
• あなたの満足度は、購入した商品の効用の合計を $S$、購入した商品の色の種類数を $T$ としたとき、$S+T \times K$ です。
  • ここで、$K$ は入力で与えられる定数です。
• あなたの満足度を最大化するように購入する商品を選んだとき、満足度を求めてください。

• $1 \leq N \leq 500$
• $1 \leq X \leq 50000$
• $1 \leq K \leq 10^9$
• $1 \leq P_i \leq X$ $(1 \leq i \leq N)$
• $1 \leq U_i \leq 10^9$ $(1 \leq i \leq N)$
• $1 \leq C_i \leq N$ $(1 \leq i \leq N)$
• 入力は全て整数

色ごとにまとめて更新する。

色 $C_i$ のアイテムで更新するとき、ナップサックDPの更新元を 「まだ $C_i$ を使っていないテーブル」「もう $C_i$ を使ったテーブル」2つから遷移させればよい。

「まだ $C_i$ を使っていないテーブル」からの遷移時のみ、追加で $K$ の満足度がもらえる。

Python3

G - Bar Cover

• $N$ 個のマスが横一列に並んでいて、左から $i$ 番目のマスには整数 $A_i$ が書かれています。
• また、あなたは連続するマス $K$ 個を覆えるタイルを $\lfloor \frac{N}{K}\rfloor$ 枚持っています。
• $i=1,\ldots,\lfloor \frac{N}{K}\rfloor$ について以下の問題を解いてください。
  • タイルを重ならずにちょうど $i$ 個置くとき、タイルで覆われたマスに書かれた数の和としてありうる値の最大値を求めよ。

• $1\leq N\leq 2\times 10^5$
• $1\leq K \leq \min(5,N)$
• $-10^9\leq A_i\leq 10^9$
• 入力される数値は全て整数

一度覆われた区間は、枚数を増やしてもずっと覆われたまま、みたいな性質があると楽になるなあと考えたが、そんなことはなかった。

■枚数を増やしたときに、一度覆われた区間が覆われなくなる例
K=3
  0   0 100 -50 100   0   0
        |---------|            1枚の時の最適配置
|---------|     |---------|    2枚の時の最適配置

分割統治をする。
分割統治にあたり、そのままで考えると区間またぎの処理が邪魔になるので、「ここに左端を揃えてタイル1枚を置いた時のスコア」を表す長さ $N-K+1$ の数列になおす。

K=3
A  3  1  4 -1 -5  9  2
  `v------'
B  8  4 -2  3  6

元の問題は、$B$ から「互いに $K-1$ 以上の間隔をあけていくつかの要素を選択したときの和」と言い換えられる。

言い換えたとて、$[l,m)$ と $[m,r)$ から $[l,r)$ を求めたいとき、やはりこの「間隔」が邪魔になる。
だがそこは、$K$ が小さいことを利用して「左右から、空白が保証されている区間の長さ」を状態に加えることで、解決できる。

• $\mathrm{DP}[l,r,x,y,i]:=B[l,r)$ から、少なくとも左から $x$ 個、右から $y$ 個は選ばず、$i$ 個の要素を選んだときの和の最大値
  • ※ $x,y=0～K-1$ の範囲を動く。

区間 $[l,m)$ と $[m,r)$ をマージするとき、$[l,m)$ の右から $k$ 個を選んでいない場合、$[m,r)$ の左から $K-k-1$ 個が選ばれていなければ良い。
つまり、$\mathrm{DP}[l,r,x,y,*]$ は、$\mathrm{DP}[l,m,x,k,*]$ と $\mathrm{DP}[m,r,K-k-1,y,*]$ のマージで計算できる。
ただし、$k=0～K-1$ の範囲を動き、その中で最も良いものを採用するとする。

あとは個数 $i$ の次元をマージしたい。
最大値畳み込みなのだが、以下のように素直な畳み込みでは、1回のマージで区間長の2乗に比例した計算量がかかり、全体の計算量が $O(N^2)$ 以上となってしまう。

• 素直な最大値畳み込み
  • $P_{i+j} = \max_{i,j}(Q_i + R_j)$
  • ただし、$P=\mathrm{DP}[l,r,x,y],Q=\mathrm{DP}[l,m,x,k],R=\mathrm{DP}[m,r,K-k-1,y]$
  • $|Q||R|$ の計算量がかかる

ここで、「$\mathrm{DP}[l,r,x,y,i]$ は、$i$ に対して上に凸」という性質を利用する。

要は、「選択する個数を増やしていくと、1個増やした事によるスコアの増分は、だんだん減っていくよね」という性質。

• potato167氏による証明

マージしたい2列がこの性質を持つ場合、「2つの列の内、次に1個増やすことの増分が大きい方を採用」を繰り返すことで、 区間長に比例した計算量でマージできる。

全体で、$O(N K^3 \log{N})$ で求められる。

公式解説では $O(N K^2 \log{N})$ とあるので、より効率的な更新方法があるのかもしれない（しっかり読めてない）が、3乗でも間に合う。

実装上の問題として、区間長が $1～2$ など $K$ より短い場合、DPの「左右から $x,y$ 個は選んでいない」という状態をどう持たせ、どう更新していいか迷ったので、 ある程度区間長が短く（$2K$ 以下）なったら、再帰を止めて愚直に $O(K^4)$ 程度かけて求めるようにした。

Python3