これが灰色 diff なのかーーー、マジかーーー!!!
いや、AtCoder プレイヤー、数学強すぎでしょ!!!
問題概要
正の整数 が与えられる。
の順列 をすべて考えたときの、
%
の値の最大値を求めよ。
制約
考えたこと
文句なしの数学ゲー。でも灰色 diff なのは驚く。そもそも問題の趣旨を理解するのもそんなに簡単じゃないと思う。 とすると
- 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 % 1 = 0
- 1 % 2 = 1
- 2 % 3 = 2
- 3 % 4 = 3
- ...
- (N-1) % N = N-1
とすれば、各「% Pi」に対して最大を達成できるので、合計値も最大になる。答えは、
となる。計算量は 。実装上はオーバーフローに注意 (int 型ではなく、long long 型にしよう)!!!
#include <bits/stdc++.h> using namespace std; int main() { long long N; cin >> N; cout << N * (N - 1) / 2 << endl; }