SOMPO HD プログラミングコンテスト2021 (AtCoder Beginner Contest 192) 感想

#総合結果
* [Score] 1500 pts
* [Time] 41:27 + <font color="red"> 05:00 $\times$ 2 </font> = 51:27
* [Ranking] 682 nd [Rated内: 440 th]
* [Performance] <font color=#0000FF> 1764　</font>
* [Rating] <font color=#0000FF> 1845 </font> → <font color=#0000FF> 1837 </font> (-8)

##各問題ごとの詳細, 提出コード
|Question|Score|Time/Result|Penalty|During Contest|After Contest|
|:--:|:--:|:--:|:--:|:--:|:--:|
|<font color=#808080> A問題 </font>|100 pts|01:06|<font color="red">  </font>|[■](https://atcoder.jp/contests/abc192/submissions/20282709)||
|<font color=#808080> B問題 </font>|200 pts|06:02|<font color="red">  </font>|[■](https://atcoder.jp/contests/abc192/submissions/20291437)||
|<font color=#808080> C問題 </font>|300 pts|09:07|<font color="red">  </font>|[■](https://atcoder.jp/contests/abc192/submissions/20294755)||
|<font color=#00C0C0> D問題 </font>|400 pts|<b>41:27</b>|<font color="red"> 1 Penalty </font>|[■](https://atcoder.jp/contests/abc192/submissions/20312282)||
|<font color=#008000> E問題 </font>|500 pts|34:32|<font color="red"> 1 Penalty </font>|[■](https://atcoder.jp/contests/abc192/submissions/20309105)||
|<font color=#0000FF> F問題 </font>|0 pts|--:--|<font color="red"> </font>||[■](https://atcoder.jp/contests/abc192/submissions/20343594)|
|<b>Total</b>|<b>1500 pts</b>|<b>41:27</b>|<b><font color="red"> 2 Penalties </font></b>|||

#問題ごとの略解
##<font color=#808080> A問題 (100pts, diff: 7) </font> [Star](https://atcoder.jp/contests/abc192/tasks/abc192_a)
$X$ 枚持っている時, 次にご褒美がもらえるのは, $X$ より大きい最小の $100$ の倍数である. この整数を $Y$ とすると, $Y=\begin{cases} X+100 & (Xは100の倍数) \\\\ 100 \left \lceil \dfrac{X}{100} \right \rceil & (Xは100の倍数ではない)\end{cases}$ である. ここで, $100$ の倍数でない $X$ に対して, $X$ を $100$ で割った商と余りを $q,r$ とすると, $0<r<100$ で,
$$100 \left \lceil \dfrac{X}{100} \right \rceil=100 \left \lceil q+\dfrac{r}{100} \right \rceil=100(q+1)=100q+100=X+(100-r)$$
より, 求めるべき答えは
$$Y-X=\begin{cases} 100 & (Xは100の倍数) \\\\ 100-(X \mod 100) & (Xは100の倍数ではない)\end{cases}$$
である.

##<font color=#808080> B問題 (200pts, diff: 23) </font> [uNrEaDaBlE sTrInG](https://atcoder.jp/contests/abc192/tasks/abc192_b)
実装問題である. $i$ (1-index) 回目のループで奇数ならば $S_i$ が小文字かの判定, 偶数ならば $S_i$ が大文字かの判定をし, すべて真ならば文字列 $S$ は読みにくい文字列となる.

##<font color=#808080> C問題 (300pts, diff: 105) </font> [Kaprekar Number](https://atcoder.jp/contests/abc192/tasks/abc192_c)
$x$ が $d$ 桁のとき, $g_1(x), g_2(x)$ は愚直に実装しても $O(d^2)$ で求めることができるので, $a_n$ から $a_{n+1}=f(a_n)=g_1(a_n)-g_2(a_n)$ は $O(d^2)$ で求めることができ, $a_{n+1}$ も $d$ 桁以下である. よって, これを $n=1, \dots, K$ に対して行うと, $a_K$ は $O(d^2K)$ で求められる.  ここで, $d$ は $N$ の桁数より, $d=O(\log N)$ が成り立つので, この問題を $O(K (\log N)^2)$ [^c1] で求めることができた.

[^c1]: ソートを用いると, 計算量は $O(K \log N \log \log N)$ になる.
##<font color=#00C0C0> D問題 (400pts, diff: 1425) </font> [Base n](https://atcoder.jp/contests/abc192/tasks/abc192_d)
$T_n(X)$ で文字列 $X$ を $n$ -進法表記として得られる値とする.

$|X|=1$ のとき, $d+1 \leq n$ なる任意の整数 $n$ に対して, $T_n(X)=d$ である. よって,
$$\begin{cases} 1 & (d \leq M) \\\\ 0  & (d>M) \end{cases}$$
である.

以下から, $|X| \leq 2$ とする. ここで, $k:=|X|$ とし, $X=x_{k-1} x_{k-2} \dots x_1 x_0$ とする. ここで, 列 $(T_n(X))\_{n=d+1}^{\infty}$ は以下のことから狭義単調増加列であることがわかる.

