けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AtCoder ABC 139 D - ModSum (400 点)

これが灰色 diff なのかーーー、マジかーーー!!!
いや、AtCoder プレイヤー、数学強すぎでしょ!!!

問題へのリンク

問題概要

正の整数  N が与えられる。
 1, 2, \dots, N の順列  P をすべて考えたときの、

 \sum_{i = 1}^{N} i %  P_{i}

の値の最大値を求めよ。

制約

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

考えたこと

文句なしの数学ゲー。でも灰色 diff なのは驚く。そもそも問題の趣旨を理解するのもそんなに簡単じゃないと思う。 N = 5 とすると

  • 1 % ○
  • 2 % ○
  • 3 % ○
  • 4 % ○
  • 5 % ○

の総和が最大になるように、○のところに 1〜5 を 1 個ずつ入れる、という問題になる。この場合の答えは

  • 1 % 2 = 1
  • 2 % 3 = 2
  • 3 % 4 = 3
  • 4 % 5 = 4
  • 5 % 1 = 0

が最適になる。これ以上は大きくできない。それは何故だろうか。

上界の証明

まず、「% 1」「% 2」「% 3」「% 4」「% 5」のそれぞれについて、理論的にどこまで余りを大きくできるのかを考えてみよう。そうすると

  • 「% 1」: あまり 0 にしかならない
  • 「% 2」: あまりは最大で 1
  • 「% 3」: あまりは最大で 2
  • 「% 4」: あまりは最大で 3
  • 「% 5」: あまりは最大で 4

という感じになっている。一方、上で作った例を見ると...

  • 5 % 1 = 0
  • 1 % 2 = 1
  • 2 % 3 = 2
  • 3 % 4 = 3
  • 4 % 5 = 4

見事に「% 1」「% 2」「% 3」「% 4」「% 5」の全部について、最大を達成している。よって、合計値も当然最大だ!!!

一般の  N の場合でも、

  • N % 1 = 0
  • 1 % 2 = 1
  • 2 % 3 = 2
  • 3 % 4 = 3
  • ...
  • (N-1) % N = N-1

とすれば、各「% Pi」に対して最大を達成できるので、合計値も最大になる。答えは、

  •  0 + 1 + 2 + \dots + (N-1) = \frac{N(N-1)}{2}

となる。計算量は  O(1)。実装上はオーバーフローに注意 (int 型ではなく、long long 型にしよう)!!!

#include <bits/stdc++.h>
using namespace std;

int main() {
  long long N;
  cin >> N;
  cout << N * (N - 1) / 2 << endl;
}