AtCoder Regular Contest 123 感想

#総合結果
* [Score] 1300 pts
* [Time] 106:42 + <font color="red"> 05:00 $\times$ 1 </font> =111:42
* [Ranking] 560 th [Rated内: 538 th]
* [Performance] <font color=#0000FF> 1806　</font>
* [Rating] <font color=#0000FF> 1941 </font> → <font color=#0000FF> 1928 </font> (-13)

##各問題ごとの詳細, 提出コード
|Question|Score|Time/Result|Penalty|During Contest|After Contest|
|:--:|--:|:--:|:--:|:--:|:--:|
|<font color=#808080> A問題 </font>|300 pts|004:41|<font color="red"> 1 Penalty </font>|[■](https://atcoder.jp/contests/arc123/submissions/24353973)||
|<font color=#808080> B問題 </font>|400 pts|012:10|<font color="red"> </font>|[■](https://atcoder.jp/contests/arc123/submissions/24356144)||
|<font color=#0000FF> C問題 </font>|600 pts|<b>106:42</b>|<font color="red"> </font>|[■](https://atcoder.jp/contests/arc123/submissions/24371568)|[■](https://atcoder.jp/contests/arc123/submissions/24375390)<br>解説に即した実装|
|<font color=#C0C000> D問題 </font>|0 pts|--:--|<font color="red"> </font>|||
|<font color=#FF0000> E問題 </font>|0 pts|--:--|<font color="red"> </font>|||
|<font color=#AEB3B5> F問題 </font>|0 pts|--:--|<font color="red"> </font>|||
|<b>Total</b>|<b>1300 pts</b>|<b>106:42</b>|<b><font color="red"> 1 Penalty </font></b>|||

#問題ごとの略解
##<font color=#808080> A問題 (300pts, diff: 177) </font> [Arithmetic Sequence](https://atcoder.jp/contests/arc123/tasks/arc123_a)

3項からなる列 $(A,B,C)$ が等差数列であることの定義 $B-A=C-B$ を変形すると, $A-2B+C=0$ になる. よって, ここで, 与えられた列を $(X,Y,Z)$ としたとき, $K:=X-2Y+Z$ とする. ここで, $X,Y,Z$ に $1$ 加算することはそれぞれ, $K$ について, $1$ 増やす, $2$ 減らす,  $1$ 増やすと同じであることから, 以下の問題に帰着できた.

> $K=X-2Y+Z$ に対して, $+1$ か $-2$ を施して, $K=0$ を達成するための最小回数を求めよ.

* $K<0$ のとき<br>$K$ を増やすためには, $+1$ を $|K|$ 回施すしかないので, 答えは $|K|$ である.
* $K \geq 0$ のとき
    * $K$ が偶数のとき<br>$-2$ を $K/2$ 回 施すことで, 目標を達成できる.
    * $K$ が奇数のとき<br>$-2$ だけでは目標を達成できないので, 1回だけ $+1$ をし, $(K+1)/2$ 回 $-2$ を施せば良い.

よって, $K=X-2Y+Z$ としたとき, 答えは
$$\begin{cases} |K| & (K <0) \\\\ K/2 & (K: 偶数) \\\\ (K+1)/2+1 & (K:奇数) \end{cases}$$
である.

##<font color=#808080> B問題 (400pts, diff: 351) </font> [Increasing Triples](https://atcoder.jp/contests/arc123/tasks/arc123_b)
必要ならば, ソートして, $A,B,C$ を単調増加としてもよい. このとき, 答え (最大値) を $M$ とする.
$$T=\\{(A_{i_1}, B_{j_1}, C_{k_1}), \dots, (A_{i_t}, B_{j_t}, C_{k_t})\\}$$
は

* 各 $l$ に対して $A_{i_l} < B_{j_l} < C_{k_l}$ をみたす
* $(i_1, \dots, i_t), (j_1, \dots, j_t), (k_1, \dots, k_t)$ の中に重複は無い.
* 対称性から $i_1 < \dots < i_t$ としてもよい. 

なお, 箇条書きで述べた3つの条件を条件 (*) とかく. このとき, 以下のことがわかる. 以下, この問題における解答 (取りうる組の最大個数) を $M$ とする.

> $|T|=M>0$ かつ, $i_1=1$ を満たすものが存在する.
> (証明) $i_1 \neq 1$ のとき, $i_1>1$ である. このとき, $A_1 \leq A_{i_1}$ であることから,
> $$T':=\\{(A_1, B_{j_1}, C_{k_1}), \dots, (A_{i_t}, B_{j_t}, C_{k_t})\\}$$
> は, $|T'|=M$ であり, 条件 (*) を満たす.

