A. Minimizing the String

問題概要

Problem - A - Codeforces

長さ $n$ の文字列 s が与えられる。1文字削除して辞書順最小の s' を出力せよ。

制約

$2 \le n \le 2 \cdot 10^5$

考え方

辞書順最小の文字列を求めるには、前から順番に辞書順最小の文字列で構成していくことになります。よって $s_i \geq s_{i+1}$ なる $i$ が存在した場合は $s_i$ を除くことで辞書順最小が達成されます。

Submission #45970471 - Codeforces

B. Divisor Subtraction

問題概要

Problem - B - Codeforces

以下の操作をするとき、操作の回数を求めよ。

操作
$n = 0$ ならば操作を終了する。そうでなければ $n$ の最小の素因数 $d$ をもとめ、 $n$ から $d$ を引く

制約

$2 \le n \le 10^{10}$

考え方

一度 $n$ が偶数になった場合はその後は常に $2$ が最小の素因数になるため、 $2$ を引き続けることになります。よって $n$ が奇数の場合は最小の素因数 $d$ を求め $n-d$ をし、残りの数を $2$ で割った回数が解となります。

Submission #45970778 - Codeforces

C. Meme Problem

問題概要

Problem - C - Codeforces

$a + b = d$ かつ $a \cdot b = d$ を満たすような $a, b$ を求めよ。誤差は $|(a + b) - a \cdot b| \le 10^{-6}, |(a + b) - d| \le 10^{-6}$ まで許容される。クエリが $t$ 個与えられるのでそれぞれに答えよ。

制約

$t : 1 \le t \le 10^3$
$d : 0 \le d \le 10^3$

考え方

二分探索なのかと思いきや、2次方程式の解を求めることに帰着します。解の公式 $\displaystyle a = \frac{d \pm \sqrt{d^2-4d}}{2}, b = d - a$ に代入して解が求まりますが、判別式 $D = d^2-4d \lt 0$ となる場合は解なしのため N と出力します。