Codeforces Round #701 (Div. 2)のきろく

久しぶりにCodeforcesに出ました。できればD問題通したかったな。
問題文和訳はこちら

A. Add and Divide (500点、実行時間制限: 1 sec)
B. Replace and Keep Sorted (1000点)
- 自分の解法
- 解説の解法
C. Digital Graffiti (1500点)
- 自分の解法
- 解説の解法
D. Multiples and Power Differences (1750点)
E. Move and Swap (2500点): 未提出
F. Copy or Prefix Sum (3000点): 未提出
結果、感想

A. Add and Divide (500点、実行時間制限: 1 sec)

$\displaystyle\frac{a}{b} \gt \frac{a}{b+1}$ より $\displaystyle\left\lfloor \frac{a}{b} \right\rfloor \geq \left\lfloor \frac{a}{b+1} \right\rfloor$ であるので、途中で $b$ を増やす操作を挟むとき、操作列の長さを長くすることなくこの操作を最初に移すことができます。
さて、 $b$ の値を決めたとき $a$ を $\displaystyle\left\lfloor \frac{a}{b} \right\rfloor$ にする操作の回数ですが、 $b=1$ のときは $\displaystyle\left\lfloor \frac{a}{b} \right\rfloor = a$ なので何回やっても $a = 0$ にすることはできないですが、 $b = 2$ のときは $\log_2(10^9) \simeq 29.897$ であるため、 $30$ 回以内で $a = 0$ にすることができます。 $b$ の値を増やすと、割り算の回数が減るのでそれに従って操作回数を更新していきます。 $b$ の値を大きくしすぎると最初の足し算の回数が増え、全体の操作回数が多くなってしまうので、適当な大きさまでで更新を止めます。割り算の回数は高々30回なので、初期値よりも30大きな値までで十分です。

B. Replace and Keep Sorted (1000点)

$b$ は $a$ の部分列 $[a_l,\,a_{l+1},\,\dots,\,a_r]$ から値を1つだけ変えた配列です。

自分の解法

$c$ 番目の要素を変えるとする、即ち、 $j \neq c$ のとき $b_j = a_{l + j -1}$ で $j = c$ のとき $b_j \neq a_{l + j -1}$ とします。 $a$ も $b$ も狭義単調増加整数列であることから $c$ によって場合分けができます。

$c = 1$ (区間の左端)のとき、 $b_1$ は $1$ から $a_{l + 1} - 1$ までの正整数のうち $a_l$ ではない $a_{l +1} - 2$ 個の整数をとることができます。
$1 \lt c \lt r-l+1$ (区間の端でない場合)のとき、 $b_c$ は $a_{l + c -2} +1$ から $a_{l + c} - 1$ までの正整数のうち $a_{l + c - 1}$ ではない $a_{l + c} - a_{l + c - 2} -2$ 個の整数をとることができます。
$c = r - l + 1$ (区間の右端)のとき、 $b_{r - l + 1}$ は $a_{r - 1} + 1$ から $k$ までの正整数のうち $a_r$ ではない $k - a_{r - 1} - 1$ 個の整数をとることができます。

以上より、これらは同時には起こりえないので求める答えは $$\begin{align}
(a_{l + 1} - 2) &+ \sum_{c = 2}^{r - l}\, (a_{l + c} - a_{l + c - 2} - 2) + (k - a_{r - 1} - 1) \\
&= k + (a_r - a_l + 1) - 2(r - l + 1)
\end{align} $$ となります*1。私はコンテスト中はシグマの中身を計算せず累積和で通してます。

解説の解法

いずれかの要素を $x$ にしたときに何個の $k$ -類似列ができるか、という考え方です。

