AtCoder Regular Contest 113 感想

#総合結果
* [Score] 1800 pts
* [Time] 62:48 + <font color="red"> 05:00 $\times$ 1 </font> = 67:48
* [Ranking] 469 th [Rated内: 448 th]
* [Performance] <font color=#0000FF> 1955 </font>
* [Rating] <font color=#0000FF> 1837 </font> → <font color=#0000FF> 1859 </font> (+12)

##各問題ごとの詳細, 提出コード
|Question|Score|Time/Result|Penalty|During Contest|After Contest|
|:--:|--:|:--:|:--:|:--:|:--:|
|<font color=#808080> A問題 </font>|300 pts|08:28|<font color="red"> </font>|[■](https://atcoder.jp/contests/arc113/submissions/20376615)<br>(※Imos法のライブラリーは未使用)|[■](https://atcoder.jp/contests/arc113/submissions/20402813)|
|<font color=#804000> B問題 </font>|400 pts|19:54|<font color="red">1 Penalty</font>|[■](https://atcoder.jp/contests/arc113/submissions/20379511)|[■](https://atcoder.jp/contests/arc113/submissions/20470098)|
|<font color=#008000> C問題 </font>|500 pts|28:47|<font color="red"> </font>|[■](https://atcoder.jp/contests/arc113/submissions/20381852)||
|<font color=#00C0C0> D問題 </font>|600 pts|<b>62:48</b>|<font color="red"> </font>|[■](https://atcoder.jp/contests/arc113/submissions/20389538)||
|<font color=#FF8000> E問題 </font>|0 pts|--:--|<font color="red"> </font>|[]()||
|<font color=#AEB3B5> F問題 </font>|0 pts|--:--|<font color="red"> </font>|[]()||
|<b>Total</b>|<b>1800 pts</b>|<b>62:48</b>|<font color="red"> <b>1 Penalty</b></font>|||

#問題ごとの略解
##<font color=#808080> A問題 (300pts, diff: 237) </font> [A*B*C](https://atcoder.jp/contests/arc113/tasks/arc113_a)
$a=\alpha$ と固定する. すると, 問題は $bc \leq \left \lfloor \dfrac{K}{\alpha} \right \rfloor$ を満たす正の整数の組 $(b,c)$ は何個か? という小問題に帰着する. この答えを $X_\alpha$ とする.

$V_t$ を $xy=t$ を満たす正の整数の組 $(x,y)$ の個数とする. $x$ を $\beta$ に固定した時, $\beta$ の倍数すべてに $V_t$ に $1$ ずつ寄与することがわかる. よって, $V_\beta, V_{2 \beta}, \dots$ に $1$ 寄与する.

このことから, 実際に $\beta=1, \dots, K$ として, $K$ 以下の $\beta$ の倍数に $1$ ずつ加算させていけば, $t=1, \dots, K$ に対して $V_t$ と求まる.

また, $xy \leq t$ を満たす正の整数の組 $(x,y)$ の組の個数 $W_t$ は $W_t=\sum_{j=1}^t V_j$ で求めることができる.

以上のことから $X_\alpha=W_{\lfloor K/\alpha \rfloor}$ なので, $\alpha=1, \dots, K$ と動かして, 求めるべき答えは
$$\sum_{\alpha=1}^K X_\alpha=\sum_{\alpha=1}^K W_{\lfloor K/\alpha \rfloor} $$
となる.

計算量は $V_1, \dots, V_K$ を求めるのに
$$O \left(\dfrac{K}{1}+\dfrac{K}{2}+\dots+\dfrac{K}{K} \right)=O(K \log K)$$
かかり[^a1], $W_t$ を求めるのには累積和で $O(K)$, 最終解答を求めるのに $O(K)$ かかり, 全体では $O(K \log K)$ となる.

なお, 2重の ${\tt for}$ 文を回すことによっても $O(K \log K)$ で求めることができる.

[^a1]: $O(K^2)$ と思っていると通せない.

##<font color=#804000> B問題 (400pts, diff: 537) </font> [A^B^C](https://atcoder.jp/contests/arc113/tasks/arc113_b)
剰余に関する基本的な事実として, 整数 $\alpha, \beta$ と非負整数 $p$, 正の整数 $m$ において,
$$\alpha \equiv \beta \pmod{m} \Rightarrow \alpha^p \equiv \beta^p \pmod{m}$$
である. よって, 入力された $A$ について, 必要ならば $10$ で割った余りに変えることによって, $0 \leq A < 10$ としてもよい.

