AtCoder Beginner Contest 187 感想

##総合結果
* [Score] 1500 pts
* [Time] 35:10+<font color="red"> 05:00 $\times$ 0</font>=35:10
* [Ranking] 476 th
* [Performance] <font color=#0000FF> 1832　</font>
* [Rating] <font color=#0000FF> 1750 </font> →  <font color=#0000FF> 1759 </font> (+9)

##各問題ごとの詳細
* <font color="gray"> A問題 </font> 01:02
* <font color="gray"> B問題 </font> 04:06
* <font color="gray"> C問題 </font> 08:22
* <font color=#804000> D問題 </font> 14:52 
* <font color=#00C0C0> E問題 </font> 35:10
* <font color=#0000FF> F問題 </font> --:--


##提出コード (コンテスト後提出含む)
* <font color="gray"> A問題 </font> [■](https://atcoder.jp/contests/abc187/submissions/19117263)
* <font color="gray"> B問題 </font> [■](https://atcoder.jp/contests/abc187/submissions/19121610)
* <font color="gray"> C問題 </font> [■](https://atcoder.jp/contests/abc187/submissions/19169603)
* <font color=#804000> D問題 </font> [■](https://atcoder.jp/contests/abc187/submissions/19169627)
* <font color=#00C0C0> E問題 </font> [■](https://atcoder.jp/contests/abc187/submissions/19169173)
* <font color=#0000FF> F問題 </font> [■](https://atcoder.jp/contests/abc187/submissions/19169053)


#問題ごとの略解
##<font color="gray"> A問題 (100pts, diff:8) </font> [Large Digits](https://atcoder.jp/contests/abc187/tasks/abc187_a)

$S(X)$ は以下の様にして再帰的に求めることができる.

$$S(X)=\\begin{cases} S\left(\left \lfloor \frac{X}{10} \right \rfloor \right) + (X {\rm ~mod~} 10) && (X \geq 10) \\\\ X && (X<10) \\end{cases}$$

よって, $\max(S(A),S(B))$ を出力すればよい.

##<font color="gray"> B問題 (200pts, diff:68) </font> [Gentle Pairs](https://atcoder.jp/contests/abc187/tasks/abc187_b)

2点 $P_i=(X_i,Y_i), P_j=(X_j,Y_j)$ を通る直線の傾き $m_{i,j}$ は

$$m_{i,j}=\dfrac{Y_j-Y_i}{X_j-X_i}$$

なので, $-1 \leq m_{i,j} \leq 1$ を満たす $i,j~(i<j)$ の個数を愚直に数え上げればいい. なお,

$$-1 \leq m_{i,j} \leq 1 \iff -|X_j-X_i| \leq Y_j-Y_i \leq |X_j-X_i|$$

であるが, 必要ならば, $X_1 \leq \dots \leq X_N$ となるようにソートすれば絶対値が外れ, 実装が少し楽になる.

##<font color="gray"> C問題 (300pts, diff:207) </font> [1-SAT](https://atcoder.jp/contests/abc187/tasks/abc187_c)

以下, 先頭の文字が ${\tt !}$ である文字列に対して, $\overline{T}$ で $T$ から ${\tt !}$ を除いた文字列とする.[^1] このとき, 文字列 $S_1, \dots, S_N$ に対して, 以下の処理を順々に実行していく
.

* $i=1, \dots, N$ に対して, $F_{S_i,0}=F_{S_i,1}=0$ または $F_{\overline{S_i},0}=F_{\overline{S_i},1}=0$ とする.
* $j=1, \dots, N$ に対して, 以下を実行する.
    * $S_i$ の先頭の文字が ${\tt !}$ 以外のとき, $F_{S,0}=1$ とする.
    * $S_i$ の先頭の文字が ${\tt !}$ とき, $F_{\overline{S},1}=1$ とする.
* $F_{S,0}=F_{S,1}=1$ となる文字列 $S$ が存在すれば, この文字列 $S$ を出力すればよい. 存在しなければ, ${\tt satisfiable}$ を出力すればよい.

[^1]: 例: $T={\tt !atcoder}$ のとき, $\overline{T}={\tt atcoder}$

##<font color=#804000> D問題 (400pts, diff:650) </font> [Choose Me](https://atcoder.jp/contests/abc187/tasks/abc187_d)

町 $i$ で演説を行った際に高橋氏と青木氏の間で縮まる票数を $\Delta_i$ とする. 町 $i$ で演説すると, 青木氏に投票されるはずだった $A_i$ 票が消え, 新たに $A_i+B_i$ 票が高橋氏に投票されるので, $\Delta_i=2A_i+B_i$ である.

高橋氏が演説を全くしなかった場合, 青木氏が $\sum_{i=1}^N A_i$ 票だけ優勢である. よって, $\Delta_1,\dots, \Delta_N$ を降順に並べた $\Delta_{\alpha_1},\dots,\Delta_{\alpha_N}$ に対して,

$$\sum_{k=1}^K \Delta_{\alpha_k} > \sum_{i=1}^N A_i$$

を満たす最小の $K$ が答えである. これはソートがボトルネックになるが, 計算量 $O(N \log N)$ で求めることができる.
##<font color=#00C0C0> E問題 (500pts, diff:1358) </font> [Through Path](https://atcoder.jp/contests/abc187/tasks/abc187_e)

問題の便宜上, 木は無向辺だが, 表示の方法において, 頂点 $a,b$ を結ぶ辺を $(a,b)$ と書き,  $(a,b),(b,a)$ は異なる辺を表すとする. 各クエリについて, 以下うち一方のみが成立する.

* 「頂点 $v$ の子孫 [^2] 全てに $c$ を加える.」と同等となるような頂点 $v$ が存在する.
* 「頂点 $w$ の子孫以外全てに $c$ を加える.」と同等となるような頂点 $w$ が存在する.

###証明
$t=1$ の場合のみを考え, $e=(a,b)$ とする. なお, $t=2$ のときも同様である.

頂点 ${\rm root}$ を根とする根付き木 $T$ について, 頂点 $v$ の深さを ${\rm depth}_T (v)$ とする. このとき, ${\rm depth}\_T(a)<{\rm depth}\_T(b)$ または ${\rm depth}\_T(a)>{\rm depth}\_T(b)$ が成立する [^3] .

* ${\rm depth}\_T(a)>{\rm depth}\_T(b)$ のとき: 頂点 $a$ は頂点 $b$ の親である. 従って,
$$頂点 w が 頂点 b を通らずに到達可能 \iff 頂点 w は頂点 a の子孫$$
が成立する. 従って, 「頂点 $a$ の子孫全てに $c$ を加える」 と同等である.

* ${\rm depth}\_T(a)<{\rm depth}\_T(b)$ のとき: 頂点 $b$ は頂点 $a$ の親である. このとき,
$$頂点 w が 頂点 b を通らずに到達可能 \iff 頂点 w は頂点 b の子孫ではない$$
が成立する. 従って, 「頂点 $b$ の子孫全てに $c$ を加える」 と同等である.

ここで, 「頂点 $b$ の子孫全てに $c$ を加える」は以下の2つことを実行することと同等である.

* 「頂点 ${\rm root}$ の子孫全て [^4] に $c$ を加える.」
* 「頂点 $b$ の子孫全てに $-c$ を加える.」

よって, 「頂点 $v$ の子孫全てに $c$ を加える.」をどの様に処理すればよいかを考えれば良い.

全ての項が $0$ に初期化された数列 $X=(X_v)\_{v=1}^N$ について, 「頂点 $v$ の子孫全てに $c$ を加える.」 の度に, $X_v$ に $c$ を加算する. そして, 全Query終了後, 以下の様にして出力すべき値 $Y=(Y_v)\_{v=1}^N$ が分かる. ただし, 根でない頂点 $v$ に対して, $v'$ で 頂点 $v$ の親を表すとする. 

$$Y_v=\begin{cases} X_v & (v={\rm root}) \\\\ X_v+Y_{v'} & (v \neq {\rm root}) \end{cases}$$

なお, この $(Y_v)$ は ${\rm depth}_T(v)$ が小さい順に計算しなければならない.
[^2]: 頂点 $v$ は頂点 $v$ の子孫であることに注意.
[^3]: 実際には, もっと強く $|{\rm depth}\_T(a)-{\rm depth}\_T(b)|=1$ が成立する.
[^4]: 要は全頂点

##<font color=#0000FF> F問題 (600pts, diff:1895) </font> [Close Group](https://atcoder.jp/contests/abc187/tasks/abc187_f)

与えられたグラフを $G$ とする. $[\\![N]\\!]:=\\{1, 2, \dots, N\\}$ とし, $S \subset [\\![N]\\!]$ に対して, ${\rm DP}[S]$ を
$${\rm DP}[S]:=Sから誘導される部分グラフG[S]に関する問題の答え$$
とする. ここで, $G[S]$ が完全グラフならば, ${\rm DP}[S]=1$ であることは自明である[^5].以下, $G[S]$ が完全グラフでないとする. このとき, ある $S$ の部分集合 $T (\neq \emptyset,S)$ で 
$${\rm DP}[S]={\rm DP}[T]+{\rm DP}[S \setminus T]$$
となるものが存在する. このとき, ${\rm DP}[S]$ は以下の様にして求めることができる.
$${\rm DP}[S]=\min_{\substack{T \subset S\\\\ T \neq \emptyset,S}} \left({\rm DP}[T]+{\rm DP}[S \setminus T] \right)$$

ここで, $\min_{T \subset S} \cdot$ について, 計算量は二項定理から,
$$\sum_{S \subset [\\![N]\\!]} 2^{|S|}=\sum_{k=0}^N \dbinom{N}{k} 2^k=(1+2)^N=3^N$$
である. 

[^5]: $S=\emptyset$ のときもこのあとの解答の便宜上 ${\rm DP}[\emptyset]=1$ とする. 

#感想

##良かった点

* <font color=#808080>A問題</font>, <font color=#808080>B問題</font>, <font color=#808080>C問題</font>, <font color=#804000>D問題</font> をスピーディーに解くことができた.
* 久しぶりの<font color=#FF0000>No WA</font>

##反省点

* <font color=#0000FF>F問題</font> で下手な動的計画法を考え, 下手な実装をしてしまった.
* 集合とBit演算の関係性の理解が足りなかった.

#その他
第2期 AtCoder Beginner Contest Tournament C1ブロックのクウォーターファイナルを達成し, ベスト4になりました.