C - Modulo Summation / ABC103 - D言語で競プロ

問題

$\max\{f(m) = \sum (m \% a_i )| m \geq 0, m \in \mathbb{Z}\}$ を求めよ。

https://beta.atcoder.jp/contests/abc103/tasks/abc103_c

解法

まず任意の $i$ について、 $0 \leq (m \% a_i) \leq a_i - 1$ であることから、 $f(m)$ の上限は $\sum a_i - N$ であることはすぐに分かります。そして、サンプルなどを見ているとmを上手くとれば $f(m)$ をこの上限に一致させることが出来るのではないかと予想が立てられます。

実際この予想は正しくて、 $m = a_1 a_2 \dots a_N - 1$ とすると、任意の $i$ に対して $m \equiv -1 \equiv a_i - 1 (\mod a_i)$ となることが分かり、このとき $f(m) = \sum a_i - N$ となり上限に一致させることが出来ます。

感想

予想を立てるところまではすぐにいったのですが、それを証明するのに意外と時間がかかってしまいました。分かってしまえば簡単なのですが、 $a_i$ が互いに素でないときは成り立たなかったりするのではないかと考えたり、最近知った中国剰余定理かなとか考えてしまいました。modの世界では-1が最大になるというのは面白いですね。

実装

今回はJavaです。最近Javaの練習をしています。競プロにはやや使いづらいような印象ですが、uwiさんなどは普通に使いこなしているので凄いなと思いました。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n = sc.nextInt();
        int ans = 0;
        for (int i = 0; i < n; i++) {
            int a = sc.nextInt();
            ans += a - 1;
        }

        System.out.println(ans);
    }
}