ABC198 D 解答

D - Send More Money（1224）

問題文

英小文字からなる文字列 S1, S2, S3 が与えられます。
覆面算 S1+S2=S3 を解いてください。
正確には、次の 3つの条件をすべて満たすような正の整数の組 N1, N2, N3 が存在するか判定し、存在するならばそのうち 1 つを求めてください。ここで、N1,N2,N3を (先頭に余分な 0 をつけないで) 十進表記した文字列をそれぞれ N′1, N′2, N′3とします。
・N′iの文字数は、Si の文字数に等しい
・N1 + N2 = N3を満たす
・Siの x 文字目とSjの y 文字目が等しいとき、またその時に限り、N′のx文字目とN′jのy文字目が等しい

制約

S1,S2,S3は英小文字のみからなる長さ1以上10以下の文字列

考察

この問題はいわゆる

虫食い算

です。小学生の頃にやったよ！という方も多いのではないでしょうか。

  2 1 5
+  □ 7
   3 7 2

□に入る数字はなんでしょう。

こんなやつです。この場合は□=5ですね。もうちょっと増やします。

    2 1 ○
+    □ 7
    3 7 △

こうすると色々と考えられます。
(○,△,□)=(1,8,6), (9,6,5),...

などなんでも良しです。数を変えてもっと虫食いを増やします。全部虫食わせてしまいましょう。○とかだと足りないのでアルファベットで置き換えます。

    send
 + more
  money

ということで本問題になるわけですね。
ここから本問題を考えていきます。

この問題で一番大切なのは、３つ目の制約の

またその時に限り

という部分です。これを言い換えますと

同じ記号の数字は同じ
かつ
異なる記号に入る数字は必ず異なる
（同じ数字は入らない）

となります。上の方はまあそうだろうな、という感じですが、下の方はこの問題を解くのにとっても大事な要素となっています。

この条件からわかることとして、

記号が11種類上あったら解なし

があります。１０進数の数字は0 ~ 9までの10種類しかありませんので、もし11種類以上あったら困ってしまいます。ただ、逆に言えば本問題では10種類の記号までしか考慮する必要がないということです。

ですので、最大10種類の記号に10種類の数字をそれぞれ当てはめて、S1+S2=S3を満たしているかを確認すれば答えが求まりそうです。また、その組み合わせの数は10!です。だいたい10^6です。なんか間に合いそうですね。幸いなことに制約も5sといつもより長いですので、定数倍が重くてもなんとかなりそうです。

次に、当てはめ方の説明をします。

今回は「next_permutation」という関数を用いました。私はC++ですが他の言語にも似たような機能があると思います。もしないのならいい感じに頑張ってください。

この関数は、ソート済みの数列を与えると全ての順列を取得してくれるすごいやつです。

例： {1,2,3}
1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

全部取得してくれます。本問題では

{0,1,2,3,4,5,6,7,8,9}

の順列に対しnext_permutaionを行い。その先頭から順番にa, b, c, ... と当てはめていきましょう。

{0,1,2,3,4,5,6,7,8,9} : a = 0, b=1, c = 2
{8,4,2,5,1,0,3,9,7,6} : a = 8, b=4, c = 2
(生成順は適当です)

最後に実装の流れを説明します。

１、どの記号が使われているか調べる
２、11種類以上なら解なし
３、next_permutationで順列を生成
４、先頭から当てはめる
５、先頭の数字に0がきてたら３に戻る
６、S1+S2=S3が成立してたら解を出力
　してなかったら３に戻る

こんな感じですね。これで本問題は解けました。

実装

 #include <bits/stdc++.h> #define  rep(i,n) for(int i=0;i<n;++i) #define  reps(i,s,n) for(int i=s;i<n;++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;

int main()
{
   string s1,s2,s3;
   cin >> s1 >> s2 >> s3;
   vector<char> C;
   vector<char> C_top;

   //使われている文字と
   //先頭に使われている文字を取得。
   //findで見つからなかったら追加。
   auto get_char =[&](string s)
   {
       if(find(C_top.begin(),C_top.end(),s[0]) == C_top.end())
       {
           C_top.emplace_back(s[0]);
       }
       for(auto c : s)
       {
           if(find(C.begin(),C.end(),c) == C.end())
           { 
               C.emplace_back(c);
           }
       }
   };
   get_char(s1);
   get_char(s2);
   get_char(s3);
   //１１個以上の文字があったら絶対に満たせない。
   //同じ文字は同じ数字　かつ　同じ数字は同じ文字
   if(C.size() > 10)
   {
        cout << "UNSOLVABLE" << endl;
        return 0;
   }
   //文字列を数字列に変換（mapの変換テーブルを用いる）
   auto convert = [](string s,map<char,int> mp)
   {
       ll now = 0;
       for(auto c:s)
       {
           now *= 10;
           now += mp[c];
       }
       return now;
   };

   vector<int> num = {0,1,2,3,4,5,6,7,8,9};
   do
   {
       //変換テーブルを作成（数字の当てはめ表）
       map<char,int> mp;
       rep(i,C.size()) mp[C[i]]=num[i];
       //先頭に0がきたらダメ！
       bool ng = false;
       for(auto t:C_top) if(mp[t] == 0) ng = true;
       if(ng) continue;
       //条件を満たすか確かめる
       ll ans1,ans2,ans3;
       ans1 = convert(s1,mp);
       ans2 = convert(s2,mp);
       ans3 = convert(s3,mp);
       if(ans1+ans2==ans3) 
       {
           cout << ans1 << endl;
           cout << ans2 << endl;
           cout << ans3 << endl;
           return 0;
       }
   } while (next_permutation(num.begin(),num.end()));
   cout << "UNSOLVABLE" << endl;
   return 0;
}

あとがき

「虫食い算を全部試すだけ」なのですが、その実装は少しばかり大変でした。

next_permutationを用いていますが、この関数は本来は「次の順列を取得、先頭の順列に戻ったらfalseを返す。」という挙動のようです。それをうまく使うことで、全順列を生成しています。ですので、この関数に渡す前は「昇順にソート」することを忘れないようにしましょう。