イバコの生存記録

いまは競プロ（AtCoder）記事がメインです。

92. 今日解いた問題（2022.03.29）

プログラミング AtCoder

今日解いた問題についてまとめます。

自分で解きたい方のために、最初に問題だけ置いて、後で自分の解法を書きます。

問題一覧

C - Linear Approximation （Diff: 1089）
E - Get Everything (Diff: 1397)

2 問目が個人的に面白かったです。

自分の解法など

C - Linear Approximation

予め $B_i = A_i - i$ を計算しておけば、 $|B_i - b|$ の総和が最小となる $b$ を求める問題になります。

考えやすくするため、 $B_i$ は昇順に並んでいるとします。適当な数 $x$ を $b$ の値として考えてみます。 $b = x + 1$ とすると、総和は $(x 以下の要素数) - (x より大きな要素数)$ だけ変化することが分かります。逆に $b = x - 1$ とすると、総和は $(x以上の要素数) - (xより小さな要素数)$ だけ変化します。これらを考慮すると、 $B_i$ の中央値が $b$ として最適なことが分かります。

よって、この問題は数列のソートに最も時間がかかって $O(N \log N)$ です。

E - Get Everything

まず、 $N$ が非常に小さいことに注目します。素直に考えると $M$ について全探索したくなるのですが、おそらく $N$ に関して全探索するのだろう、と目星をつけておきます。

$N$ 個の宝箱をそれぞれビットに割り当てると、鍵が開けられる宝箱についてビットを $1$ とすることで、鍵に対して $0 \le d_i \lt 2^N$ という値を算出できます。複数の鍵を組み合わせて開けられる宝箱は、 $d_i \; or \; d_j$ のようなビット演算で表現できます。

ここまで来たら、 $dp(x \; or \; y) = \min(dp(x \; or \; y), dp(x) + dp(y))$ のような式で費用の最小値を更新できることが見えてきます。単独の鍵で開けられるところを $dp(d_i) = a_i$ で初期化しておき、他は $\infty$ とします（加算するのでオーバーフローに注意します）。 $0 \le k \lt 2^N$ の二重ループで DP テーブルを更新していきます。

これを $N$ 回繰り返せば DP テーブルは十分更新されるので、 $dp(2^N-1)$ が $\infty$ であればすべての宝箱を開けることは不可能、それ以外の場合は現在値が答えになります。

計算量は $O(N(2^N)^2)$ ですが、 $N \le 12$ なのでこれでも $10^7$ 程度のループ数に収まります。