AtCoder Beginner Contest 208 感想

# 総合結果
* [Score] 1500 pts
* [Time] 88:42 + <font color="red"> 05:00 $\times$ 1 </font> = 93:42
* [Ranking] 240 th [Rated内: 134 th]
* [Performance] <font color=#C0C000> 2077　</font>
* [Rating] <font color=#0000FF> 1891 </font> → <font color=#0000FF> 1911 </font> (+20)

## 各問題ごとの詳細, 提出コード
|Question|Score|Time/Result|Penalty|During Contest|After Contest|
|:--:|--:|:--:|:--:|:--:|:--:|
|<font color=#808080> A問題 </font>|100 pts|01:05|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc208/submissions/23948904)||
|<font color=#808080> B問題 </font>|200 pts|03:22|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc208/submissions/23953897)||
|<font color=#808080> C問題 </font>|300 pts|06:18|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc208/submissions/23957883)||
|<font color=#008000> D問題 </font>|400 pts|12:23|<font color="red"> </font>|[■](https://atcoder.jp/contests/abc208/submissions/23963641)||
|<font color=#C0C000> E問題 </font>|500 pts|<b>88:42</b>|<font color="red"> 1 Penalty </font>|[■](https://atcoder.jp/contests/abc208/submissions/23986891)<br>(上から見る)|[■](https://atcoder.jp/contests/abc208/submissions/24010552)<br>(下から見る)|
|<font color=#FF8000> F問題 </font>|0 pts|--:--|<font color="red"> </font>||[■](https://atcoder.jp/contests/abc208/submissions/24016558)|
|<b>Total</b>|<b>1500 pts</b>|<b>88:42</b>|<b><font color="red"> 1 Penalty </font></b>|||

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

$6$ 面サイコロを $A$ 個振って, 出目の和がちょうど $B$ 以上になることがありうるための必要十分条件は, $A \leq B \leq 6A$ である. よって, 整数 $A,B$ を受け取り, $A \leq B \leq 6A$ かどうかを判定すれば良い.

## <font color=#808080> B問題 (200pts, diff: 51) </font> [Factorial Yen Coin](https://atcoder.jp/contests/abc208/tasks/abc208_b)

今回の問題で使われる貨幣の額について, $1!,2!, \dots, 10!$ であることから, 以下の事実が成り立つ.

> 貨幣の額が $A_1,A_2, \dots, A_N$ であるとする. 任意の $k$ について, $A_1 | A_2 | \dots | A_N$ が成り立つならば, 使う貨幣の枚数を最小にするためには上から貪欲にすればよい.

実際, $1!|2!|3!|\dots|10!$ が成り立つので, $10!, \dots, 1!$ 円貨幣の順に貪欲に使う枚数を調べれば良い.

## <font color=#808080> C問題 (300pts, diff: 142) </font> [Fair Candy Distribution](https://atcoder.jp/contests/abc208/tasks/abc208_c)

お菓子の配り方について, 観察してみると, 以下のことがわかる. ただし, $K$ を $N$ で割った商と余りをそれぞれ $q,r$ とする.

* 国民番号が小さい方から $r$ 番目以下ならば, お菓子を $q+1$ 個もらえる.
* 国民番号が小さい方から $r$ 番目以下でなければ, お菓子を $q$ 個もらえる.

よって, $N$ 人の国民番号を集めた配列 $A=[a_1, \dots, a_N]$ を昇順 (小さい整数から大きい整数) へ並び替えた配列 $A'=[a'_1, \dots, a'_r]$ において,

$$国民番号 x が小さい方からr番目以下 \iff x \leq a'_r$$

となることを利用すると, 1人毎のお菓子の個数を $O(1)$ で求めることができる.

計算量は $A$ の昇順ソート $A'$ を求めるためにソートをするパートがボトルネックになり, $N$ 人の答えを $O(N \log N)$ で求めることができる[^c1].

