96. 今日解いた問題（2022.04.06）

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

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

問題一覧

A - Bridge and Sheets (Diff: 247)
B - Reserve or Reverse (Diff: 934)
C - The Majority (Diff: 1560)

自分の解法など

A - Bridge and Sheets

最適な戦略を考察します。

たとえば、長さ $3$ のシートで $[0, 5]$ の部分を覆うことを考えます。全てを覆うことが要求されているため、いずれは左端にシートを置く必要があります。よって、とりあえず左端にシートを置くと $[0, 3]$ の部分が覆われます。次に、同じように考えていずれは $x=3$ の場所にシートを置く必要があります。

このように考察すると、長さ $l$ の連続する区間が覆われていないとき、シートは少なくとも $\lceil \frac{l}{W} \rceil$ 枚必要であり、また、これが最適解です。

よって、既に存在する $N$ 枚のシートを座標昇順に並べて、覆われていない区間の長さを算出して各部分に必要な最小シート枚数を算出し、足せば答えになります。ちなみに、この問題では予め $a$ は座標昇順に並んでいるため、ソートする必要はないです（ソートしても間に合います）。

計算量は $O(N)$ です。

B - Reserve or Reverse

最適な戦略を考察します。

例 1 を見ます。a を 1 文字目に持って行きたいので、 $x = (1, 3)$ としたいです。これ以上取れないので、結局これが最適解になります。

例 3 を見ます。a をなるべく前方に持って行きたいです。この例を見ると、後ろから順に見て a を貪欲に選択し、前から順に入れ替える戦略が有効そうです。今回はこの考え方がベースになります。

前方に持ってくる文字は a とは限りません（例 4 を見れば分かります）。どのように前方へ持っていく文字を決定するか考えます。

入れ替え操作をイメージすると、「現在入れ替え対象となってる前方の文字」と「現在確認している後方の文字」の間に「後方の文字」より小さいものが無ければ前方に持って行けばよいことが分かります（もし間に小さいものがあれば、それを前方に持ってくる方が辞書順は小さくなります）。ここでさらに考察すると、「前方の文字」が「後方の文字」より小さい場合は入れ替え操作をしない方がよいと分かります。

以上より、次のような操作で辞書順最小の文字列を作ることができると分かりました。

前方のインデックスを $i$ 、後方のインデックスを $j$ として、 $i = 1, j = N$ で初期化する。 $c =$ 'a'（文字）とする
$i \ge j$ または $c \ge$ 'z'（文字）なら終了
$s_k = c$ となる $k (i \lt k \le j)$ が存在しないなら $c \leftarrow c + 1$ として 2. へ
$s_i \le c$ なら何もせず $i \leftarrow i + 1$ として 2. へ
$s_j = c$ なら $s_i, s_j$ を入れ替えて $i \leftarrow i + 1$ 、 $j \leftarrow j - 1$ として 2. へ
$j \leftarrow j - 1$ として 2. へ

ここで問題となるのは 3. の「間に文字が存在するか？」の判定です。ここを定数時間に落とすため、文字ごとに登場回数の累積和配列 $A$ （長さ $N$ ）を取っておきます。 $A_j - A_i = 0$ であれば、 $s_i$ から $s_j$ の間にその文字は存在しないです。これによって、事前計算 $O(N)$ 、判定 $O(1)$ が達成できます。

以上より、 $O(N)$ で解くことができました。

C - The Majority

状況を上手く整理します。

とりあえず全ての箱に $1$ のボールを少なくとも 1 つ入れておく必要があるため、そうしておきます。

その後、各箱において $1$ のボールが過半数を維持するように他のボールを入れていくことを考えます。これは、 $1$ 以外のボールを入れるとき、一緒に $1$ のボールを入れてやることで達成できることが分かります。逆に、このような操作ができないと過半数は達成できません。

この操作で $1$ 以外の全てのボールを箱に入れて、なお $1$ のボールが余っていた場合はどこに入れても良いです。これで全てのボールを箱に入れられました。

操作をまとめると、

【0】 $a_1 \lt K$ または $\displaystyle a_1 - K \lt \sum_{i=2}^{N}a_i$ であるなら達成不可能（0 通り）
【1】 $1$ のボールを、 $K$ 個の箱に各 1 つずつ入れる
【2】 $i (2 \le i \le N)$ のボールを 1 つずつ、 $1$ のボールとペアにして任意の箱に入れる
【3】 $1$ のボールが余っているなら、1 つずつ任意の箱に入れる

それぞれの操作が何通りあるかを式で表現すると、

【1】1
【2】 $\displaystyle \prod_{i=2}^{N} {}_K H_{a_i}$
【3】 $\displaystyle {}_K H_{a_1 - K - \sum_{i=2}^{N} a_i}$

となります。ここで【2】の式について $_{K} H_{a_i} = _{K + a_i - 1}C_{a_i}$ ですが、制約より $K$ の方が上限が小さいので $_{K+a_i-1}C_{K-1}$ とした方が計算量を落とせます。また、Combination の計算で出てくる除算は mod 逆元を利用します。