#総合結果
- [Score] 1500 pts
- [Time] 44:37 + 05:00 $\times$ 0 = 44:37
- [Ranking] 805 th [Rated内: 622 nd]
- [Performance] 1587
- [Rating] 1946 → 1914 (-32)
##各問題ごとの詳細, 提出コード
| Question | Score | Time/Result | Penalty | During Contest | After Contest |
|---|---|---|---|---|---|
| A問題 | 100 pts | 01:08 | ■ | ||
| B問題 | 200 pts | 02:47 | ■ | ||
| C問題 | 300 pts | 05:49 | ■ | ||
| D問題 | 400 pts | 09:45 | ■ | ||
| E問題 | 0 pts | --:-- | ■ | ||
| F問題 | 500 pts | 44:37 | ■ | ||
| G問題 | 0 pts | --:-- | |||
| H問題 | 0 pts | --:-- | |||
| Total | 1500 pts | 44:37 | No Penalties |
#問題ごとの感想
## A問題 (100pts, diff: 14) Find Multiple
$A$ 以上 $B$ 以下の $C$ の倍数を見つけるためには, いくつかの方法がある.
- $C \left \lceil \dfrac{A}{C} \right \rceil=C \left \lfloor \dfrac{A+C-1}{C} \right \rfloor$ が $A$ 以上の最小の $C$ の倍数である.
- $C \left \lfloor \dfrac{B}{C} \right \rfloor$ が $B$ 以上の最大の $C$ の倍数である.
- $x=A,A+1, \dots, B$ それぞれが $C$ の倍数かどうかを判定する.
## B問題 (200pts, diff: 58) Base K
$K$ 進表記で表された $x_0 \dots x_m$ が表す値 $X$ は以下のようにして求められる.
- $X \gets 0$
- $i=0,1, \dots, m$ の順に以下を実行する.
- $X \gets LX+x_i$
- $X$ を出力する.
## C問題 (300pts, diff: 119) Long Sequence
数列 $B$ の連続する $N$ 項の和は, $\alpha:=\sum_{i=1}^N A_i$ であることから, $q:=\left \lfloor \dfrac{X}{\alpha} \right \rfloor$ とすると, 答え $K$ は $qN < K \leq (q+1)N$ を満たすことがわかる. よって, $N \leq 10^5$ なので, $\beta \gets q \alpha$ として, $\beta$ に $A_i$ を足しながら, $qN+i$ が答えかどうかを順々にみれば, 計算量 $O(N)$ で求められる.
## D問題 (400pts, diff: 644) FG operation
動的計画法で求める. ${\rm DP}[i][a]$ で, $i$ 回操作した結果, 先頭の項が $a$ であるような操作の数とする. このとき, ${\rm DP}[N-1][K]~(K=0, \dots, 9)$ が求めるべき解である.
- $i=0$ のとき, 操作はしないので, 結果は元の列に一致する. よって,
$${\rm DP}[0][a]=\begin{cases} 1 & (a=A_1) \\ 0 & (a \neq A_1) \end{cases}$$
- $1 \leq i \leq N-1$ のとき, $i-1$ 回の操作で, 先頭の項が $b$ になったとする. このとき, 操作 $F$ , 操作 $G$ それぞれを考えることにより,
$${\rm DP}[i][(b+A_{i+1}) \bmod{10}] \quad (\because F), \quad {\rm DP}[i][(bA_{i+1})] \bmod{10}] \quad (\because G)$$
に ${\rm DP}[i-1][b]$ を足すことになる.
この動的計画法により, 計算量 $O(N)$ で求めることができる.
## E問題 (500pts, diff: 1593) Distance on Large Perfect Binary Tree
※制約上ありえないが, $D=0$ のときも言及する (答えは $2^N-1$ であるが) .
まず, $T_n$ で深さが $n$ の完全二分木とする. このとき, 以下のような特徴がある.
- $T_n$ にある深さ $k~(0 \leq k \leq n)$ の頂点のは $2^k$ 個ある.
- $T_n$ は2つの $T_{n-1}$ の根を共に新たな頂点で結んだ木である.
ここで, $T_{N-1}$ 上での2点間の距離の最大値は $2(N-1)$ なので, $2(N-1)<D$ のときは直ちに解答を $0$ と求められる. 以下 $2(N-1) \leq D$ とする.
全ての頂点対を最小共通先祖 (LCA) で場合分けする. このとき, 対称性から, ある深さ $k$ の頂点において, その頂点を根とする部分木に制限したときの距離 $D$ の点対の個数を $X_k$ とすると, 求めるべき答えは
$$\sum_{k=0}^{N-1} 2^k X_k$$
である. 以下, $X_k$ を求める.
$X_k$ は $T_{N-1-k}$ に同型である. 今, 最小共通先祖が根なので, 選べる頂点の対 $(u,v)$ は以下のうちのどれかが成立するような選ぶ方になる.
- $u,v$ のうち, 少なくとも一方が根
- 根が結ぶ2つの部分木をそれぞれ左, 右と呼ぶことにすると, $u$ は左, $v$ は右の頂点 (またはその逆).
場合分けする. ここで, $\mu:=N-1-k$ とし, $\mu$ は頂点が深さの最大値である.
- $u$ が根のとき, $0 \leq D \leq \mu$ ならば, $v$ として深さが $D$ となる頂点を選ぶことで最小共通先祖が根で, $\operatorname{dis}(u,v)=D$ になることができる. $\mu < D$ のときはこの条件下では$\operatorname{dis}(u,v)=D$ にすることができない. 深さ $D$ の頂点は $2^D$ 個あり, $v$ が根のときも合わせて, このパターンでは
$$\begin{cases} 1 & (D=0) \\ 2 \times 2^D & (1 \leq D \leq \mu) \\ 0 & (\mu < D) \end{cases}$$
となる.
- $u$ が右, $v$ が左のとき, $T_\mu$ における $u,v$ の深さの和と $\operatorname{dis}(u,v)$ は一致する.
- $u \neq v$ が確定しているので, このパターンで $D=0$ とはならない.
- $1 \leq D \leq \mu$ のとき, $u,v$ の深さの組として可能なのは, $(1,D-1), \dots, (D-1, 1)$ の $D-1$ 通りである.
- $\mu < D \leq 2\mu$ のとき, $u,v$ の深さの組として可能なのは, $(D-\mu,\mu), \dots, (\mu, D-\mu)$ の $2\mu-D+1$ 通りである.
- $T_\mu$ における $u,v$ の深さは $\mu$ 以下なので, $2\mu <D$ とはなりえない.
ここで, 右左の区別があり, 2つの深さの組が $i,j$ となるような頂点の選び方は $2^{i-1} \times 2^{j-1}=2^{i+j-2}$ であり, 今 $i+j=D$ となるようにしているので, $2^{D-2}$ 通りである.
このことから, $u,v$ の頂点の役割を交換することも考慮して, このパターンでは,
$$\begin{cases} 0 & (D=0) \\ 2 \times 2^D (D-1) & (0 < D \leq \mu) \\ 2 \times 2^{D-2} & (2 \mu-D+1) \\ 0 & (2 \mu <D) \end{cases}$$
である. 以上の2パターンを合わせることにより, $\mu_k:=N-1-k$ として,
$$X_k=\begin{cases} 1 & (D=0) \\ 2 \times (2^{D-2}(D-1)+2^D) & (0 < D \leq \mu) \\ 2 \times 2^{D-2}(2 \mu-D+1) & (\mu < D \leq 2\mu) \\ 0 & (2 \mu < D) \end{cases}$$
となる.
よって, $k=0,1,\dots, 2(N-1)$ に対して, $2^k$ を前計算すことにより, 各 $X_k$ を $O(1)$ で求められので, $\displaystyle \sum_{k=0}^{N-1} 2^k X_k$ を $O(N)$ で求めることができる.
## F問題 (500pts, diff: 1304) Distance Sums 2
$X_i:=\sum_{j=1}^N \operatorname{dis}(i,j)$ とする. ここで, 与えられる木 $T$ を適当な頂点 ${\rm root}$ を根とする根付き木とみなす.
まず, $X_{\operatorname{root}}$ は以下のようにして求められる.
頂点 $v$ の $T$ における深さを $\operatorname{depth}_T(v)$ とすると,
$$\displaystyle X_{\rm root}=\sum_{v=1}^N \operatorname{depth}_T(v)$$
である.
この $X_{\operatorname{root}}$ を利用して残りを求めることにする.
根でない頂点 $v$ の親を $w$ とし, $X_w$ が既に求まっているとする. このとき, $v$ の子孫の集合を $S_v$ とすると,
$$\operatorname{dis}(v,u)=\begin{cases} \operatorname{dis}(w,u)-1 & (u \in S_v) \\ \operatorname{dis}(w,u)+1 & (u \not \in S_v) \end{cases}$$
である. よって,
\begin{align*}
X_v
&=\sum_{u=1}^N \operatorname{dis}(v,u) \\\\
&=\sum_{u \in S_v} (\operatorname{dis}(w,u)-1)+\sum_{u \not \in S_v} (\operatorname{dis}(w,u)+1) \\\\
&=\sum_{u=1}^N \operatorname{dis}(w,u)-|S_v|+(N-|S_v|) \\\\
&=X_w+N-2|S_v|
\end{align*}
である. ここで, $|S_v|$ は頂点 $v$ の子孫の個数であるが, これは以下の漸化式を葉から計算することで求めることができる. ただし, ${\rm ch}(v)$ で頂点 $v$ の子とする.
$$|S_v|=\sum_{a \in {\rm ch}(v)} |S_a|+1$$
この $|S_v|$ の情報と, $X_{\rm root}$ から, 深さが小さい順に全ての $X_{\bullet}$ を求めることができる. 計算量は $O(N)$ である.
## G問題 (600pts, diff: 2439) Isosceles Trapezium
(正解でき次第加筆予定)
## H問題 (600pts, diff: 3047) Security Camera
(正解でき次第加筆予定)