しょぼなまログ

Codeforces 1103 (Div. 3) C問題 解法が証明できない...

2026/06/13
最終更新: 2026/07/10
タグ: article, ブログ, Codeforces, 競プロ, 記事6, ignore
目次
変更 (2026年7月10日)
注意
考えたこと
続き
まとめ

変更 (2026年7月10日)

あまりにも中途半端な記事になってしまっていたので、一旦ホームページの目次から消しました。

前記事はこちら

問題はこちら（codeforces）

注意

証明できていません。

考えたこと

1足す操作よりも先にxで割る操作をしたほうが良いことの証明

整数 tt を操作することを考える。また、

P: tt に1を足す操作
Q: tt を xx で割る操作

とする。

Pを先に行う場合を考える。
Pを nn 回行った後にQを1回行った場合の操作後の値を t′t' とすると、

t′=⌊t+nx⌋t' = \lfloor \frac{t + n}{x} \rfloor

ここで、 t=px+r1,n=qx+r2t = px + r_1, n = qx + r_2 となるように p,q,r1,r2p, q, r_1, r_2 を置く。（ 0≤r1<x,0≤r2<x0 \le r_1 < x, 0 \le r_2 < x ）
すると、

t′=⌊px+qx+r1+r2x⌋=p+q+⌊r1+r2x⌋\begin{aligned} t' = \lfloor \frac{px + qx + r_1 + r_2}{x} \rfloor \\ = p + q + \lfloor \frac{r_1 + r_2}{x} \rfloor \end{aligned}

この場合、総操作回数は n+1n+1 回である。

次に、Pを後に行う場合を考える。
Pを mm 回行う場合、操作後の値を t′′t''とすると、

t′′=⌊tx⌋+m=p+⌊r1x⌋+m=p+m\begin{aligned} t'' = \lfloor \frac{t}{x} \rfloor + m\\ = p + \lfloor \frac{r_1}{x} \rfloor + m \\ = p + m \end{aligned}

この場合、総操作回数は m+1m + 1 回である。

上記の2つの手順を使って、同じ値にするためにかかる操作回数を比較する。
すなわち、 t′=t′′t' = t'' の場合を考える。

t′=t′′p+q+⌊r1+r2x⌋=p+m⌊r1+nx⌋=m\begin{aligned} t' = t'' \\ p + q + \lfloor \frac{r_1 + r_2}{x} \rfloor = p + m \\ \lfloor \frac{r_1 + n}{x} \rfloor = m \end{aligned}

よって、以下の式が成り立つ:

mx≤r1+n<(m+1)xmx \le r_1 + n < (m + 1)x

左の2辺より、

mx−m−r1≤n−mmx - m - r_1 \le n - m

ここから mm の値によって場合分けする。

(i) m=1m = 1 の場合

mx−m−r1≤n−mmx - m - r_1 \le n - m の mm に 1を代入する:

x−r1−1≤n−mx - r_1 - 1 \le n - m

0≤r1<x0 \le r_1 < x であるから、

0≤n−mm≤n\begin{aligned} 0 \le n - m \\ m \le n \end{aligned}

(ii) m≥2m \ge 2 の場合

mx−m−r1=(m−1)x−m+(x−r1)≥2m−2−m+(x−r1)=(m−2)+(x−r1)≥0\begin{aligned} mx - m - r_1 = (m - 1)x - m + (x - r_1) \\ \ge 2m - 2 - m + (x - r_1) \\ = (m - 2) + (x - r_1) \\ \ge 0 \end{aligned}

よって、

0≤mx−m−r1≤n−mm≤n\begin{aligned} 0 \le mx - m - r_1 \le n - m \\ m \le n \end{aligned}

したがって、取りうるすべての mm に対して m≤nm \le n が言えたので、Qを1回、Pを任意の回数行うときは、先にQを行った方がよいことが示された。

続き

Qを ss 回（ 2≤s2 \le s ）行うときは Q'を「 tt を xsx^s で割る」という風に定義しなおせばいいかと思ったが、割るときに切り捨てが入るので完全に等しくできない？

あとPとQを交互に行うときはどう考えればいいのか？

まとめ

証明が苦手すぎます。はい。

こういう時はこう証明するみたいな知見が全く足りていない状況なんですね。いろんな解説を読みまくるしかないか...