* $i=0,1, \dots, k-1$ に対して, $x_i \geq 0$ である.
* $x_i>0$ なる $i \in \\{0,1, \dots, k \\}$ が存在する.
* 任意の正整数 $n$ と非負整数 $i$  に対して, $n^i<(n+1)^i$ である.
* 以上のことから, $T_n(X)<T_{n+1}(X)$ であることがわかる.

$T_{d+1}(X)>M$ ならば, 条件を満たす $n$ は存在無いので答えは $0$ であり,$T_{d+1}(X) \leq M$ ならば, 正の整数 $P$ を $T_{P}(X) \leq M < T_{P+1}(X)$ を満たす(唯一)の整数として, $P-d$ 個の整数 $T_{d+1}(X), \dots, T_P(X)$ は列 $(T_n(X))\_{n=d+1}^{\infty}$ が狭義単調増加であることからすべて異なる. よって, 解答は $P-d$ である. また, この $P$ は条件の単調減少性から, 二部探索を用いて $O(\log M)$ で求めることができる. ここで, 自明な下界と上界はそれぞれ $d+1, M$ である.

##<font color=#008000> E問題 (500pts, diff: 1135) </font> [Train](https://atcoder.jp/contests/abc192/tasks/abc192_e)
与えれらたグラフを頂点集合が $V$, 辺集合が $E$ であるグラフ $G=(V,E)$ とする. 各頂点 $v \in V$ に対して, 最速で $T_v$ で到着できる時に, $k$ 毎に時間が $t$ かかり, $w$ に到着する列車にいつ乗るべきかを考える. ここで, 早く行くに越したことがないので, 結局は $T_v$ 以上の最小の $k$ の倍数の時刻に発車する列車に乗るべきである. この事実を用いてDijkstra法で実装すれば, $O((N+M) \log N)$ で求めることができる. 

##<font color=#0000FF> F問題 (600pts, diff: 1783) </font>[Potion](https://atcoder.jp/contests/abc192/tasks/abc192_f)
ここで, 制約から, $\sum_{i=1}^N A_i \leq X$ であることがわかる. よって, 素材を合成した結果, $X$ を超えてしまうということはない.

合成する素材の数 $k$ を固定する. このとき, 問題は $A_1, \dots, A_N$ から $k$ 個を使った和のうち, $k$ で割った余りが $X$ で割った余りと等しくなるもので最大はいくつか? (または存在しないか?) という問題を解くことになる. この問題は動的計画法によって解くことができる.

${\rm DP}[i,m,r]~(0 \leq i \leq N, 0 \leq m \leq k, 0 \leq r<k)$ を $A_1, \dots, A_i$ から ちょうど $m$ 個使った和で $k$ で割った余りが $r$ のもののうちの最大の和 (存在しないときは $-\infty$)とする. このとき, 遷移は $i \geq 1$ のとき, $A_i$ を使うか使わないかという場合分けによって,
$${\rm DP}[i,m,r]=\max \left({\rm DP}[i-1,m,r], {\rm DP}[i-1,m-1,(r-A_i) {\rm ~mod~} N] \right)$$
となる. また, $i=0$ のときは
$${\rm DP}[0,m,r]=\begin{cases} 1 & (m=r=0) \\\\ -\infty & ({\rm otherwise})\end{cases}$$
となる. このように計算した ${\rm DP}[N,k,N {\rm ~mod~} k]$ が小問題の解答である.

$k=1, \dots, N$ における小問題の答えを $B_k$ とすると, $B_k+tk=X$ という式から, 求めるべき解答は
$$\min_{1 \leq k \leq N} \dfrac{X-B_k}{k}$$
になる.

計算量は各小問題において $O(k)^2 O(N)=O(N^3)$ より, 全体では $O(N^4)$ になる. ここで, $k=1, \dots, K$ と動き, $\sum_{k=1}^N k=\dfrac{1}{2} N(N+1)$ であることから, $1/4$ が係数つき, $\dfrac{100^4}{4}=2.5 \times 10^7$ は十分に高速である.

#感想

##総評
今回は<font color=#00C0C0> D問題 </font>, <font color=#008000> E問題 </font> で軽率なミスをしてしまった. 特に <font color=#008000> E問題 </font> でのミスは何度もしているミスである. また, <font color=#0000FF> F問題 </font> では正解の方法が思いついていたものの, 4乗だからという理由で実装もせずに捨ててしまった. このようなことが続いた場合, <font color=#C0C000> 黄色 </font> になるという目標は夢物語で終わってしまうだろう.

##反省点
<font color=#808080> B問題 </font> が遅い (いつもは2~3分).
WAの理由

* <font color=#00C0C0> D問題 </font> 問題文の誤読(○得られる数の種類集 $\to $ ✕ $n$ の個数)
* <font color=#008000> E問題 </font> 多重辺無視