エイシングプログラミングコンテスト2021 (AtCoder Beginner Contest 202) 感想

#総合結果
* [Score] 1500 pts
* [Time] 38:11 + <font color="red"> 05:00 $\times$ 0 </font> = 38:11
* [Ranking] 168 th [Rated内: 75 th]
* [Performance] <font color=#C0C000> 2239　</font>
* [Rating] <font color=#0000FF> 1956 </font> → <font color=#0000FF> 1988 </font> (+32)

##各問題ごとの詳細, 提出コード
|Question|Score|Time/Result|Penalty|During Contest|After Contest|
|:--:|--:|:--:|:--:|:--:|:--:|
|<font color=#808080> A問題 </font>|100 pts|00:52|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc202/submissions/22792071)||
|<font color=#808080> B問題 </font>|200 pts|02:36|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc202/submissions/22796932)||
|<font color=#808080> C問題 </font>|300 pts|05:25|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc202/submissions/22801626)||
|<font color=#008000> D問題 </font>|400 pts|13:57|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc202/submissions/22808954)<br>(${\tt for}$ 文)|[■](https://atcoder.jp/contests/abc202/submissions/22843132)<br>(再起)|
|<font color=#0000FF> E問題 </font>|500 pts|<b>38:11</b>|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc202/submissions/22819338)||
|<font color=#FF0000> F問題 </font>|0 pts|--:--|<font color="red"> </font>|||
|<b>Total</b>|<b>1500 pts</b>|<b>38:11</b>|<b><font color="red"> No Penalties </font></b>|||

#問題ごとの略解
##<font color=#808080> A問題 (100pts, diff: 4) </font> [Three Dice](https://atcoder.jp/contests/abc202/tasks/abc202_a)

一般的な (6面) サイコロで, $X$ を表している面の反対の面では $7-X$ を表しているので, 答えは
$$(7-a)+(7-b)+(7-c)=21-(a+b+c)$$
である. 右辺, 左辺どちらの式で実装しても良い.

##<font color=#808080> B問題 (200pts, diff: 16) </font> [180°](https://atcoder.jp/contests/abc202/tasks/abc202_b)
$D[{\tt 0}]={\tt 0}, D[{\tt 1}]={\tt 1}, D[{\tt 6}]={\tt 6}, D[{\tt 8}]={\tt 8}, D[{\tt 9}]={\tt 6}$ という内容の辞書を用意し, 空文字列で初期化した文字列 $T$ に対して, 以下の操作を $S$ の逆順に行えばよい. ただし, $S$ の逆順とは, $S$ の $i$ 番目の文字を $S[i]$  としたとき, $s=S[|S|], S[|S|-1], \dots, S[2], S[1]$ の順に行うことである.

 * $T$ の右側に $D[s]$ を加える.

また, 別解として, $S$ を逆順にした $\overline{S}$ において, ${\tt 6}$ と ${\tt 9}$ を交換する方法もある.

##<font color=#808080> C問題 (300pts, diff: 204) </font> [Made Up](https://atcoder.jp/contests/abc202/tasks/abc202_c)
$A, B, C$ を写像と見なす. 厳密には, 数列 $A$ と写像 $\alpha: [\\![N]\\!] \to [\\![N]\\!]; i \mapsto A_i$ を同一視する. $B, C$ についても同様である. このとき, 問題は以下のようになる.

> $D:=B \circ C$ (写像の合成) とする. このとき, $(i,j) \in [\\![N]\\!]^2$ のうち, $A(i)=D(j)$ を満たすのはいくつか?

ここで, 先に結論を言うと, 答えは, 写像 $A$ において, $A(i)=x$ を満たす $i$ の個数を $\alpha_x$, $D$ において, $A(j)=y$ を満たす $j$ の個数を $\delta_y$ とすると,
$$\sum_{z=1}^N \alpha_z \delta_z$$
である. 以下ではこれを証明する.

条件 $\mathcal{P}$ において,
$$[\mathcal{P}]:=\begin{cases} 1 & (\mathcal{P} が真のとき) \\\\ 0 & (\mathcal{P} が偽のとき) \end{cases} $$
とする. ここで, 2つの条件 $\mathcal{P}, \mathcal{Q}$ において,
$$[\mathcal{P} かつ \mathcal{Q}]=[\mathcal{P}][\mathcal{Q}]$$
が成り立つことに注意する. このとき, 答えを $X$ とすると,

```math
\begin{align*}
X
&=\sum_{i,j} [A(i)=D(j)] \\\\
&=\sum_{i,j} \sum_{z=1}^N [A(i)=D(j)=z] \\\\
&=\sum_{z=1}^N \sum_{i,j} [A(i)=D(j)=z] \\\\
&=\sum_{z=1}^N \sum_{i,j} [A(i)=z かつ D(j)=z] \\\\
&=\sum_{z=1}^N \sum_{i,j} [A(i)=z] [D(j)=z] \\\\
&=\sum_{z=1}^N \left(\sum_{i=1}^N [A(i)=z] \right) \left(\sum_{j=1}^N [D(j)=z] \right) \\\\
&=\sum_{z=1}^N \alpha_z \delta_z
\end{align*}
```
より, $X$ は上の式のように表せることが分かった.

