マイナビプログラミングコンテスト2021 (AtCoder Beginner Contest 201) 感想

#総合結果
* [Score] 1500 pts
* [Time] 50:53 + <font color="red"> 05:00 $\times$ 0 </font> = 50:53
* [Ranking] 200 th [Rated内: 62 nd]
* [Performance] <font color=#C0C000> 2274　</font>
* [Rating] <font color=#0000FF> 1972 </font> → <font color=#C0C000> 2006 </font> (+34) (Highest!!) (<font color=#C0C000> Yellow in !! </font>)

##各問題ごとの詳細, 提出コード
|Question|Score|Time/Result|Penalty|During Contest|After Contest|
|:--:|--:|:--:|:--:|:--:|:--:|
|<font color=#808080> A問題 </font>|100 pts|02:05|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc201/submissions/22597661)||
|<font color=#808080> B問題 </font>|200 pts|03:38|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc201/submissions/22600492)||
|<font color=#804000> C問題 </font>|300 pts|06:36|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc201/submissions/22600492)||
|<font color=#00C0C0> D問題 </font>|400 pts|16:51<font color="red"> </font>||[■](https://atcoder.jp/contests/abc201/submissions/22611678)||
|<font color=#0000FF> E問題 </font>|500 pts|<b>50:53</b>|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc201/submissions/22622434)||
|<font color=#FF8000> F問題 </font>|0 pts|--:--|<font color="red"> </font>|||
|<b>Total</b>|<b>1500 pts</b>|<b>50:53</b>|<b><font color="red"> No Penalties </font></b>|||

#問題ごとの略解
##<font color=#808080> A問題 (100pts, diff: 12) </font> [Tiny Arithmetic Sequence](https://atcoder.jp/contests/abc201/tasks/abc201_a)

一般的に, 3項からなる数列 $(X,Y,Z)$ が等差数列になるための必要十分条件は $Y-X=Z-Y$ であるが, これを変形すると, $X+Z=2Y$ である. つまり, $(両端の和)=2 \times (中央の項)$ である.

このとき, 並び替えて中央になりうるのは3通りであることに注意すると,
$$A_1+A_2=2A_3, \quad A_2+A_3=2A_1, \quad A_3+A_1=2A_2$$
のうち, 少なくとも1つが成り立てば ${\tt Yes}$, 1つも成り立たなければ ${\tt No}$ である.

##<font color=#808080> B問題 (200pts, diff: 32) </font> [Do you know the second highest mountain?](https://atcoder.jp/contests/abc201/tasks/abc201_d)

各入力 $S_i, T_i$ について, タプル $(T_i, S_i)$ を生成する. そして, $N$ 個のタプルからなるリスト $L=[(T_1, S_1), \dots, (T_N, S_N)]$ を辞書式降順にソートした結果を $L'=[(T_1', S_1'), \dots, (T_N', S_N')]$ としたとき, 答えは $S_2'$ である.

##<font color=#804000> C問題 (300pts, diff: 439) </font> [Secret Number](https://atcoder.jp/contests/abc201/tasks/abc201_c)

暗証番号につかえる文字は $0$ ~ $9$ の $10$ 種類で, $4$ 桁なので, 可能性としては $10^4$ 通りである. よって, $10^4$ 個の可能性すべてについて, その暗証番号が条件を満たすかどうかを試せば良い. ただし, 実装について, ${\tt o}$ の条件に注意しなければならない.

計算量は暗証番号に使える文字数を $K$, 桁を $d$ とすると, $O(dK^d)$ である,

##<font color=#00C0C0> D問題 (400pts, diff: 1317) </font> [Game in Momotetsu World](https://atcoder.jp/contests/abc201/tasks/abc201_d)

この問題は動的計画法で解く, ${\rm DP}[i,j]$ で, マス $(i,j)$ から初め, 2人が最善に動かしたとしたときの (先手の点数) $-$ (後手の点数) とする. これが計算できたとき,
$$\begin{cases} {\rm DP}[1,1]>0 \iff 高橋君の勝利 \\\\ {\rm DP}[1,1]=0 \iff 引き分け \\\\ {\rm DP}[1,1]<0 \iff 青木君の勝利 \end{cases}$$
である.

ここから, ${\rm DP}[i,j]$ を求める. まず, ベースケースとして, 一番右下のときは動かせないので, 両者ともに0点である. よって, ${\rm DP}[H,W]=0$ である.

次に, 一般の $(i,j)$ についての ${\rm DP}[i,j]$ を考える. ここで, $P_{i,j}$ を
$$P\_{i,j}=\begin{cases} 1 & (A\_{i,j}={\tt +}) \\\\ -1 & (A\_{i,j}={\tt -}) \end{cases}$$

とし, $M_{i,j}$ で, マス $(i,j)$ から移動可能なマス全体の集合とする.

マス $(i,j)$ に駒があるとき, マス $(k,l)$ に動かしたとするときの最終的な結果を考える. まず, コマを $(k,l)$ に動かしたので, $P_{k,l}$ 点得る. その後, 相手は ${\rm DP}[k,l]$ を満たすような動きをする. このとき, ${\rm DP}$ の定義から, マス $(i,j)$ とマス $(k,l)$ から見た, 先手と後手は入れ替わっているので, 最終的な結果は $P_{k,l}-{\rm DP}[k,l]$ になる. ここで, コマを動かすプレイヤーは最適に動かすことから, この値を最大にしたい. よって,
$$\max\_{(k,l) \in M_{i,j}} \left(P_{k,l} - {\rm DP}[k,l] \right)$$
である. 

