AtCoder Beginner Contest 242のきろく - Flkanjin’s 競プロ録

A - T-shirt (100点)
B - Minimize Ordering (200点)
C - 1111gal password (300点)
D - ABC Transform (400点)
E - (∀x∀) (500点)
F - Black and White Rooks (500点)
G - Range Pairing Query (600点、実行時間制限: 5 sec)
Ex - Random Painting (600点、実行時間制限: 3 sec): 未提出
結果、感想

A - T-shirt (100点)

$X \leq A$ の時は必ずTシャツは貰えるので、答えの確率は $1$ 、 $X \gt B$ の時は、Tシャツをもらえることが無いので $0$ です。
その他のときは $B-A$ 人の中から一様に $C$ 人を選ぶとき、自分が選ばれるときの確率ですので $\displaystyle \frac{C}{B-A}$ が答えとなります。

B - Minimize Ordering (200点)

$S$ 内の文字を昇順に並び替えればいいので、sort関数で並び替えてやればいいです。

C - 1111gal password (300点)

桁DPです。

${\mathrm{dp}}_{i,j} = (\text{最下位の桁が $j$ である $i$ 桁の条件を満たす整数の個数})$

とします。このとき、初期条件を

${\mathrm{dp}}_{1,j} = 1 (1 \leq j \leq 9)$

として、遷移条件

