ℕ Coloring

問題

C - ℕ Coloring

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

atcoder.jp

提出

Submission #44446643 - AtCoder Regular Contest 115

AtCoder is a programming contest site for anyone from beginners to experts. We hold weekly programming contests online.

atcoder.jp

解けたが、数学的に正しいのか分からず解いた

最近の自分の中のトレンドとして、解法が数学的に正しいのか考えてから解くようにしたいと思っている(まだ全然できないが笑)。
この問題では、解法を思いついたものの、この解法で確実にACできるかは分からなかった。

とりあえず思いついた解法を書いていく。
「$A_i$の値は一つ前の約数+1にする」というもの。
もう少し厳密に書く。
$A_i$の約数を列挙したときに、$A_i$以外で最大の約数を$j$とする。
$A_i$の値は$A_j$の値に1足したものにする。
このようにすると、とりあえず問題の条件は満たせる。
この解法で数列に現れる値の最大値が最小になるのかはよく分からなかった。

ちょっと証明を考えてみる。
数列に現れる値の最大値をMとする。
Mとしてあり得るもので最小の値は、N以下の約数の個数の最大になる。
「$A_i$の値は一つ前の約数+1にする」という操作を繰り返すと、$A_i$の最大値はN以下の約数の個数の最大になる。
よって、考えた解法でACでき、最大値はN以下の約数の個数の最大になる。

これで証明になっているのかは分からないが、ギリギリ納得できる範囲には納まったと思う。