総合結果

[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