[^c1]: $O(N)$ で求める方法もあるが, この問題では不要.

## <font color=#008000> D問題 (400pts, diff: 1190) </font> [Shortest Path Queries 2](https://atcoder.jp/contests/abc208/tasks/abc208_d)

この問題では Warshall - Floyd 法の原理を理解しなければ正解を導き出すことが厳しくなる. そもそも, Warshall -Floyd 法とは以下のようなアルゴリズムである.

$g(s,t,k)$ を本問題のように, 頂点 $s,t,1,\dots,k$ のみを用いて到達可能な経路のうちの最短時間とする (ただし, 到達不能な場合は $g(s,t,k)=\infty$). まず, $g(s,t,0)$ は以下のようになる. ただし, 与えられるグラフを $D=(V:=[\\![N]\\!], A)$ とする.

$$g(s,t,0)=\begin{cases} 0 & (s=t) \\\\
\operatorname{cost}(st) & (s \neq t, st \in A) \\\\
\infty & (s \neq t, st \not \in A) \end{cases}$$

このとき, $g(s,t,k)$ を求める. $s$ から $t$ へ 頂点 $s,t,1, \dots, k$ のみを用いて到達可能な経路を以下の2つに場合分けする.

* (A): 頂点 $k$ を使わない経路
* (B): 頂点 $k$ を使う経路

それぞれの場合について考察する.

* (A): 頂点 $k$ を使わない経路について<br>
このような経路は, 頂点 $s,t,1, \dots, k-1$ のみを用いて到達可能であると見なせ, このような経路の内, 最短時間であるものは $g(s,t,k-1)$ である.
* (B): 頂点 $k$ を使う経路について<br>
このような経路について, 以下のようなパート分けをする.
    * (イ) 頂点 $s$ から頂点 $k$ へのパート
    * (ロ) 頂点 $k$ から頂点 $t$ へのパート

(イ)のパートについて, このような経路のうち, 最短時間であるものは $g(s,k,k)$ であるが, $f(\*,\*,\*)$ の定義によって, $g(s,k,k)=f(s,k,k-1)$ であることに注意せよ. 同様に, (ロ) のパートにおける最短時間は $g(k,t,k-1)$ である. また, (B) のような経路において, (イ) パートの経路と (ロ) パートの経路はそれぞれ独立に選ぶことができるので, (B) のような経路における最小時間は $g(s,k,k-1)+g(k,t,k-1)$ である.

以上の(A), (B) で全ての $s$ から $t$ へ到達可能な経路について調べたので, 

$$g(s,t,k)=\min(g(s,t,k-1), g(s,k,k-1)+g(k,t,k-1))$$

である. 

以上の漸化式と $g(s,t,0)$ の結果を利用することにより, $1 \leq s,t, \leq N, 1 \leq k \leq N$ なる全ての $g(s,t,k)$ を全体で $g(s,t,k)$ を時間計算量 $O(N^3)$ で求めることができ, この結果から

$$\sum_{\substack{1 \leq s,t \leq N \\\\ 1 \leq k \leq N \\\\ g(s,t,k) < \infty}} g(s,t,k)$$

が答えである.

---
### 補足
上での $g(s,t,N)$ が $s$ から $t$ への最短時間になっている. このようなアルゴリズムを Warshall - Floyd 法 といい, 時間計算量 $O(N^3)$ で全頂点間の最短時間 (距離) を求めることができる. このアルゴリズムは全頂点間について計算できること, 及び, 辺の数に時間計算量が依らないという特徴がある.

なお, 上の説明そのままに実装すると空間計算量 $O(N^3)$ だが, 実は以下のように実装することもでき, この場合空間計算量が $O(N^2)$ になる.

