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

久しぶりの更新です。AtCoder Beginner Contest 221に参加です。

A - Seismic magnitude scales (100点)
B - typo (200点)
C - Select Mul (300点)
D - Online games (400点)
E - LEQ (500点)
F - Diameter set (500点)
G - Jumping sequence (600点、実行時間制限: 5 sec): 未提出
H - Count Multiset (600点): 未提出
結果、感想

A - Seismic magnitude scales (100点)

答えは $32^{A-B}$ となります。powなどを用いてもこの問題ではOKですが、場合によっては誤差が発生しうるのでfor文を使うのが無難と思いそちらで組みました。

B - typo (200点)

問題文の通り、何も操作を行わないとき、 $i$ 文字目と $i+1$ 文字目を入れ替えたとき、それぞれについて一致するかどうかを調べることで解けます。
実装的には各 $i$ について $i$ 文字目と $i+1$ 文字目を入れ替えたときと戻した時を判定すれば、何も操作を行わないときについて別個に書く必要がなくなるので、コードは短くなりますね。

C - Select Mul (300点)

$N$ の各桁の数字を任意の順番に並べて、その先頭の数と、後ろの数と見做すことで全ての分離方法を考えることができ、その方法は $N$ の桁数を $n$ とするとき $O(n!n)$ 通りあり、計算量も $O(n!n)$ となります。
ここで、各分離方法について、それぞれの数字を降順にソートした方が答えが大きくなるため、各数字を2つのグループのどちらかに所属するかの $2^n$ 通りのみの分離方法のみ調べる必要性があることになります。これはbit全探索を用いて計算量 $O(2^nn)$ で実装できます。
本番では後者の方法がすぐ思い浮かんだので、そちらでのみ実装しました。
どうやら $O(n)$ 解や $O(n \log n)$ 解があるようですが、こんなの本番中に思いつけへんやん...

D - Online games (400点)

全ての日について考えると最大で $2 \times 10^9$ 日目まで考える必要があるので、間に合いません。人数の変動があるのは各 $i$ について $A_i$ 日目と $A_i + B_i$ 日目なので、その節目で人数が何人になって、その間隔が何日なのかを計算することで答えを求めることができます。
本番では間隔の前後を間違えて1WAしました。

E - LEQ (500点)

$A^{'}_1$ が $A_i$ , $A^{'}_k$ が $A_j$ であるような部分列の個数は $A_{i+1},\,A_{i+2},\,\dots,\,A_{j-1}$ のそれぞれを選ぶかどうかの $2^{j-i-1}$ 通りであるため、求める答えは $\displaystyle \sum_{\substack{1 \leq i \lt j \leq N \\ A_i \leq A_j}} 2^{j-i-1}$ です。
$2^{j-i-1} = \dfrac{2^j}{2^{i-1}}$ であるため $A^{'}_1$ として $A_i$ を選んだ時、 $i \lt j \leq N,$ $A_i \leq A_j$ となるような $j$ について $2^j$ を足していき、 $2^{i-1}$ で割ることでこのときの部分列数が求まります。よってこれを全ての $i$ について足していけばいいことができます。
これは $A_1,\,A_2,\,\dots,\,A_N$ について $1,\,2,\,\dots,\,2^{N-1}$ という重みを付けた個数のセグ木について添え字の降順に走査することで実装することができますが、 $A_i$ の値が $10^9$ 程度になることにもなるため座標圧縮してやる必要があります。
本番ではセグ木の演算でmodをとらせるということをしていなかったため1WA出してしまいました。

F - Diameter set (500点)

木の直径はdouble sweep によって求めることができます。そこから木の中心 $c$ を求めますが、この時、直径の偶奇で場合分けをしますが、各辺上に頂点を追加してやることで、直径を2倍にし、偶数にすることができ、この直径を $2d$ とします。
この木を $c$ を根とする根附き木として、 $c$ の直接の子を $k_1,\,k_2,\,\dots,\,k_n$ として、 $c$ 以外の点をそれぞれどの $k_i$ の子孫(または $k_i$ 自身)であるかでグループ分けします。各グループについて $c$ からの距離が $d$ であるような点の個数を $m_i$ とします。条件を満たす点の選び方は各グループについて距離 $d$ の点を高々1つづつ選んでいき、かつ選んだ個数が $2$ 以上のものであるため、 $\displaystyle \prod_{i = 1}^{n}(m_i+1) - \sum_{i=1}^{n}m_i -1$ 通りとなります。