C - Modulo Summation

競プロ

はじめに

競技プログラミング、AtCoder Beginner Contest 103
C - Modulo Summation
言語はC#
何かあればTwitter→@pirorirori_n712まで

問題

問題文

N個の正整数a1,a2,...,aNが与えられます。
非負整数mに対して、f(m)=(m mod a1)+(m mod a2)+...+(m mod aN)とします。
ここで、X mod YはXをYで割った余りを表します。
fの最大値を求めてください。

制約

・入力は全て整数である
・2≤N≤3000
・2≤ai10^5

入力

入力は以下の形式で標準入力から与えられる。

N
a1 a2 ... aN

出力

fの最大値を出力せよ。

解き方

以下を参考にしています。
https://img.atcoder.jp/abc103/editorial.pdf

f(m)を最大にすることを考える。

まず、
f(m)=0になるmの数は以下のように求められる。

m=a1*a2*…aN
例：入力例1

f(m)=0になるｍの数は
m=3*4*6=72

このmから1を引いた数であれば
a1～aNまでの全ての数で
mを割ったときの余りが最大になる。

例：入力例1

余りが最大になるｍの数は
m=3*4*6-1=71
71%3=2
71%4=3
71%6=5

f(m)=0になるmを求めると
かなり大きな数になってしまう、
かつ
f(m)=0になるmから1を引いたものをmにすれば
余りは常に最大になることが分かっていてmを求める必要がないので
a1～aNまでの数から1を引いたものを全て足せば答えが出る。

全体のコード

using System;
using System.Linq;
using System.Collections.Generic;

class Cmondai
{
    static void Main()
    {
        var N = Int32.Parse(Console.ReadLine());
        var A = Console.ReadLine().Split(' ').Select(x => Int32.Parse(x)).ToArray();
        var ans = 0L;
        for (int i = 0; i < N; ++i)
        {
            ans += A[i] - 1;
        }
        Console.WriteLine(ans);
    }
}