AT274の技術だったりなかったり

あっとのTECH LOG

競プロのこととか技術のこととか。たまに日常を書きます。

ABC139 D - ModSum

問題原文

atcoder.jp

問題要旨

 1, 2, ... N を並べ替えた数列  P が与えられる。
これらを適切に並び替えることで、  \sum_{i=1}^{N} i \% P_i を最大化せよ。

  •   1 \leq N \leq 10^{9}

解法

 P = 2, 3, 4, 5 ... N, 1 という感じに並び替えるのが最適。
実際の答えは等差数列の和の公式を使えばいい。

(証明的なの)
答えは、  x_1 \% mod 1 +  x_2 \% mod 2 + ... +  x_N \% mod N の形をしてる。
各modの最大値は  0, 1, 2 ... N - 1 となるから、 結局これを合計したものが上限値。
そして先ほどの並べ方は、その上限値を達成できる。

実装

N = int(input())
print((N - 1) * (1 + (N - 1)) // 2)

感想

ギャグといえばギャグ。