* $x(s,t)$ を以下のように初期化する.
$$x(s,t)=\begin{cases} 0 & (s=t) \\\\
\operatorname{cost}(st) & (s \neq t, st \in A) \\\\
\infty & (s \neq t, st \not \in A) \end{cases}$$
* $k=1, \dots, N$ に対して以下を実行する.
    * $s=1, \dots, t$ に対して以下を実行する.
        * $t=1, \dots, N$ に対して
            * $g(s,t)$ を $\min(g(s,t), g(s,k)+g(k,t))$ に更新する.
* このときの　$x(s,t)$ が答えである. 

## <font color=#C0C000> E問題 (500pts, diff: 2024) </font> [Digit Products](https://atcoder.jp/contests/abc208/tasks/abc208_e)

### 方針 I (上から見る)
$N$ 以下の正整数のうち, ある条件を満たす整数の個数を求める問題は 桁DP が有効である. そこで, 以下のようなDPが思いつく.

$${\rm DP}[i, {T/F}, a]:=(上から) i 桁目までみると, N 未満が確定 (する, しない) ような整数における桁積が a であるものの個数$$

しかし, この問題では $0$ の扱い leading-zero どうかで役割によって変わってしまう. この原因によって上の定義では遷移が難しくなってしまう. そこで, 以下のような leading-zero 付き桁 DP で考えていく.

$${\rm DP}[i][c][a]:=1 以上 N 以下の整数で状況が c (後述) であるものうち, 桁積がちょうど a であるような個数$$

とする. ここで, $c$ と状況については以下のように対応させる.

* $c=F$: 上から $i$ 桁目が $N$ と一致している.
* $c=T_0$: 上から $i$ 桁目までで $N$ 未満が確定しているが, 上から $i$ 桁目までが全て $0$ である.
* $c=T_1$: 上から $i$ 桁目までで $N$ 未満が確定しているが, 上から $i$ 桁目までに $0$ 以外が存在する.

以下, $N$ の上から $i$ 桁目の整数を $n_i$ と書くことにする.

まず, ${\rm DP}[1][c][a]$ について考える.

* $c=F$ のとき: $c=F$ となるような上 $1$ 桁のとり方は $n_1$ しか無い. よって,
 $${\rm DP}[1][F][a]=[a=n_1]=\begin{cases} 1 & (a=n_1) \\\\ 0 & (a \neq n_1) \end{cases}$$
* $c=T_0$ のとき: $c=T_0$ となるような上 $1$ 桁のとり方は leading-zero　に限る. leading-zero は桁積から無視することに注意すると,
 $${\rm DP}[1][T_0][a]=[a=1]=\begin{cases} 1 & (a=1) \\\\ 0 & (a \neq 1) \end{cases}$$
* $c=T_1$ のとき: $c=T_1$ となるような上 $1$ 桁のとり方は $1,2,\dots,n_1-1$ である. よって,
 $${\rm DP}[1][T_1][a]=[1 \leq a < n_1]=\begin{cases} 1 & (1 \leq a < n_1) \\\\ 0 & ({\rm otherwise}) \end{cases}$$

