AtCoder ABC 063 C - Bugged (4Q, 茶色, 300 点)

面白い問題。最近はこういうの、あまり見ないかもしれない。

• 問題へのリンク

問題概要

個の正の整数 が与えられる。

これらからいくつか選んで総和をとる。ただし、その値が 10 の倍数である場合には、その値は 0 になってしまう。

この値の最大値を求めよ。

制約

• 
• 

考えたこと

正の整数をいくつか選ぶ方法をすべて試すことを考えると、 通りの方法がある。ビット全探索を用いると、この 通りの方法をすべて調べることができる。しかし、 なので、この方法では間に合わない。

まず、「すべて足す」方法を試してみよう！！！　

もし仮に、 ( とする) が 10 の倍数でないならば、その値が最大である。

それでは、 が 10 の倍数になってしまったときはどうしたらよいだろうか。その場合は、 から 1 個の値を引いたものを試していくことが考えられるだろう。

ここで重要な考察として、もし がすべて 10 の倍数であるならば、結局 がすべて 10 の倍数であるということが分かる。そして、 がすべて 10 の倍数であるとき、これらからどのように選んで総和をとっても 10 の倍数になってしまうのだ（この場合の答えは 0）。

以上の考察をもとに、次の 3 つの場合に分けて考えると良さそうだと分かる。

---

• がすべて 10 の倍数であるとき：答えは 0
• が 10 の倍数でないとき：答えは
• が 10 の倍数であって、 の中に 10 の倍数でないものがあるとき：（後述）

---

3 つ目の場合を最後に考える。

が 10 の倍数であって、 の中に 10 の倍数でないものがあるとき

この場合は、 の中に 10 の倍数でないものが存在する（そうでなければ、 がすべて 10 の倍数になるため）。直感的には、そのうち最大の数を答えればよさそうだ。

気になるのが、 から 2 個以上の値を引く場合も考えた方が、答えが大きくなるケースもあるのではないか？？ということだ。これについて一応考えておこう。少し考えると、次のことが示せる。

---

を正の整数とし、 は 10 の倍数であるとする。

が 10 の倍数でないならば、 のいずれかは 10 の倍数でない。

---

証明

と がともに 10 の倍数であると仮定する。このとき、 が 10 の倍数であることから、

(= )

も 10 の倍数である。これは矛盾である。

(証明終わり)

であるから、 から 2 個の値を引いたものが最大になることはないと言える（3 個以上の値を引いたものが最大になることがないことも同様に言える）。

コード

以上の解法は の計算量で実装できる。

#include <bits/stdc++.h>
using namespace std;
                                 
int main() {
    int N, sum = 0, res = 0;
    cin >> N;
    vector<int> s(N);
    for (int i = 0; i < N; i++) {
        cin >> s[i];
        sum += s[i];
    }

    if (sum % 10 != 0) res = sum;
    else {
        for (int i = 0; i < N; i++) {
            if ((sum - s[i]) % 10 != 0) res = max(res, sum - s[i]);
        }
    }
    cout << res << endl;
}