Div.2 B : Hometask

問題概要

与えられる数字から適当に抜き出して並べ替えてできる数のうち、最も大きな数を答えよ。ただし 2, 3, 5 で割り切れる数になる必要がある。

考え方

項目別に考えてみよう。まずは倍数の考え方。そもそも 2 と 5 の公倍数であるから 10 の倍数でなければならない。つまり 1 番下の桁は 0 になる。そして 3 の倍数でもあるから、使う "数字" の和も 3 の倍数になる。もし与えられた数字全てを足して 3 の倍数になるなら大丈夫だが、そうでない場合はいくつか使わない数字を選ぶ必要がある。出来上がる数は桁数の関係から、できるだけ数を抜き取らないのが理想である。可能なら 1 つ、多くとも 2 つの数を省いて作りたい。
実際にそれは可能で、3 で割った余りが合計と等しくなる数字があるならそれを抜けばいいし、無ければ 3 で割った余り（≠0）が異なる（ただし 1 or 2）数を 2 個抜けばいい。与えられた数字群がそのような構成になっていなければ題意を満たす数は構成できない。
あとは残った数を数字が大きな順に並べれば完成。ただしいくつかのコーナーケースにはちゃんと対応する必要がある。

コード

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
int main(void) {
  int n;
  cin >> n;
  vector<int> d(n);
  for (int i = 0; i < n; ++i) cin >> d[i];
  sort(d.rbegin(), d.rend());

  int sum = 0, m[] = {0, 0, 0};
  for (int i = 0; i < n; ++i) {
    sum += d[i];
    ++m[d[i] % 3];
  }
  sum %= 3;

  if (sum) {
    if (m[sum]) {
      for (int i = d.size() - 1; i >= 0; --i)
        if (d[i] % 3 == sum) {
          d.erase(d.begin() + i);
          break;
        }
      sum = 0;
    } else if (m[3 - sum] > 1) {
      sum = 3 - sum;
      int rem = 2;
      for (int i = d.size() - 1; i >= 0; --i)
        if (d[i] % 3 == sum) {
          d.erase(d.begin() + i);
          if (--rem == 0) break;
        }
      sum = 0;
    }
  }

  if (sum || d.size() == 0 || d[d.size() - 1]) {
    cout << "-1\n";
  } else if (d[0] == 0) {
    cout << "0\n";
  } else {
    for (int i = 0; i < d.size(); ++i) cout << d[i];
    cout << "\n";
  }
  return 0;
}