次に, ${\rm DP}[i-1][c][\*]$ から ${\rm DP}[i][c'][\*]$ への遷移が考えるが, 以下の3つの遷移は明らかに起きないことがわかる.
$$T_0 \to F, \quad T_1 \to F, \quad T_1 \to T_0$$
よって, 以下の $6$ パターンについての遷移を考える.

|$i-1$ \ $i$|$F$|$T_0$|$T_1$|
|:--:|:--:|:--:|:--:|
|$F$ (未満不確定)|(A)|(B)|(C)|
|$T_0$ (0オンリー)|$\times$|(D)|(E)|
|$T_1$ (未満,正が共に確定)|$\times$|$\times$|(F)|

* (A): $F \to F$<br> そもそも $c=F$ であるとき, 上から $i$ 桁は $n_1, \dots, n_i$ であることから,
 $${\rm DP}[i][F][a]=[a=n_1 \dots n_i]$$
である.
* (B): $F \to T_0$<br> $n_1 \neq 0$ であることから, $F$ から $T_0$ に遷移することはありえない.
* (C): $F \to T_1$<br> $F$ から $T_1$ に遷移するためには, 上から $i$ 桁目を $1,\dots,n_i-1$ にすればよい. よって, 以下のような寄与が発生する.
 $${\rm DP}[i][T_1][ma] に {\rm DP}[i][F][a] を足す (1 \leq m <n_i)$$
* (D): $T_0 \to T_0$<br> $T_0$ であるときは上から $i$ 桁全てが leading-zero なので,
 $${\rm DP}[1][T_0][a]=[a=1]$$
である.
* (E): $T_0 \to T_1$<br> 上から $i$ 桁目としては $1,2,\dots,10-1$ が可能である ($0$ にすると $T_0$ になってしまう). よって,
 $${\rm DP}[i][T_1][ma] に {\rm DP}[i][T_0][a] を足す (1 \leq m <10)$$
* (F): $T_1 \to T_1$<br> 上から $i$ 桁目としては $0,1, \dots, 10-1$ が可能である. よって,
 $${\rm DP}[i][T_1][ma] に {\rm DP}[i][T_1][a] を足す (0 \leq m < 10)$$

このようにして ${\rm DP}[i][c][a]$ を求め, $N$ が $d$ 桁のとき,

$$\sum_{a=1}^K {\rm DP}[d][F][a]+\sum_{a=1}^K {\rm DP}[d][T_1][a]$$

である (${\rm DP}[d][T_0][a]$ は0に関する情報なので除外). 

---
これで正解の値を求めることができたが, 計算量について考えなくてはならない.

まず, $a >K$ ならば, その後は $a=0$ になるが, $a>K$ のままかという状況しか発生しないので, $a>K$ の部分をまとめてしまっても問題ない.

次に, ${\rm DP}[i][c][\bullet]$ が非ゼロになる $a$ の個数を考える. $1,2,\dots,10-1$ のうち, 素因数分解した場合に出てくる素数は $2,3,5,7$ に限る. このことから, $a$ の個数としては

$$\log_2 K \log_3 K \log_5 K \log_7 K=O((\log K)^4)$$

程度である.

以上から, ${\rm DP}[i][c][\bullet]$ を辞書 (連想配列) で記録することにより, 10 - 進法の底を $B=10$ として, $O(B(\log K)^4 \log N)$ で求めることができた.

---
このように 桁DP でも leading-zero の役割が普通の 0 のときと変わってしまう場合, leading - zero 付き桁DPすることで楽に遷移を求めることができる.

leading - zero 付き桁DP の問題例:<br>[ABC 194 [F] Digits Paradise in Hexadecimal](https://atcoder.jp/contests/abc194/tasks/abc194_f)

↓解説 (私が書いた記事に飛びます)

https://qiita.com/Kazun_kyopro/items/1746a8c0aae7555e5a64#-f%E5%95%8F%E9%A1%8C-600pts-diff-2197-digits-paradise-in-hexadecimal

### 方針 II (下から見る)
$N, K$ のときの答えを $h(N,K)$ と書くことにする. また, $N$ を $10$ で割った商と余りをそれぞれ $q,r$ とする.

* $q=0$ のとき<br>これは $N <10$ を意味している. このとき, 1桁の整数の桁積はその整数なので, $h(N,K)=\min(N,K)$ である.
* $q>0$ のとき<br>$N \geq 10$ が確定する. このとき, $n<10$ のときと $n \geq 10$ のときで場合分けする.
    * $n<10$ のとき: 上の $q=0$ の場合と同様にして愚直に計算して $\min(10,K)$ 個であることがわかる.
    * $n \geq 10$ のとき: 下一桁の整数 $x$ で場合分けする.
        * $x=0$ のとき: この時点で桁積が $0$ であることが確定するので, $n=10, 20, \dots, 10q$ という $N$ 以下の $10$ の倍数全てが条件を満たす.
        * $1 \leq x \leq r$ のとき: 下2桁目以降の整数 $y$ として可能なのは, $y=1, \dots, q$ である. よって, $y$ として適切なのは, $h(q,\lfloor K/x \rfloor)$ である.
        * $r <  x <10$ のとき: 下2桁目以降の整数 $y$ として可能なのは, $y=1, \dots, q-1$ である. よって, $y$ として適切なのは, $h(q-1,\lfloor K/x \rfloor)$ である.

よって,
$$h(N,K)=\min(9,K)+q+\sum_{x=1}^r h(q,\left \lfloor \dfrac{K}{x} \right \rfloor)+\sum_{x=r+1}^9 h(q-1,\left \lfloor \dfrac{K}{x} \right \rfloor)$$
である. 計算量は商列挙の考え方から, $O(B \log N \sqrt{K})$ になる.

## <font color=#FF8000> F問題 (600pts, diff: 2772) </font>[Cumulative Sum](https://atcoder.jp/contests/abc208/tasks/abc208_f)

(2021/07/06 02:09 加筆)

有限列 $A=(A_i)\_{i=0}^L$ に対して, 作用素 $\mathcal{S}$ を $A$ の累積和を与える作用素とする. つまり, $\mathcal{S}(A)=(B_i)_{i=0}^L$ は

$$B_i=\sum_{j=0}^L A_j$$

である. また, $B_0=A_0, B_i=B_{i-1}+A_i~(i \geq 1)$ が成り立つ.

ここから, $f(n,m)$ について観察する.

* $m=0$ のとき<br>定義から, $f(n,m)=n^K$ である.
* $m \geq 1$ のとき<br> 実は, $f(n,m)=\mathcal{S}(f(n,m-1))_n$ が成り立ち, $f(n,m)$ は $f(n,m-1)$ の累積和になることがわかる. これは $f(0,m)=f(0,m-1)=0$ 及び, $f(n,m)=f(n-1,m)+f(n,m-1)$ という式から従う.

よって, $\mathcal{S}^m(A):=\underbrace{\mathcal{S}(\dots(\mathcal{S}}_{m}(A))\dots)$ とし, 列 $H=(n^K)\_n$ とすると, $f(n,m)=\mathcal{S}^m(H)$ が成り立つことがわかった.

---
ここで, 以下の事実が成り立つ.

1. 多項式 $P(n)$ が $d$ -次多項式ならば, 多項式 $\sum_{i=1}^n P(i)$ は $d+1$ -次多項式になる.
1. 高々 $d$ -次の多項式同士の和も高々 $d$ -次である.

このことから, 以下のことが成り立つ.
> $a_m(n):=f(n,m)$ とすると, $a_m$ は $m+K$ -次の多項式になる.
> (証明)
>
> * $m=0$ のとき $a_0(n)=f(n,0)=n^K$ は $K$ -次の多項式である.
> * $m$ のときに $a_m(n)$ が $m+K$ -次の多項式であったとする. $a_{m+1}(n)$ について,
> $a_{m+1}(n)=\sum_{i=0}^n a_m(i)$ であり, $a_m$ は $m+K$ -次の多項式なので, $a_{m+1}$ は $m+K+1$ -次の多項式である.

よって, $a_M$ は $M+K$ -次多項式になっている.

---
ここで, 多項式に関して, 以下のような重要な性質がある.

> $d+1$ 個の実数の組 $(x_0, y_0), \dots, (x_{d+1}, y_{d+1})~(i \neq j \Rightarrow x_i \neq x_j)$ が与えられている. このとき,
> $$P(x_0)=y_0, \dots, P(x_d)=y_d$$
> を満たすような高々 $d$ 次の多項式 $P$ が一意に存在する.

この存在証明は構成的であり, このような構成方法を Lagrange 補間という.

Lagrange 補間多項式 $L_i(x)~(i=0, \dots, d)$ を以下のように定める.

$$L_i(x)=\prod_{\substack{0 \leq j \leq d \\\\ i \neq j}} \dfrac{x-x_j}{x_i-x_j}$$

このとき, $L_i(x_j)=[i=j]$ であることに注意すると,

$$P(x)=\sum_{j=0}^d y_j L_j(x)$$

とすると, $L_j$ は定義から $d$ -次であるので, $P$ は高々 $d$ -次になる.

このようにして, $P$ を愚直に $O(d^2)$ で求めることができる.

---
Lagrange 補間を利用して, $f(N,M)=a_M(N)$ を求める. $a_M$ は $M+K$ 次であったことから, 異なる $M+K+1$ 個の非負整数 $x_0, \dots, x_{M+K+1}$ を選び, $y_i=a_M(i)$ を求めることによって, Lagrange 補間を利用して $a_M$ 及び $a_M(N)$ を求めることができる.

しかし, 愚直に求めると計算量が $O((M+K)^2)$ になり, 到底間に合わないので, 工夫することによって計算量を削減する.

---
$x_i$ の選び方を工夫する. $x_i=i$ とすることにより, Lagrange 補間多項式に $N$ を代入した $L_i(N)$ は

```math
\begin{align*}
L_i(N)
&=\prod_{\substack{0 \leq j \leq d \\\\ i \neq j}} \dfrac{N-j}{i-j} \\\\
&=\dfrac{(N-0)(N-1)\dots (N-(i-1))(N-(i+1)) \dots (N-d)}{(i-0)(i-1) \dots (i-(i-1))(i-(i+1)) \dots (i-d)} \\\\
&=\dfrac{\prod_{j=0}^{i-1} (N-j) \times \prod_{j=i+1}^d (N-j)}{i (i-1) \dots 1 \times (-1)(-2) \dots (-(d-i))} \\\\
&=\dfrac{\prod_{j=0}^{i-1} (N-j) \times \prod_{j=i+1}^d (N-j)}{i! (-1)^{d-i} (d-i)!} \\\\
&=(-1)^{d-i}\times \dfrac{\prod_{j=0}^{i-1} (N-j) \times \prod_{j=i+1}^d (N-j)}{i!(d-i)!}
\end{align*}
```

になる. ここで, 計算量の工夫のために, 左右それぞれからの累積積 ${\rm Left}_i, {\rm Right}_i$ を

$${\rm Left}\_0=N, \quad {\rm Left}\_i={\rm Left}\_{i-1} \times (N-i), \quad {\rm Right}\_d=N-d, \quad {\rm Right}\_i={\rm Right}\_{i+1} \times (N-i)$$

とすると,

$$L_i(N)=(-1)^{d-i}\times \dfrac{{\rm Left}\_{i-1} \times {\rm Right}\_{i+1}}{i!(d-i)!}$$

となり, 計算量の(定数倍での) 削減に成功する (${\rm Left}\_{-1}={\rm Right}_{d+1}=1$ とする).

よって, $(k!)^{-1} \pmod{10^9+7}$ を前計算で求めることにより, 各 $L_i(N)$ を $O(1)$ で求めることができる. また, $y_i=a_M(i)$ について, $a_m(n)=\mathcal{S}^m(H)$ であったことに注意すると, 愚直に $a_0(i)~(0 \leq i \leq M+K)$ を $O(K \log K)$, $a_1(i), \dots, a_M(i)$ を各 $a_j$ について $O(M+K)$, 合計 $O(M(M+K))$ で求めることができる.

以上から, $a_M(0), \dots, a_M(M+K)$ を $O(K \log K+M(M+K))$ で求め, Lagrange 補間多項式から $a_M(N)$ を $O(M+K)$ で求めることができ, 全体の計算量 $O(K \log K+M(M+K))$ で求まった.