よって, $i_1=1$ としてもよい. また, $(A_1, B_{j_1}, C_{k_1})$ において, $B_{j_1}$ についても, 上と同様の証明により, $j_1$ は $A_1 < B_{j'\_1}$ を満たす最小の整数 $j'\_1$ としてもよく. さらに, $k_1$ についても $B_{j_1} < C_{k'\_1}$ を満たす最小の整数 $k'\_1$ としてもよい.

このようにして, $M$ を達成する組の作り方において, $(A_1, B_{j'\_1}, C_{k'\_1})$ が存在することがわかった.

この考察から, 以下のアルゴリズムによって正解を求めることができる.

* $M=0$ とする.
* $p$ を十分大きな整数とし, $A,B,C$ にそれぞれ $p,2p,3p$ を加える (この $p,2p,3p$ はストッパーの働きを果たす).
* $A, B, C$ が全て非空である限り以下を行う.
    * $A$ の最小値を $\alpha$ とする.
    * $B$ のうち, 小さい順に各項 $b$ が $b \leq \alpha$ ならば, $B$ から $b$ を削除する. この操作後の $B$ の最小値を $\beta$ とする.
    * $C$ のうち, 小さい順に各項 $c$ が $c \leq \beta$ ならば, $C$ から $c$ を削除する. この操作後の $c$ の最小値を $\gamma$ とする.
    * $A,B,C$ からそれぞれ $\alpha, \beta, \gamma$ を削除する.
    * $\alpha \neq p, \beta \neq 2p, \gamma \neq 3p$ ならば, $M$ に $1$ を加える.
* $M$ を出力.

計算量は, ソートがボトルネックになり, $O(N \log N)$ である.

##<font color=#0000FF> C問題 (600pts, diff: 1827) </font> [1, 2, 3 - Decomposition](https://atcoder.jp/contests/arc123/tasks/arc123_c)

$\mathcal{G}$ で, 10進法表記した時, 全ての項が $1,2,3$ であるような自然数全体の集合とする. このとき, 実は以下が成り立ち, どんな自然数でも答えは $5$ 以下であることがわかる.

> 任意の自然数 $N$ に対して, 以下を満たす自然数 $p_1,p_2,p_3,p_4,p_5$ が存在する.
> $$p_1,p_2,p_3,p_4,p_5 \in \mathcal{G} \cup \\{0\\}, \quad p_1+p_2+p_3+p_4+p_5=N$$
>

<details><summary>証明</summary><div>
数学的帰納法で示す.

* $0 \leq N \leq 4$ のとき<br>明らかに成り立つ.
* $N \geq 5$ のとき<br> $N \geq 5$ のとき, 以下を満たすような自然数 $n,r$ が存在する.
$$N=10n+r, \quad 5 \leq r \leq 15$$
このとき, $5 \leq r \leq 15$ より, $1$ 以上 $3$ 以下の $5$ 個の整数 $q_1, \dots, q_5$で $q_1+\dots+q_5=r$ なるものが存在する. そして, 仮定から, $p_1, \dots, p_5 \in \mathcal{G} \cup \\{0\\}$ で, $p_1+\dots+p_5=n$ なるものが存在する. このとき, $i=1, \dots, 5$ に対して, $10p_i+q_i \in \mathcal{G} \cup \\{0\\}$ であり,
$$(10p_1+q_1)+\dots+(10p_5+q_5)=10(p_1+\dots+p_5)+(q_1+\dots+q_5)=10n+r=N$$
であり, 条件を満たすことが分かった.
</div></details>

よって, 答えは $5$ 以下であることが分かったので, 以下のアルゴリズムに正当性を持つことができる. ただし, $N$ における答えを $f(N)$ とする.

* $N=0$ ならば, $0$ を返す.
* $k=1,2,3,4,5$ の順に実行する.
* $k \leq r \leq 3k$ に対して, $N-r$ が $10$ の倍数であり, $f((N-r)/10) \leq k$ ならば, $k$ 以下が確定し, ${\tt for}$ 文の意味から, $k$ が答えになるので, $k$ を返す. 

計算量は, ここで, $N$ を求めるときに, $m:=\lfloor N/10 \rfloor$ とすると, 再帰呼び出しは $f(m), f(m-1)$ に限られることから, 計算量は $O(N \log N)$ である.

##<font color=#C0C000> D問題 (700pts, diff: 2143) </font> [Inc, Dec - Decomposition](https://atcoder.jp/contests/arc123/tasks/arc123_d)
(正解でき次第加筆予定)

##<font color=#FF0000> E問題 (700pts, diff: 2828) </font> [Training](https://atcoder.jp/contests/arc123/tasks/arc123_e)
(正解でき次第加筆予定)

##<font color=#AEB3B5> F問題 (1000pts, diff: 3424) </font> [Insert Addition](https://atcoder.jp/contests/arc123/tasks/arc123_f)
(正解でき次第加筆予定)