##<font color=#0000FF> E問題 (500pts, diff: 1694) </font> [Xor Distances](https://atcoder.jp/contests/abc201/tasks/abc201_e)

まず, 木を ${\rm root}$ を根とする根付き木とする. ここで, 重みの演算が普通の $+$ だったときに関して, 以下のような事実がある.
> 2つの頂点 $u,v$ において, 最小共通祖先 を $\operatorname{lca}(u,v)$ と書き, 頂点 $v$ における根からの距離 (深さ) を $\operatorname{depth}(v)$ と書くことにする. このとき, 2頂点 $u,v$ 間の距離 $\operatorname{dist}(u,v)$ について,
> $$\operatorname{dist}(u,v)=\operatorname{depth}(u)+\operatorname{depth}(v)-2\operatorname{depth}(\operatorname{lca}(u,v))$$
> が成り立つ.

ここで, この問題の演算は XOR であることに注意する. よって, XOR に関する演算で加法と減法にあたるものをそれぞれ $\oplus, \ominus$ とすると, XOR は可換であることから, 上と同様にして,
$$\operatorname{dist}(u,v)=\operatorname{depth}(u) \oplus \operatorname{depth}(v) \ominus 2\operatorname{depth}(\operatorname{lca}(u,v))$$
が成り立つ.[^e1]

ここで, まず $\ominus$ について考える. さて, XOR に関して, 以下の様な性質がある.
> 任意の整数 $a$ に対して, $a \oplus a=0$ である.

この性質から, $a$ の XOR におけるマイナス元は $a$ 自信である. また, $b$ を引くということは, $b$ のマイナス元を足すということなので, 上の式は

$$\operatorname{dist}(u,v)=\operatorname{depth}(u) \oplus \operatorname{depth}(v) \oplus 2\operatorname{depth}(\operatorname{lca}(u,v))$$

になる.

次に, $2\operatorname{depth}(\operatorname{lca}(u,v))$ の $2$ について考える. ここで, $x \oplus 2a$ を $x \oplus 2a=x \oplus a \oplus a$ と考えると, 上で述べた性質から, $x \oplus 2a=x$ である. よって,

$$\operatorname{dist}(u,v)=\operatorname{depth}(u) \oplus \operatorname{depth}(v)$$

となる.

よって, $\operatorname{depth}(v)$ (XOR の意味での) を求めることができれば, $\operatorname{dist}(u,v)$ を容易に求めることができることがわかった. 次に, 和を求める.

ここで, XOR はbit毎に連続であることに注目すると, 各辺の重みは $0$ または $1$ のときのみを考慮して考えてもよいことがわかる. 以下, このようにする.

このとき, 
$$\operatorname{dist}(u,v)=1 \iff (\operatorname{depth}(u),\operatorname{depth}(v))=(1,0) \{\rm ~or~} (0,1)$$
である. よって, 2つの頂点の$\operatorname{depth}$ が異なるときのみ, 和に $1$ 貢献することから, $\operatorname{dist}(u)=0,1$ なる頂点の個数を $E_0, E_1$ とすると,
$$\sum_{1 \leq u < v \leq N} \operatorname{dist}(u,v)=E_0 E_1=E_1(N-E_1)$$

である. 

今は重みが $0$ or $1$ のときのみに制限したが, 一般的な場合を考える. このときは各bit毎に上とほとんど同じ議論を行い, 最終的にbit倍したものが答えになる. 数式であらわすと, 頂点 $v$ のうち, ${\operatorname{depth}(v)}$ の $i$ -th bit が立っている頂点の個数を $F_i$ とすると, 答えは
$$\sum_{i=0}^\infty 2^i F_i(N-F_i)$$
である. ただし, $\infty$ については, 制約より, 各辺の重みが $2^{60}$ 未満なので, $\infty$ は $59$ に置き換えてもよい.

計算量は $\operatorname{depth}(v)$ を求めるために木DPを用いるパート, そして $F_k$ を求めるパートそれぞれで $O(N \log \max W)$ で求めることができる.
 
[^e1]: ここで登場する $2$ の意味については後ほど.
##<font color=#FF8000> F問題 (600pts, diff: 2484) </font> [Insertion Sort](https://atcoder.jp/contests/abc201/tasks/abc201_f)

(正解でき次第更新予定)

#感想

##総評
先週は参戦できなかった影響により, 2週間ぶりのコンテストになった. <font color=#0000FF> E問題 </font>の diff が<font color=#0000FF> 青 </font>にしては易しく, 次の<font color=#FF8000> F問題 </font> が難しかったことから, <font color=#C0C000> 黄色 </font> を狙うには, <font color=#0000FF> E問題 </font> までの早解きが必須であった.

##良かった点
* <font color=#0000FF> E問題 </font> の理論をある程度はやく求めることができた.

##反省点
* <font color=#808080> A問題 </font> が普段に比べると遅い.
* <font color=#0000FF> E問題 </font> の実装ミス ($\infty$ の値を $\log \max W$ にすべきところを, $\log W_{N-1}$ にしてしまった) .

## お知らせ
このコンテストをもって, <font color=#C0C000> 黄色コーダー </font> になりました.