93. 昨日と今日解いた問題（2022.03.31）

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

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

問題一覧

E - Mex Min （Diff: 1088）
C - Align （Diff: 1095）
D - Strange Lunchbox （Diff: 1085）
E - Amusement Park （Diff: 1084）

前 2 つは、正直緑diffとは思えないほど難しかったです。この問題セットの中では 3 問目が一番楽かな、と思います。

自分の解法など

E - Mex Min

$i \rightarrow i+1$ の遷移で変化するのは

$x_i$ が除外される
$x_{i+1+M}$ が採用される

のみです。よって、これを上手く計算してやればよさそうです。

$A_1$ について mex を計算するついでに、その数列に $0 \le y \lt N$ なる $y$ がいくつ含まれるか Dictionary として保持しておきます。これとは別に、数列に含まれない、非負整数の（重複のない）リストを保持します。mex はこの中で最小の数です。PriorityQueue を使いたいところですが、遷移によって動的な除去が必要なので、MultiSet を使います。遷移ごとに Dictionary と MultiSet を適切に更新していきます。

計算量は $O(N \log N)$ ですが、MultiSet の操作が $O(\log N)$ とはいえオーバーヘッド大きめなので若干厳しいです。制約が $N \le 1.5 \times 10^6$ と大きめなのも厳しいです。重いのは MultiSet で最小値を持ってくる所で、定数倍改善としてこの操作を極力行わないようにしないと間に合いませんでした。

これは…（4 sec制限） pic.twitter.com/vbyuyDdRgc
— イバコ (@ibako_piyo) 2022年3月30日

C - Align

あんまり戦略が浮かばないのでサンプルを見てみます。すると、「大きい数・小さい数・大きい数…」という順に並べていけばなんとなくよさそうに思えます。

$(x_1, x_2, x_3)$ という数列を考えてみて、 $x_1 \lt x_2 \lt x_3$ であれば $(x_1, x_2)$ または $(x_2, x_3)$ を入れ替えた方がよいことが分かります。よって、 $x_1 \le x_2\ge x_3 \le x_4 \ge \dots$ または $x_1 \ge x_2\le x_3 \ge x_4 \le \dots$ のような並べ方が必要条件になっているといえます。

前者の条件で問題の値を求めると、 $(-x_1 + x_2) + (x_2 - x_3) + (-x_3 + x_4) \dots$ のような計算式になります。また、後者の条件では $(x_1 - x_2) + (-x_2 + x_3) + (x_3 - x_4) \dots$ のようになります。式を整理して、以下のようになります（ $B_i$ は $A_i$ を並べ替えた数列とします）。

が奇数のとき
- $B_1 - 2B_2 + 2B_3 - 2B_4 + \dots -2B_{N-1} + B_N$
  または
- $-B_1 + 2B_2 - 2B_3 + 2B_4 - \dots +2B_{N-1} - B_N$
が偶数のとき
- $B_1 - 2B_2 + 2B_3 - 2B_4 + \dots + 2B_{N-1} - B_N$
  または
- $-B_1 + 2B_2 - 2B_3 + 2B_4 - \dots - 2B_{N-1} + B_N$

よって、これを最大化するように数列の項を割り当てればよいです。つまり、加算になっている項は大きい方から、減算になっている項は小さい方から割り当てます。ただし、係数が 1 である項が 2 箇所出てくるので、ここには正であれば「大きい方から」なるべく小さな値、負であれば「小さい方から」なるべく大きな値を割り当てなければなりません。それ以外は、先ほどの条件に従って適当に当てはめればよいです。

結局、数列のソート後にこれらの割当操作をするだけなので、計算量は $O(N \log N)$ です。

D - Strange Lunchbox

全探索は無理です。問題文の雰囲気からたぶん DP だろうなー、と思います。

$dp(i 個目までの弁当を確認した, j 個のたこ焼きになる, k個のたい焼きになる) = 最小の弁当数$ と素直にテーブルを作ってみます。これで行けそうです。

問題はぴったり $X$ 個のたこ焼き・ $Y$ 個のたこ焼きが入手できるとは限らない点です。 $A_i, B_i \le 300$ という制約があるので、オーバーしても $300$ 個分程度です。よって、それぞれ $600$ 個分テーブルを用意して、答えを出すときに $X \le j \le 600, Y \le k \le 600$ の範囲を全部見て最小値を出すことにします。

計算量は $O(N(600)^2)$ で大きく見積もって $10^7$ 程度なので十分そうです。

E - Amusement Park

明らかに、満足度の大きなアトラクションに乗り続けるのが最善手です。ただし、 $K \le 10^9$ と非常に制約が大きいため、単純なシミュレーションはできません。

そこで、予め $A_i$ を降順に並べた $B_i$ を考えて、順番に項を見つつ以下のようなシミュレーションを行っていきます。ただし、末端の計算は等差数列の和の公式などを用いて定数時間で行います。また、アトラクションに乗れる残り回数に気をつけて、数が足りない場合は除算・剰余を用いて適切な計算式に変更します（式は割愛します）。