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

久しぶりの参加録。AtCoder Beginner Contest 261に参加。調子が戻ってきたかな?

A - Intersection (100点)
B - Tournament Result (200点)
C - NewFolder(1) (300点)
D - Flipping and Bonus (400点)
E - Many Operations (500点)
F - Sorting Color Balls (500点、実行時間制限: 3 sec)
G - Replace (600点): 未提出
Ex - Game on Graph (600点): 未提出
結果、感想

A - Intersection (100点)

区間 $[L_1,\,R_1],$ $[L_2,\,R_2]$ が共通部分を持つとき、その共通部分の左端は $\max\{L_1,\,L_2\}$ で右端は $\min\{R_1,\,R_2\}$ となります。共通部分を持たないときはその左端と右端が入れ替わる、即ち、 $\max\{L_1,\,L_2\} > \min\{R_1,\,R_2\}$ となります。そのため出力すべき答えは $\max\{0,\,\min\{R_1,\,R_2\} - \max\{L_1,\,L_2\}\}$ となります。

B - Tournament Result (200点)

$A_{i,\,j}=$ 'W' で $A_{j,\,i}\neq$ 'L'
$A_{i,\,j}=$ 'L' で $A_{j,\,i}\neq$ 'W'
$A_{i,\,j}=$ 'D' で $A_{j,\,i}\neq$ 'D'

のいずれかが成り立つような $i < j$ が存在するか、2重ループで探せばいいです。

C - NewFolder(1) (300点)

各文字列 $S_i$ に対して毎回 $S_1$ から $S_{i-1}$ まで一致するかを調べると文字列の長さを $L$ として $O(LN^2)$ となってTLEします。
mapやunordered_mapを用いることで $O(LN\log N)$ や $O(LN)$ で計算可能で、 $L \leq 10$ より十分高速です。

D - Flipping and Bonus (400点)

DはDPのD。

${\mathrm{dp}}_{i,\,j} = (\text{$i$ 回のコイントス後カウンタが $j$ のときの賞金の最大値})$

とします。今回は貰うDPでの記述が難しいので配るDPで書きます。
初期値を

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

とし、 $i=1,\,2,\,\dots,\,N$ に対して $j=0,\,1,\,\dots,\,N-1$ について ${\mathrm{dp}}_{i-1,\,j} \neq -1$ のとき遷移

${\mathrm{dp}}_{i,\,0} \leftarrow \max\{{\mathrm{dp}}_{i,\,0},\,{\mathrm{dp}}_{i-1,\,j}\} \\ {\mathrm{dp}}_{i,\,j+1} \leftarrow \max\{{\mathrm{dp}}_{i,\,j+1},\,{\mathrm{dp}}_{i-1,\,j} + X_i + y_{j+1}\}$

を行います。ここでの $y_j$ は連続ボーナスで、

$y_j = \left\{ \begin{array}{ll} Y_k & ({}^{\exists} k\ \ \mathrm{s.\!t.}\ \ C_k = j)\\ 0 & (\mathrm{Otherwise}) \end{array} \right.$

とします。
出力する答えは $\displaystyle \max_{0 \leq j \leq N} {\mathrm{dp}}_{N,j}$ です。
また、上の $-1$ のところを $-10^{18}$ など十分に小さい値にすれば場合分けが不要になります。

E - Many Operations (500点)

毎回愚直に操作 $1,\,2,\,\dots,\,i$ を行っていると操作回数が全体で $\dfrac{1}{2}N(N+1)$ となるので計算量 $O(N^2)$ でTLEとなります。

各操作はbit演算であるため、bit毎に独立であり、2進数表記で下位から $j$ 桁目が $k =0 \text{ または } 1$ であったときに操作 $1,\,2,\,\dots,\,i$ を施した結果 $r_{i,\,j,\,k}$ は初期値を $r_{0,\,j,\,k} = k$ として $r_{i,\,j,\,k} = \operatorname{op}_j (r_{i-1,\,j,\,k} )$ として計算可能です。よって $i$ 回目では操作前の値 $x$ に対して $y = \displaystyle\sum_{j=0}^{30} 2^j r_{i,\,j,\, \left\lfloor \frac{x}{2^i} \right\rfloor \bmod 2}$ が答えとなり、 $x$ を $y$ に置き換えて $i$ 回目の操作につなげます。

また、 $R_0 = \displaystyle\sum_{j=0}^{30} 2^j r_{i,\,j,\, 0}$ は $0$ に、 $R_1 = \displaystyle\sum_{j=0}^{30} 2^j r_{i,\,j,\, 1}$ は $2^30 - 1$ に操作 $1,\,2,\,\dots,\,i$ を行ったときの値であるため、bit毎に考えずに $y = R_1 \operatorname{and} x + R_0 \operatorname{and} (\operatorname{not}x)$ と計算することができます。

計算量は $B=30 = \displaystyle\sup_{\text{問題制約}} \log N$ としてbit毎に求めるのが $O(NB)$ 、後者が $O(N)$ となります。

F - Sorting Color Balls (500点、実行時間制限: 3 sec)

初期状態で $i < j$ で $X_i > X_j$ であるような $i,\,j$ の組はソートの途中で入れ替えなければならず、その他の $i,\,j$ の組は入れ替える必要がありません。同色の球は入れ替えてもコストがかからないため、求める答えは $(\text{全体の転倒数})-\displaystyle\sum_{c=1}^{N}(\text{色 $c$ の球のみの転倒数})$ となります。
転倒数は $\displaystyle \sum_{i=1}^{N} \#\{j \mid j < i \land X_j > X_i\}$ であるため、セグ木やBITなどで計算することができます。しかし、各色についてもセグ木やBITを作ると全体で $O(N^2)$ 個の要素となるので時間計算量、空間計算量ともにオーバーします。
各色についてのセグ木やBITについては $X_i$ を座圧してやることで必要な要素数を全体で $O(N)$ にしてやることができ、空間計算量 $O(N)$ 、時間計算量 $O(N \log N)$ でACすることができます。