AtCoder Beginner Contest (ABC221) に参加して， ABCDEF 6完2ペナルティ 238位でした．その記録です．

A - Seismic magnitude scales

$32^{B-A}$ が答です．

B - typo

S = T か，または， 隣り合う2文字を入れ替えてみて T と一致すれば Yes, そうでなければ No です．

「隣り合う」というのを見落として1WA．良く読まなくちゃ．

C - Select Mul

$N$の桁数を $t$ として，2つに分離する方法が $2^t$ くらいあります (実際には両者1つ以上必要なので，$2^t - 2$)．これらを全部探索します． 2つに分けたら，各々降順ソートして掛け合わせます．

D - Online games

イベントソートです．

  • ユーザが x 日目にログインした … $(x, 1)$
  • ユーザが y 日目にログアウトした … $(y, -1)$

これらを昇順にソートして，順に見ます．現在のログイン数を表す 変数 num に，一つ前に見た組の日付を表す変数 prev を使い， $(z, c)$ を見たら，次を実行します:

answer[num] += z - prev;
num += c;
prev = z;

E - LEQ

解法

$i < j$ で $A_i \leq A_j$ となっていたら， $i$ で始まって $j$ で終わる部分列 $2^{j - i - 1}$ 個は条件を満たします．これ以外に条件を満たす部分列はありません．

したがって，求める答は

$$ \sum_i \frac{1}{2^{i+1}} \sum \{ 2^{j} \mid i < j \text{ and } A_i \leq A_j \} $$

となりますから， $i$ の大きい方から順に，和をセグメント木で求めていけば良いです． 座標圧縮が必要です．

経緯

$i$ を大きい方から見ていくということは考えていたのですが， $i$ が減るたびに，

  • 今ある値を全部2倍して，
  • A_i のところに 1 を追加する

という操作をしなくてはならず，これはできないよな，と思って 上の解法に至るまでだいぶ時間を使いました．終了後，それは 遅延セグメント木でできる，という指摘がありました．

F - Diameter set

解法

木の直径などに関しては以下が成り立ちます． maguroflyさんのまとめ がわかりやすい．

  • 任意の点$x$に対し，$x$ から $y$ が最遠で，$y$ から $z$ が最遠であるとき， $y$ と $z$ を結ぶパスが直径パスになる．
  • 最遠点までの距離が最小の点を中心と呼ぶことにすると，
    • 直径$d$が偶数の時，中心がちょうど1つ存在する． これは，任意の直径パス $y$ – $z$ に対して，パス上にあって $y$ から 距離 $d$ の点である．
    • 直径$d$が奇数の時，中心がちょうど2つ存在する． これは，任意の直径パス $y$ – $z$ に対して，パス上にあって $y$ から 距離 $(d - 1) / 2$ と $(d + 1) / 2$ の点である．

直径$d$が奇数の時には，各中心を根とする (もう一つの中心と反対方向の) 部分木の，深さ$(d - 1) / 2$ の点の数を $m$, $n$ とすれば， 答は $mn$ になります．

直径$d$が偶数の時には，中心に隣接する点の集合を $A$ として， 各 $a \in A$ を根とする (中心と反対方向の) 部分木の， 深さ $d/2 - 1$ の点の集合を $L_a$ と書くことにすれば， 各 $L_a$ から 1点または 0点を選んで赤く塗ることができます． ただし，全体として，部分木を2個以上選ばなくてはなりません． したがって答は，$m_a = |L_a|$ として， $\prod_a (m_a + 1) - \sum_a m_a - 1$ です．

経緯

サンプルが通ったのが，終了5分前． 提出したらWAの山で，だめかなと思ったのですが， 偶然バグが見つかって，終了15秒前に通せました．ラッキー．