AtCoder Beginner Contest 376 E問題の解説＆攻略記事です。
コンテストの解説を見ても「なんでこんなの思いつくねん！」と思わず叫んでしまうことが多いので、どう考えてそうなったのかをできるだけ細かく書いていきます。
問題URL
今回のポイントは2つです。
それでは攻略していきましょう！
入力例を手計算してみる
今回の最初のポイントは、手計算です。
解法がすぐに浮かばない場合、何か重要な性質を見落としている場合が多いです。
そういうときは入力例などを頼りにいくつか計算してみると解法が見えたり見えなかったりします。
今回は入力例の2つ目のクエリ
5 3
6 4 1 5 9
8 6 5 1 7
についていくつか計算してみましょう。
ここで部分集合1と2に注目すると、$max \ A_i$のはどちらも9です。
考えてみれば$i=4$を部分集合に入れると、$A$の最大要素は常に9になります。
ですから、$i=4$を部分集合に入れた場合の最小値は
9 \times (7+(B_{i \neq 4}の小さい方からK-1個の総和))
となります。
$i=4$以外の$K-1$個をどう選ぼうが、$ \max \ A_i $は9で固定されているからです。
ここで、$M_a$を次のように定義しましょう。
i=aがmax \ A_iとなるような要素数Kの部分集合の中で、Ansが最小のもの
例えば、$i=0$が$max \ A_i$となるような要素数$K$の部分集合は以下の3つです。
この中で$Ans$の最小は84なので、$M_0=84$です。
最終的な答えは$min \{ M_0, M_1,\cdots,M_{N-1} \}$となるので、$M_a$が爆速で求められれば良さそうです。
ここでポイントになるのは、DP感覚です。
DP感覚を研ぎ澄ませる
DP感覚というのは僕がかってに使っている造語で、「あ、これなんかDPっぽいことができそう」という感覚のことです。
競プロをある程度やっているとこの感覚があるていど身についてくるものです。
今回の問題でいうと、$A_i$の小さい順に$M_i$を求めていけばうまくいきそうだな〜という感じです。
ということで、$A_i$の小さい順に並べ替えて左から$M_i$を求めることを考えます。
並び替えたものがこちら
そしてもう1つ、$S_i$を
$$
i番目より左のなかでB_iの小さい方からK-1個の集合
$$
としておきます。そして$S_i$の要素の総和を$sum(S_i)$と書くことにします。
\displaylines{
sum(S_2) = 5+6 = 11 \\
sum(S_3) = 1 + 5 = 6 \\
sum(S_4) = 1 + 5 = 6 \\
}
となります。この$S$を使うと、
$$
M_i = A_i \times (B_i + sum(S_i))
$$
なので、$sum(S_i)$が爆速で求められれば$M_i$も爆速で求めることができます。
そしてそして、この$S_i$は$S_{i-1}$から求めることができます！
DPっぽいですね。
区間はだんだん広げると吉であることが多いので、$S$が区間になってるな〜ということに気がつけば、「だんだん広げていけば良さそう！」と思えそうです。
具体的には以下の手順です。
- $S_{i-1}$に$B_{i-1}$を追加する
- そしてその中から一番大きい要素を削除すれば、$S_i$となっている
追加と最大要素の削除が行えればいいので、$S$をsetや優先度付きキューで管理すればこの問題を解くことができます！！
解決
以上でABC376-Eは攻略完了です！
お疲れ様でした！