AtCoder Regular Contest 113のきろく - Flkanjin’s 競プロ録

6問編成ARCで初めてDまで通ったのに...

A - A*B*C (300点)
- 自分が通した解法
- 想定解
B - A^B^C (400点)
C - String Invasion (500点)
D - Sky Reflector (600点)
E - Rvom and Rsrev (800点): 未提出
F - Social Distance (1000点、実行時間制限: 4 sec): 未提出
結果、感想

A - ABC (300点)

いきなり想定解と違う解法でした

自分が通した解法

$ABC \leq K \Longleftrightarrow BC \leq \displaystyle\frac{K}{A}$ となりますが、それぞれ正整数なので $1 \leq BC \leq \displaystyle\left\lfloor \frac{K}{A} \right\rfloor$ となります。 $1 \leq j \leq \displaystyle\left\lfloor \frac{K}{A} \right\rfloor$ である $j$ について $BC = j$ となる $(B,\,C)$ の組の個数は $j$ の正の約数の個数であるので、求める答えは $\displaystyle\sum_{A = 1}^{K} \sum_{j = 1}^{\left\lfloor \frac{K}{A} \right\rfloor} \sigma_0(j)$ となり、内側の和について、累積和をとってやることで、 $O(K\sqrt{K})$ で答えが求まります。

ここで約数函数 $\sigma_x(n) = \displaystyle \sum_{d \mid n} d^x$ であり、 $\sigma_0(n) = (\text{$n$ の約数の個数})$ です。

想定解

$A$ を1つ固定させたとき $AB \leq K$ となる $B$ は $\displaystyle\left\lfloor \frac{K}{A} \right\rfloor$ 個存在します。ここで $B$ の個数について $A$ を $1$ から $K$ まで和をとったところで $O(K \log K)$ *1となります。また、 $(A,\,B)$ の組を1つ固定させたとき $C$ の個数は $\displaystyle\left\lfloor \frac{K}{AB} \right\rfloor$ でと、計算量 $O(1)$ で出すことができます。よって $AB \leq K$ となる $(A,\,B)$ の組を全て調べることで $O(K \log K)$ で答えが求まります。

B - A^B^C (400点)

$A^n$ の $10$ 進数での $1$ の位の値は、 $A$ の $10$ 進数での $1$ の位の値と $n$ によって決まります。それぞれの $10$ の剰余について $$\begin{align}
&0: 0 \rightarrow 0 \rightarrow \cdots
\\&1: 1 \rightarrow 1 \rightarrow \cdots
\\&2: 2 \rightarrow 4 \rightarrow 8 \rightarrow 6 \rightarrow 2 \rightarrow \cdots
\\&3: 3 \rightarrow 9 \rightarrow 7 \rightarrow 1 \rightarrow 3 \rightarrow \cdots
\\&4: 4 \rightarrow 6 \rightarrow 4 \rightarrow \cdots
\\&5: 5 \rightarrow 5 \rightarrow \cdots
\\&6: 6 \rightarrow 6 \rightarrow \cdots
\\&7: 7 \rightarrow 9 \rightarrow 3 \rightarrow 1 \rightarrow 7 \rightarrow \cdots
\\&8: 8 \rightarrow 4 \rightarrow 2 \rightarrow 6 \rightarrow 8 \rightarrow \cdots
\\&9: 9 \rightarrow 1 \rightarrow 9 \rightarrow \cdots
\end{align}$$ と、周期 $4$ (の約数)で $1$ の位が変化することが分かります。後は、 $B^C$ を $4$ で割った時の余りが分かれば $A^{B^C}$ の $1$ の位の数が求まります。ただし、余りが $0$ のときは $B^C \gt 0$ であることに注意してください。 $B^C$ を $4$ で割った時の余りは同様に $B$ を $4$ で割った時の余りと $C$ の値によって決まります。それぞれ $$\begin{align}
&0: 0 \rightarrow 0 \rightarrow \cdots
\\&1: 1 \rightarrow 1 \rightarrow \cdots
\\&2: 2 \rightarrow 0 \rightarrow 0 \rightarrow \cdots
\\&3: 3 \rightarrow 1 \rightarrow 3 \cdots
\end{align}$$ となっていて、特殊な $2$ の時を除けば、周期 $2$ (の約数)で変化することが分かります。 $B \bmod 4 = 2$ のときは $C=1$ で余り $2$ 、そうでないときは余り $0$ となります。
さてこれらの周期は実はEulerの定理やCarmichaelの定理を拡張したものから求まります。これらについてはこちらの記事を参照してください。

C - String Invasion (500点)