##<font color=#008000> D問題 (400pts, diff: 966) </font> [aab aba baa](https://atcoder.jp/contests/abc202/tasks/abc202_d)

辞書式順序はとにかく前にある文字から見ていき, 決定した瞬間, それ以降の文字は影響を与えない. よって, 前から考えていく.

$T(\alpha,\beta,k)$ で ${\tt a}$ が $\alpha$ 個, ${\tt b}$ が $\beta$ 個からなる全ての文字列のうち, 辞書式順序 $k$ 番目ｎ文字列とする. ${\tt a}$ が $\alpha$ 個, ${\tt b}$ が $\beta$ 個からなる文字列のうち, 先頭が ${\tt a}$ であるものは, $\binom{\alpha+\beta-1}{\alpha-1}$ 個である. ここで, 辞書師順序において, 先頭が ${\tt a}$ である文字列は, どんな 先頭が ${\tt b}$ である文字列よりも前にくる. よって, 辞書式順序の最初の $\binom{\alpha+\beta-1}{\alpha-1}$ 個は先頭の文字が ${\tt a}$ であり, 残りについては先頭の文字が ${\tt b}$ であることがわかる. そして, 次の文字の判定に進むことができる.

以上から, 以下のように $T(\alpha, \beta, k)$ を計算することで, 正解の文字列 $T(A,B,K)$ を求めることができる.

* $\alpha=\beta=0$ のとき, $T(\alpha, \beta, k)=\emptyset$ (空文字) である.
* $\binom{\alpha+\beta-1}{\alpha-1}<k$ ならば, (先頭の文字は ${\tt b}$ なので) $T(\alpha, \beta, k)={\tt b} \oplus T(\alpha, \beta-1, K-\binom{\alpha+\beta-1}{\alpha-1})$ である.
* $\binom{\alpha+\beta-1}{\alpha-1} \geq k$ ならば, (先頭の文字は ${\tt a}$ なので) $T(\alpha, \beta, k)={\tt a} \oplus T(\alpha-1, \beta-1, K)$ である.

二項係数 $\binom{n}{r}$ は $0 \leq r \leq n \leq A+B$ の範囲を前計算しておくことで, $T$ を再帰的に実装することで, 計算量 $O((A+B)^2)$ で求めることができる. なお, 再起ではなく ${\tt for}$ 文でも実装できる.

##<font color=#0000FF> E問題 (500pts, diff: 1638) </font> [Count Descendants](https://atcoder.jp/contests/abc202/tasks/abc202_e)

各クエリ $(D,U)$ の意味を理解する. それぞれの条件は以下のような意味を表す.

* 頂点 $u$ から根への最短パス上 (端点も含む) に頂点 $U$ が存在する. $\iff$ 頂点 $u$ は頂点 $U$ の子孫である.
* 頂点 $u$ から根への最短パスに含まれる辺の数が<b>ちょうど</b> $D$ である. $\iff$ 頂点 $u$ の深さは $D$ である.

よって, クエリ $(D,U)$ は, $U$ の子孫で深さ $D$ の頂点はいくつか? を問うていることがわかった.

この換言したクエリを求めることを考える. このとき, 木を巡回する Euler Tour を考える. ここで, Euler Tour とは, 根付き木における深さ優先探索を行った際に訪れた頂点の履歴を記録したものである. 以下 根付き木における Euler Tour $E$ を
$$E: v_0 v_1 \dots v_{2(N-1)-1} v_{2(N-1)}$$
とする. なお, $v_0=v_{2(N-1)}=1$ である. また, 各頂点 $w$ に対して, $t^+_w, t^-_w$ を
$$t^+_w:=\min \\{t \mid v_t=w \\}, \quad t^-_w:=\max \\{t \mid v_t=w \\}$$
とする. この $t^\pm_w$ はそれぞれ, DFS において, 操作の対象を表すポインタが頂点 $w$ に 入った (出た) 時刻を表す.

ここで, この Euler Tour について, 以下の重大な事実がある.
> 頂点 $x$ は頂点 $y$ の子孫である. $\iff t^+_y \leq t^+_x \leq t^-_y$

この事実から, 各クエリの答えは, 深さが $D$ で, $t^+_U \leq t^+_w \leq t^-_U$ を満たす頂点 $w$ の個数である.

実装の手順としては, 前計算として, 深さ $d$ の全ての頂点 $w$ における $t^+_w$ を記憶し (そして, ソートし) たリスト $L_d$ を用意する. 本計算では, クエリ $(U,D)$ が来るたびに, $L_d$ の要素 $a$ で, $t^+_U \leq a \leq t^-_U$ を満たす個数を二分探索を行うことで, 1クエリあたり $O(\log N)$ , 全体では $O(Q \log N)$ で求めることができる.


##<font color=#FF0000> F問題 (600pts, diff: 2905) </font> [Integer Convex Hull](https://atcoder.jp/contests/abc202/tasks/abc202_f)
(正解でき次第更新予定)