$x \lt a_l$ のとき、 $a_l$ を $x$ に置き換えることで $1$ つの $k$ -類似列ができます。
$x \gt a_r$ のとき、 $a_r$ を $x$ に置き換えることで $1$ つの $k$ -類似列ができます。
$a_l \lt x \lt a_r$ のとき、 $x$ がいずれかの $a_j$ $(j \in [l,\,r])$ と等しい場合 $k$ -類似列はできないですが、そうでないなら $a_j \lt x \lt a_{j+1}$ として、 $a_j$ か $a_{j + 1}$ を $x$ に置き換えることで $2$ つの $k$ -類似列ができます。このような $x$ は $a_l$ から $a_r$ までの整数のうち $[a_l,\,a_{l+1},\,\dots,\,a_r]$ に含まれない整数であるので、 $(a_r - a_l + 1) - (r - l + 1)$ 個あります。

以上より、これらは同時には起こりえないので求める答えは $$ \begin{align}
(a_l - 1) & + 2[(a_r - a_l +1) - (r - l + 1)] + (k - a_r) \\
& = k + (a_r - a_l + 1) - 2(r - l + 1)
\end{align} $$ と同じ式が導出できます。

C. Digital Graffiti (1500点)

自分の解法

$\displaystyle\left\lfloor \frac{a}{b} \right\rfloor = a \bmod b = p$ とすると $a = pb + p$ より $\displaystyle p = \frac{a}{1+b}$ であり、 $b \gt k$ と $a \leq x$ より $b$ を固定したときの特別な組の個数は $p$ の個数であり $\displaystyle\min\left\{b-1,\,\left\lfloor \frac{x}{1+b} \right\rfloor\right\}$ となり、 $b = 1$ から $y$ まで和をとれば答えとなりますが、そのままだとTLEしてしまいます。

$\displaystyle\left\lfloor \frac{x}{1+b} \right\rfloor \geq b - 1$ となるのは $b^2 \leq x + 1$ のときであり、その範囲では $b - 1$ を足していきます。

$b^2 \gt x + 1$ のときは $\displaystyle\left\lfloor \frac{x}{1+b} \right\rfloor = k$ として各 $k$ の値について $b$ の数を数えます。
$$ \begin{align}
\left\lfloor \frac{x}{1+b} \right\rfloor = k & \Longleftrightarrow \frac{x}{1+b} - 1 \lt k \leq \frac{x}{1+b}
\\ &\Longleftrightarrow \frac{x}{k+1} - 1 \lt b \leq \frac{x}{k} - 1
\end{align}$$ となるのでこれらを $k = 1$ から $\displaystyle\left\lfloor \frac{x}{\left\lfloor \sqrt{x+1} \right\rfloor + 2} \right\rfloor$ の範囲で足していくことで答えが求まります。

解説の解法

$\displaystyle\left\lfloor \frac{a}{b} \right\rfloor = a \bmod b = k$ のとき $a = kb + k$ となり、 $b \gt k$ であることから $k^2 \lt kb + k = a \leq x$ より $k \leq \sqrt{x}$ となります。

それぞれの $k$ について特別な組 $(a,\,b)$ の個数は以下の3条件を満たす $b$ の個数となります。

$k \lt b$
$1 \leq b \leq y$
$1 \lt kb+k \lt x \Longleftrightarrow \displaystyle\frac{1}{k} - 1 \leq b \leq \frac{x}{k} - 1 \Longrightarrow 1 \leq b \leq \frac{x}{k} - 1\ (\because b\text{ は正整数})$

となり、その個数は $\displaystyle\max\left\{0,\,\min\left\{y,\ \frac{x}{k}-1\right\} \right\}$ となり、その和が答えとなります。

D. Multiples and Power Differences (1750点)

コンテスト中には解けませんでした... ちょっと考えれば解ける問題だったので勿体ない...

$l$ を $1$ から $16$ までの公倍数の1つとして $$b_{i,j}=\left\{
\begin{array}{ll}
l & (i + j\text{ は奇数})\\
l + {a_{i,j}}^4 & (\text{otherwise})
\end{array}
\right.$$ とすれば*2と下2つの条件を満たすことができます。 $l$ としては $16!$ が思いつくもしれませんが $16!=20\,922\,789\,888\,000$ で $1 \leq b_{i, j} \leq 10^6$ の条件を満たしません。しかし、最小公倍数 $\mathrm{lcm}\{1,\,2,\,\dots,\,16\} = 720720$ なら条件を満たすことができます。