毎回操作を可能な限り後ろで行うことで最善手となります。このとき、同じ文字が2文字以上連続するブロックについて、後ろからそれらが見つかるたびにそれより後ろの文字を全てそのブロックの文字に置き換える状態となります。
このとき各操作回数について考えます。当のブロックを $b$ 、 $b$ の次のブロックを $c$ とします。 $b$ と $c$ の文字が同じときは、 $b$ に達した時は $c$ 以降は全て $b$ と同じ文字になっているため、この時の操作回数は $b$ と $c$ の間にある $b$ と異なる文字である位置の数なります。 $b$ と $c$ の文字が違う時や、 $c$ が存在しないときは $b$ に達した時は、それより後に $b$ と同じ文字からなるブロックは存在しないため、それより後ろにある文字数から $b$ と $c$ の間にある $b$ と同じ文字である位置の数を引いたものとなります。
求める答えはこれらを合計したものです。この貪欲法が正しいことの証明については公式解説を参照してください。

D - Sky Reflector (600点)

マス $(i,\,j)$ に書かれた数を $c_{i,j}$ とします。

$N = 1$のとき

$c_{1,j} = B_j$ となり、 $A_1 = \displaystyle\min_j B_j$ となるため、 $K^M$ 通りとなります。

$M = 1$のとき

$c_{i,1} = A_i$ となり、 $B_1 = \displaystyle\max_i A_i$ となるため、 $K^N$ 通りとなります。

上のどちらでもないとき

$\displaystyle\max_i A_i \leq \min_j B_j$ の時列対 $(A,\,B)$ を満たす書き込み方が存在します。そうでないときはそのような書き込み方は存在しないです。以下にこれらについて証明を述べます。

$A_i \gt B_j$となるような $(i,\,j)$ の組が存在するとき

このような $(i,\,j)$ を $(x,\,y)$ とします。つまり $A_x \gt B_y$ です。
このとき $A_x$ は $x$ 行目の最小値であるため、 $c_{x,\,y} \geq A_x$ となります。
$B_y$ は $y$ 列目の最大値であるため、 $c_{x,\,y} \leq B_y$ となります。
これらから $A_x \leq c_{x,\,y} \leq B_y$ となりますが、 $A_x \gt B_y$ に反し、矛盾します。背理法からこのような場合がありえないことが示せました。

$\displaystyle\max_i A_i \leq \min_j B_j$ が満たされるとき

$c_{i,j}=\left\{ \begin{array}{ll} A_i & (i = j)\\ B_j & (i \neq j) \end{array} \right.$ となる書き込み方を考えます。
$i$ 行目に含まれる数は $A_i$ と $B_j\ (i \neq j)$ となり、その最小値は $A_i$ となります。
$j$ 列目に含まれる数は $A_j$ と $B_j$ となり、その最大値は $B_j$ となります。
よって、具体的に書き込み方を構成することができました。

さて、このような列対 $(A, B)$ の個数ですが、次のように計算できます。
$\displaystyle\max_i A_i = m$ とします。このとき $A$ については最大値となる場所とその他の数により

$\begin{align} \sum_{k = 1}^{N} {}_N \mathrm{C}_{k} (m-1)^{N-k} &= \sum_{k = 0}^{N} {}_N \mathrm{C}_{k} (m-1)^{N-k} 1^k - (m-1)^N \\&= m^N - (m-1)^N \end{align}$

となります。2つ目の等号は二項定理によるものです。 $B$ については全ての要素が $m$ 以上であればいいので $(K-m+1)^M$ となり、全体として列対の個数は $\displaystyle\sum_{m = 1}^{K} [m^N - (m-1)^N](K-m+1)^M$ となります。
これら $N$ 乗や $M$ 乗は繰り返し二乗法で $O(\log N)$ や $O(\log M)$ で計算できるため、全体として $O(K (\log N + \log M))$ で計算できます。

E - Rvom and Rsrev (800点): 未提出

問題名は'Remove and Reverse'のそれぞれ色を付けたところの文字を選んで問題文中の操作を施したものになっていますね。
色々考えてるときに辞書順比較と数字の大小比較について対応関係があることなどが思い浮かんだりしましたが、何も役には立ちませんでした。
現段階でも分かっておりません。

分からないです...
そもそも有理数をmodで答える問題が解けたためしがないです...

結果、感想

f:id:Flkanjin:20210222165639p:plain
Dまでの速解き勝負だったこともあって、BCではまってなかなか抜け出せなかったのが痛かったなと思います。3連続で冷えてるので次こそ挽回したいです。

*1:調和級数や区分求積などを参照してください

A - A*B*C (300点)