ARC113 感想

1071 st / 3923 パフォ 1459

ARC113 の感想です

ABCD の 4完

体感難易度 A < C < D < B

レートも1600まで落ちてしまい悲しい
Bで詰まっちゃったのちょっと頭が悪くて反省　こういうのは表とか書いて整理してから実装するべきだったのに序盤の問題だからって焦っちゃったな
D でちょっと時間かけすぎた　数え上げ苦手だし仕方ないといえば仕方ないんだけどパフォから考えると20分以内に解けるようにならないとまずい

A. A*B*C

問題リンク

for a in 1..=k {
    let mut b: i64 = 1;
    while a * b <= k {
        b += 1;
    }
}

みたいにして $A, B$ を全探索してよくて、これは調和級数で $O(K \log K)$
$C$ は $K \div AB$ で求まるので全体として結局 $O(K \log K)$ で解ける

B. A^B^C

問題リンク

上の桁はそれより下の桁に影響を与えないので $1$ の位だけに着目してよい
実験したら $0, 1, …. , 9$ のどれも $mod 8$ で周期を持ってることがわかるので、書く

C. String Invasion

問題リンク

明らかに後ろから貪欲に操作していっておーけー\

D. Sky Reflector

問題リンク

$N = M = 1$ のときは $K$

そうでなくて $N = 1$ のとき、任意の $B$ を作れるが対になる $A$ が $1$ 通りしかないので $K^M$ が答え　$M = 1$ のときも同様に $K^N$

$N \ge 2, M \ge 2$ のとき $\max(A) \le min(B)$ である任意の数列を構築可能なので、境界値を固定して考えていく
$\displaystyle \sum_{x = 1}^{K} (x^N - (x - 1)^N)(K - x + 1)^M$ が答え