ここで, $A=0, \dots, 9$ において, $p$ を小さい値で実験すると, $A^p \pmod{10}$ は以下のように周期4[^b1]で循環することがわかる.

|$A \backslash p$|1|2|3|4|5|
|:--:|:--:|:--:|:--:|:--:|:--|
|<b>0</b>|0|0|0|0|0|
|<b>1</b>|1|1|1|1|1|
|<b>2</b>|2|4|8|6|2|
|<b>3</b>|3|9|7|1|3|
|<b>4</b>|4|6|4|6|4|
|<b>5</b>|5|5|5|5|5|
|<b>6</b>|6|6|6|6|6|
|<b>7</b>|7|9|3|1|7|
|<b>8</b>|8|4|2|6|8|
|<b>9</b>|9|1|9|1|9|

以上のことから, $A^{B^C} \pmod{10}$ は $A$ と $B^C \pmod{4}$ によって求めることができる. 計算量は $B^C \pmod{4}$ を求めるのに $O(\log C)$ である. [^b2]

[^b1]: 最小周期ではない.
[^b2]: $\pmod{4}$  くらいなら場合分けによって $O(1)$ でもできるが今回は不要.

##<font color=#008000> C問題 (500pts, diff: 829) </font> [String Invasion](https://atcoder.jp/contests/arc113/tasks/arc113_c)
文字列 $S$ において, $S[i]=S[i+1] \neq S[i+2]$ を満たす $i$ を昇順にならべたものを $i_1 \leq \dots \leq i_K$ とする. このとき, 操作の選択肢は $K$ 個であるが, $i_K$ を選ぶと, $i_1, \dots, i_{K-1}$ は次の回でも選ぶことができ, $i_K<|S|-2$ ならば, 選択肢に $i_K+1$ も加わり, この $i_K+1$ が次の選択の最大値になる.

この操作を繰り返すのが最善である. このときの操作の回数は次のようにして求めることができる. ただし, $X$ を解答を求める変数とし, 最初は $0$ で初期化している.

* $i=|S|-1,|S|-2, \dots,1$ 順に以下を実行する.
 * $S[i]=S[i+1]$ であれば, $S[i+2], S[i+3], \dots, S[|S|]$ にある文字のうち, $S[i]$ でない文字の個数を $X$ に加算する. そして, $S[i+2], S[i+3], \dots, S[|S|]$ をすべて $S[i]$ に変更する.

ここで, $S[i]$ が何個か? という問題に答える必要があるが, これは辞書を使うことによって, 解決することができる. 計算量は $S$ に出てくる可能性のある文字 (アルファベット) の個数を $\sigma$ とすると [^c1], $O(\sigma |S|)$ である.

[^c1]: 今回の制約では, $\sigma=26$ である.

##<font color=#00C0C0> D問題 (600pts, diff: 1389) </font> [Sky Reflector](https://atcoder.jp/contests/arc113/tasks/arc113_d)
$N=1$ のとき, マスの書き方と $B=(B_j)_{j=1}^M$ に1対1の対応がとれ, 書き込みによって $A_1$ が一意に定まることから, 答えは $K^M$ である.

$M=1$ のときも同様にして, 答えは $K^N$ である.

以降では $N,M \geq 2$ とする. 列の対 $(A=(A_i)\_{i=1}^N, B=(B_j)\_{j=1}^M)$ になるような書き込みが存在するための必要十分条件を考えるが, 実は $(A,B)$ になる書き込みが存在することと, $\max(A) \leq \min (B)$ になることは同値である.

* 十分性: $i$ 行 $j$ 列に書き込む値を $X_{i,j}$ とする. ここで, $A, B$ の定義から, 任意の $(i,j)$ に対して, $A_i \leq X_{i,j} \leq B_j$ であることがわかる. $I,J$ をそれぞれ $I=\max A, J=\min B$ を満たすような添字 (複数あるならばそのうちの1つ)とすると, $A_I \leq X_{I,J} \leq B_J$ であり, $I,J$ の定義から, $\max A \leq \min B$ であることがわかる.