${\mathrm{dp}}_{i+1,j} = \left\{ \begin{array}{ll} {\mathrm{dp}}_{i,j} + {\mathrm{dp}}_{i,j+1} & (j = 1)\\ {\mathrm{dp}}_{i,j} + {\mathrm{dp}}_{i,j+1} + {\mathrm{dp}}_{i,j-1} & (1 \lt j \lt 9)\\ {\mathrm{dp}}_{i,j} + {\mathrm{dp}}_{i,j-1} & (j = 9)\\ \end{array} \right.$

によって $i = N$ まで $1 \leq j \leq 9$ でDPの値を求めたときの、 $\displaystyle\sum_{j = 1}^{9} {\mathrm{dp}}_{N,j}$ が答えとなります。

D - ABC Transform (400点)

この問題では文字列を0-based indexで考えます。
A→B→C→A という循環を考えます。
$S^{(i)}$ から $S^{(i+1)}$ が作られるとき、 $S^{(i)}$ の $j$ 文字目から $S^{(i+1)}$ の $2j$ 文字目と $2j+1$ 文字目が作られます。このとき、 $2j$ 文字目は循環において $1$ つ進んだ文字、 $2j+1$ 文字目は循環において $2$ つ進んだ文字となります。
このことから次のことが分かります。

$S^{(i)}$ の $j$ 文字目は大本を辿ると $S^{(0)}$ の $\displaystyle \left\lfloor \frac{j}{2^i} \right\rfloor$ 文字目に由来する。
→ クエリ" $t\ \ k$ "について $S'^{(0)} = S_{\left\lfloor \frac{k}{2^t} \right\rfloor}$ 、 $k' = k \bmod 2^t$ として、 $S'^{(t)}$ の $k'$ 文字目を求める問題として読み替えることができます。
元の $0$ 文字目から $t$ 回操作後の $k$ 文字目に遷移するまで、 $(j \rightarrow 2j+1)$ の遷移を $\operatorname{popcount}(k)$ 回、 $(j \rightarrow 2j)$ の遷移を $t-\operatorname{popcount}(k)$ 回行う。ここでの $\operatorname{popcount}(\cdot)$ は二進数表記での $1$ である桁の数を表す函数
→ 循環上では $2\operatorname{popcount}(k) +1 (t-\operatorname{popcount}(k)) = t+\operatorname{popcount}(k)$ だけ進んだ文字になります。

よってこの二つの観察から答えを導くことができました。

E - (∀x∀) (500点)

回文であるので先頭 $\displaystyle \left\lceil \frac{N}{2} \right\rceil$ 文字の決め方について考えます。

まず、 $S$ の先頭 $\displaystyle \left\lceil \frac{N}{2} \right\rceil$ 文字よりも辞書順で小さい $\displaystyle \left\lceil \frac{N}{2} \right\rceil$ 文字の文字列の数を求めます。
先頭 $i$ 文字が等しいものは $26^{\left\lceil \frac{N}{2} \right\rceil-i} f(S_i)$ 個あります。ここでの $f(c)$ は文字 $c$ のアルファベット順の順番から $1$ を引いたものです。よって $i$ を $1$ から $\displaystyle \left\lceil \frac{N}{2} \right\rceil$ までを足し合わせたものがここでの値です。

次に、 $S$ と先頭 $\displaystyle \left\lceil \frac{N}{2} \right\rceil$ 文字が等しい $N$ 文字の回文が $S$ よりも辞書順で小さいかどうかを調べます。これで $g(S)$ を定義します。この段落での最初の文での条件を満たせるなら $1$ 、そうでなければ $0$ を返します。

これらよりこの問題の答えは $\displaystyle g(S) + \sum_{i = 1}^{ \left\lceil \frac{N}{2} \right\rceil} {26^{\left\lceil \frac{N}{2} \right\rceil-i} f(S_i)}$ となります。

F - Black and White Rooks (500点)

包除原理が思いつかなかった... ~~通したら追記します。~~ upsolveしたので追記します。

白と黒の飛車/Rookが同一列、同一行内に存在するとき、その行または列内で、互いに利いている白と黒のペアが存在します。その為、各行、列は駒なし/白/黒のいずれかです。よって、各行、列の状態について、各色が選ばれた行、列の全てに駒が存在し、かつ選ばれた行、列以外に駒が存在しないような配列の方法数が分かればいい、ということまではコンテスト中には分かっていました。

選ばれた行、列のみ注目します。「いずれの行、列にも駒が存在する」ということはde Morganの法則から包除原理で計算することができます。このことから最終的な答えは $\displaystyle \sum_{i=1}^{N} \sum_{j=1}^{N-i} \sum_{k=1}^{M} \sum_{l=1}^{M-k} \tbinom{N}{i}\tbinom{N-i}{j}\tbinom{M}{k}\tbinom{M-k}{l} \left\{\sum_{I=0}^{i}\sum_{K=0}^{k}(-1)^{I+K}\tbinom{i}{I}\tbinom{k}{K}\tbinom{(i-I)(k-K)}{B}\right\} \left\{\sum_{J=0}^{j}\sum_{L=0}^{l}(-1)^{J+L}\tbinom{j}{J}\tbinom{l}{L}\tbinom{(j-J)(l-L)}{W}\right\}$ です。括弧の中をメモ化しておくことで計算量 $O(N^2M^2)$ で答えることができました。

G - Range Pairing Query (600点、実行時間制限: 5 sec)

Mo’s Algorithm(莫のアルゴリズム、平方根分割)だと気づくのが遅く実装できませんでした... ~~通したら追記します。~~ upsolveしたので追記します。

各クエリに対する答えは $\displaystyle \sum_{c=1}^{N} \left\lfloor \frac{(\text{区間内で色 $c$ の服を着ている人数})\hspace{2.5cm}}{2}\right\rfloor$ です。区間を $[l,\,r]$ から $[l\pm1,\,r]$ や $[l,\,r\pm1]$ に更新するとき、追加または削除された色の人数の偶奇によって、答えが $1$ 増減したり、変わらなかったりします(具体的には人数増加して偶数になったら $+1$ 、人数減少して奇数になったら $-1$ 、その他は不変)。そのため、各色の人数と答えを変数で管理することで区間の $\pm1$ の更新は $O(1)$ で行うことができるため、Mo’s Algorithmを適用することができます。

Mo’s Algorithmはクエリを先読みし、ある特定の順番でクエリを処理することでクエリの更新回数を減らすというアルゴリズムです。全体区間をある大きさのブロックに分割し、各区間を左端がどのブロックに属すかで、ソートします。同一ブロック内の区間たちについては右端でソートします(こちらはブロックではなくもとの値でソート)。このときのブロックの大きさは大体 $\sqrt{Q}$ ぐらいにすることが多く、そのとき計算量は $O(N\sqrt{Q})$ となります。