【ABC139 D】「ModSum」を解く【Python3】

abc139d

コンテスト一覧へ

 

整数Nに対して、{1, 2, … , N} を並べ替えた数列 {P1, P2, … , PN} を選び、iをPiで割った余りをMiとしたとき、「M1+M2+⋯+MN」の最大値を求める問題です。

提出
n = int(input())
print(n*(n-1)//2)

特定の数字を {1, 2, 3, … , N} で割ったとき、考えられる余りの最大値は {0, 1, 2, … , N-1} となります。

そして実際に {N, 1, 2, … , N-1} という数列を割ることで、その余りを出すことができます。

よって最大値は {0, 1, 2, … , N-1} を足し合わせた「N×(N-1)/2」となります。

切り捨てて整数にしたいので「//」を使います。

スポンサーリンク

【ABC139】解説記事リスト

コンテスト一覧に戻る

コメントを残す

メールアドレスが公開されることはありません。