AtCoder Beginner Contest 181 D - Hachi

問題

問題文へ

1から9の数字のみからなる文字列が与えられます。文字列を並び替えて8の倍数が作れますか？

制約

• 1 |S| 2 ×

考えたこと

8の倍数は下3桁が8の倍数かで判定できます。1000は8の倍数であるためです。

制約から0が使われていません。

今回はC問題の3点が同一直線上か判定方法が思いつかない焦りから、D問題に執着してしまいました。

WAを出しながら、それを潰すためのコードを付け足していきました。

#define _GIBCXX_DEBUG
#include <bits/stdc++.h>
using namespace std;
#define rep(i, n) for (int i = 0; i < (n); ++i)
#define all(v) v.begin(), v.end()
using namespace std;
using ll = long long;


int main(void) {
  string S;
  cin >> S;

  // 1桁の場合と2桁の場合
  if (S.size() == 1) {
    if (S[0] == '8') cout << "Yes" << endl;
    else cout << "No" << endl;
    return 0;
  }
  if (S.size() == 2) {
    int num1 = stoi(S);
    if (num1 % 8 == 0) {
      cout << "Yes" << endl;
      return 0;
    }

    reverse(S.begin(), S.end());
    int num2 = stoi(S);
    if (num2 % 8 == 0) {
      cout << "Yes" << endl;
      return 0;
    }

    cout << "No" << endl;    
    return 0;
  }

  // Sに使われている数字と個数を調べる
  vector<int> v(10, 0);
  rep(i, S.size()) {
    v[S[i] - '0']++;
  }

  // 下3桁で8の倍数である文字列
  vector<string> s;
  for (int i = 104; i < 1000; ++i) {
    if (i % 8 != 0) continue;
    string t = to_string(i);
    bool ok = true;
    rep(j, t.size()) {
      if (t[j] == '0') {
        ok = false;
      }
    }
    if (ok) s.push_back(t);
  }

  // 下3桁で8の倍数に使われている数字が
  // Sに使われている数字で足りるか
  rep(i, s.size()) {
    vector<int> need(10, 0);
    rep(j, s[i].size()) {
      need[s[i][j] - '0']++;
    }

    bool ok = true;
    for (int k = 1; k < 10; ++k) {
      if (need[k] > v[k]) {
        ok = false;
        break;
      }
    }
    if (ok) {
      cout << "Yes" << endl;
      return 0;
    }
  }
  
  cout << "No" << endl;
  return 0;
}

解説を読んで

大筋の考え方としては合っていたようで、とても嬉しいです！

私のコードでは下3桁で8の倍数の候補を考えた時に、0が含まれるのを除外していました。原因はkのループを1から始めていたから、0が含まれる8の倍数も条件を満たしていたからです。

0の個数も数えています。与えられた文字列には0が含まれないため、0から始めていたらきちんと判定されていたはずです。

これからも精進しようと思います。