問題

D – Send More Money

プログラミング初級者から上級者まで楽しめる、競技プログラミングコンテストサイト「AtCoder」。オンラインで毎週開催プログラミングコンテストを開催しています。競技…

atcoder.jp

記録

• 2022/4/15 解法わからず。方針だけ確認するも実装でミスる。ACしたが実行時間が少し遅い。
• 2021/12/25 解法○ 実装×。

解法

• 制限時間は \(5\) 秒。
• 使われている文字の種類が \(11\) 種類以上だとUNSOLVABLE。
• 使われている文字を \(0\) から \(9\) に置き換える。これは配列のインデックス。
• \(0\) から \(9\) が入っている配列を作り、順列全探索で全部試す。

コード例

#include <bits/stdc++.h>
using namespace std;
#include <atcoder/all>
using namespace atcoder;
using ll = long long;
using P = pair<int, int>;
#define rep(i, n) for(int i = 0; i < (n); ++i)
// using mint = modint998244353;
// using mint = modint1000000007;
// const int mod = 1000000007;
// const ll INF = 1LL << 60;
// const int INF = 1001001001;

int main() {
  string S1, S2, S3;
  cin >> S1 >> S2 >> S3;

  map<char, int> mp;
  int cnt = 1;

  int n1 = S1.size();
  vector<int> s1(n1);
  rep(i, n1) {
    if(mp[S1[i]] == 0) {
      mp[S1[i]] = cnt;
      cnt++;
    }
    s1[i] = mp[S1[i]];
  }

  int n2 = S2.size();
  vector<int> s2(n2);
  rep(i, n2) {
    if(mp[S2[i]] == 0) {
      mp[S2[i]] = cnt;
      cnt++;
    }
    s2[i] = mp[S2[i]];
  }

  int n3 = S3.size();
  vector<int> s3(n3);
  rep(i, n3) {
    if(mp[S3[i]] == 0) {
      mp[S3[i]] = cnt;
      cnt++;
    }
    s3[i] = mp[S3[i]];
  }

  rep(i, n1) { s1[i]--; }
  rep(i, n2) { s2[i]--; }
  rep(i, n3) { s3[i]--; }
  cnt--;

  if(10 < cnt) {
    cout << "UNSOLVABLE" << endl;
    return 0;
  }

  vector<ll> v;
  rep(i, 10) { v.push_back(i); }

  do {
    ll ans1 = 0;
    ll ans2 = 0;
    ll ans3 = 0;

    if(v[s1[0]] == 0 || v[s2[0]] == 0 || v[s3[0]] == 0) {
      continue;
    }

    rep(i, n1) {
      if(i == 0) {
        ans1 = v[s1[i]];
      } else {
        ans1 = ans1 * 10 + v[s1[i]];
      }
    }

    rep(i, n2) {
      if(i == 0) {
        ans2 = v[s2[i]];
      } else {
        ans2 = ans2 * 10 + v[s2[i]];
      }
    }

    rep(i, n3) {
      if(i == 0) {
        ans3 = v[s3[i]];
      } else {
        ans3 = ans3 * 10 + v[s3[i]];
      }
    }

    if(ans1 + ans2 == ans3) {
      cout << ans1 << endl;
      cout << ans2 << endl;
      cout << ans3 << endl;
      return 0;
    }
  } while(next_permutation(v.begin(), v.end()));

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