* 必要性: 以下のようにして条件を満たすように書き込むことができる. [^d1]

 * $N \geq M$ のとき

||||$\cdots$|||
|:--:|:--:|:--:|:--:|:--:|:--:|
||$B_1$|$A_1$|$\cdots$|$A_1$|$A_1$|
||$A_2$|$B_2$|$\cdots$|$A_2$|$A_2$|
|$\vdots$|$\vdots$|$\vdots$|$\ddots$|$\vdots$|$\vdots$|
||$A_{M-1}$|$A_{M-1}$|$\cdots$|$B_{M-1}$|$A_{M-1}$|
||$A_M$|$A_M$|$\cdots$|$A_M$|$B_M$|
||$A_{M+1}$|$A_{M+1}$|$\cdots$|$A_{M+1}$|$A_{M+1}$|
|$\vdots$|$\vdots$|$\vdots$|$\ddots$|$\vdots$|$\vdots$|
||$A_N$|$A_N$|$\cdots$|$A_N$|$A_N$|

* $N \leq M$ のとき

||||$\cdots$||||$\cdots$||
|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|:--:|
||$A_1$|$B_2$|$\cdots$|$B_{N-1}$|$B_N$|$B_{N+1}$|$\cdots$|$B_M$|
||$B_1$|$A_2$|$\cdots$|$B_{N-1}$|$B_N$|$B_{N+1}$|$\cdots$|$B_M$|
|$\vdots$|$\vdots$|$\vdots$|$\ddots$|$\vdots$|$\vdots$|$\vdots$|$\ddots$|$\vdots$|
||$B_1$|$A_2$|$\cdots$|$A_{N-1}$|$B_N$|$B_{N+1}$|$\cdots$|$B_M$|
||$B_1$|$B_2$|$\cdots$|$B_{N-1}$|$A_N$|$B_{N+1}$|$\cdots$|$B_M$|

よって, 問題は $\max A \leq \min B$ なる列対 $(A,B)$ はいくつか? という問題に帰着できた.

$\max A \leq \min B$ なる列対 $(A,B)$ に対する特徴量 $\chi(A,B)$ を, $\chi(A,B):=\max A$ とする. $\chi(A,B)=k$ となる列対 $(A,B)$ を数える.

一般に, $1$ 以上の整数からなる長さ $l$ の列 $A$ で $\min A \leq t$ を満たすのは $t^l$ 個であり, $\min A=t$ を満たすのは, $\min A \leq t$ であるもののうち, $\min A \leq t-1$ ではないものすべてなので, $t^l-(t-1)^l$ であることがわかる.

このことを利用すると, $\chi(A,B)=k$ となる列対 $(A,B)$ において, $\min A=k$ となるのは $k^N-(k-1)^N$ 個, $k \leq \max B$ となるのは $(K-k+1)^M$ 個であり, これらは独立に選ぶことができるので, 合計 $(k^N-(k-1)^N) (K-k+1)^M$ 個である.

これを $k=1, \dots, K$ まで動かして, 求めるべき解は
$$\sum_{k=1}^K (k^N-(k-1)^N) (K-k+1)^M$$
である. 計算量は $O(K \log NM)$ である.

[^d1]: この表の構成に, $N,M \geq 2$ という仮定を用いている.

##<font color=#FF8000> E問題 (800pts, diff: 2789) </font> [Rvom and Rsrev](https://atcoder.jp/contests/arc113/tasks/arc113_e)
(正解でき次第更新)

##<font color=#AEB3B5> F問題 (1000pts, diff: 3990) </font> [Social Distance](https://atcoder.jp/contests/arc113/tasks/arc113_f)
(正解でき次第更新)

#感想

##総評
今回のコンテストの<font color=#00C0C0> D問題 </font>が令和ARCでのD問題で最も簡単だったことから, スピードが重要視された. そのため, Penaltyが非常におおきな影響を与える結果になった.

##良かった点
* ひさしぶりにRatingを増やすことに成功し, 昨日の失敗分をキャンセルできた.

##反省点
* WAの理由
 * <font color=#804000>B問題</font>: $p:=B^C \pmod{4}$ とし, $A^p \pmod{10}$ を求めてしまった ($B^C$ が4の倍数のとき, $p=4$ とすべきである).