日刊競プロ ABC 139 - D - ModSum-

D - ModSum

問題文
整数 N に対して、{1,2,...,N} を並べ替えた数列 {P1,P2​,...,PN​} を選びます。そして、各 i=1,2,...,N について、i を Pi​で割った余りを Mi​とします。M1​+M2​+⋯+MN​の最大値を求めてください。

制約
N は 1≤N≤10**9
を満たす整数である。

考えたこと

自分で一旦考えたが、解法が思いつかなかったので、解説を見た。

実験的に解法を導いており、そういうやり方もあるのかと目から鱗が落ちた。

実験的にNと解の規則性を見つけるコード

N = int(input())
import itertools
lis = [i+1 for i in range(N)]
print (lis)
maxan = 0
for v in itertools.permutations(lis):
 ans = 0
 for i in range(N):
   ans+= lis[i]%v[i]
 if ans>=maxan:
   maxan = ans
   print (v)
print (maxan)

N ：1,2,3,4
解：0,1,3,6

というような階差数列であることがわかる。

a>=2のとき、an=a1+Σbnより

bn=1+(n-1)*1=nとなり

an=0+Σbkより（n-1)*n/2で解がでることがわかる。

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