ABC198 D-Send More Moneyをやさしく理解する！

問題はこちらからどうぞ～

atcoder.jp

ざっくりなイメージ

f:id:naturence:20210413222451p:plain

本文には難しいことが色々書かれていますが、概要はこんな感じで捉えてもらえれば大丈夫です。与えられる文字列に含まれる各アルファベットに数字を当てはめたときに、足し算が成立するような組み合わせを出力してください。ということです。

解答への手がかり

今回注目すべきは、

1つの文字には1桁の数字があてられる

異なる文字には同じ数字をあてることができない

の２つです。

１．から１文字にあてる数字の候補は0-9の10通りであること、２．から最大でも10種類の文字しか使えないことがわかります。（１１種類の文字があると確実に異なる2文字が同じ数字を割り当てられることになります）

数字の割当先が最大で10種類、数字が全10種類であるから、考えられる割り当て方の全パターンは最大で10！=3628800通りです。今回は実行時間制限が5秒なのですべての割り当て方を知らべて（全探索！）、足し算が成立するかチェックする方法で(pypyなら)間に合います！

実装の流れ

今回の方針は全探索！
今回は以下のステップで実装します。

入力をリストで受ける
文字の種類を抽出する
文字の種類数が1１種類以上ならNG
抽出した各文字に対して数字(0-9)を割り当てる
与えられた文字列に数字を割り当てて計算が成立するか判定

いざ実装(Python)

後に順列を計算するためにitertoolsを使います。

from itertools import permutations

入力をリストで受ける

S=[list(map(ord,input()))[::-1] for _ in range(3)]

ここでは

文字をASCIIコードに変換→数字ならリストのインデックスと対応付けることができる
リストに格納
リストを逆順に変更→最後の文字を数字に直す操作の時に都合がいい

という操作を3つの文字列に対して行っています。

文字の種類を抽出する

setで重複する文字を消して文字の種類を抽出します。setでは数字を勝手にソートしてくれます。

chars=set(S[0]+S[1]+S[2])

文字の種類数が11種類以上ならNG

上述したとおりです。

if len(chars)>10:
	print("UNSOLVABLE")
	exit()

抽出した各文字に対して数字(0-9)を割り当てる

前処理として座標圧縮を行います。サイズがバラバラな数字を連続する順番に圧縮します。
詳しくはこちらが参考になると思います。
algo-logic.info

#ASCIIコードは8bitなので2**8=256
comp=[0]*256
#今回使っている文字を小さい順に番号付けして扱いを楽にする
for i,code in enumerate(chars):
  comp[code]=i
 
#配列で使っている文字コードを座標圧縮後の数字に置き換える
for i in range(3):
  for j in range(len(S[i])):
    S[i][j]=comp[S[i][j]]

各文字に対して0-9を割り当てます。この問題では、異なる文字には異なる数字が割り当てられるので順列で割り当てパターンを計算します。

#文字に数字を割り当てる
for perm in permutations(list(range(10)),len(chars)):
  #先頭の文字に0は割り当てられないので、そのケースが来たらスルーする
  if perm[S[0][-1]]==0 or perm[S[1][-1]]==0 or perm[S[2][-1]]==0:
    continue
  #計算用の配列のリセット
  tmp=[0,0,0]
  for i in range(3):
　  #文字を数字に直す
  　#桁をenumerateで表現
    for j,code2 in enumerate(S[i]):
      tmp[i]+=perm[S[i][j]]*10**j
  #実際に計算する
  #解を見つけたら終了
  if tmp[0]+tmp[1]==tmp[2]:
    print(*tmp)
    exit()
#成立する組み合わせがない場合
print("UNSOLVABLE")

コード全体

from itertools import permutations

#入力をリストでうける
S=[list(map(ord,input()))[::-1] for _ in range(3)]
#文字の種類を集める
chars=set(S[0]+S[1]+S[2])


#種類が10以上の場合は絶対に数字が被るためNG
if len(chars)>10:
	print("UNSOLVABLE")
	exit()
    
# 座標圧縮で散らばった文字（コード）を順番に置き換えて
#扱いやすくする
#ASCIIコードは8bitなので256で絶対に収まる
comp=[0]*256
#今回使っている文字を小さい順に番号付けして扱いを楽にする
for i,code in enumerate(chars):
  comp[code]=i

#配列で使っている文字コードを座標圧縮後の数字に置き換える
for i in range(3):
  for j in range(len(S[i])):
    S[i][j]=comp[S[i][j]]

#今回使われている文字に対して0-9のいずれかを割り当てる
#順列を用いて全探索
for perm in permutations(list(range(10)),len(chars)):
  #先頭の文字に0は割り当てられないので、そのケースが来たらスルーする
  if perm[S[0][-1]]==0 or perm[S[1][-1]]==0 or perm[S[2][-1]]==0:
    continue
  #計算用の配列のリセット
  tmp=[0,0,0]
  for i in range(3):
    #桁をenumerateで表現
    for j,code2 in enumerate(S[i]):
      tmp[i]+=perm[S[i][j]]*10**j
  #解を見つけたら終了
  if tmp[0]+tmp[1]==tmp[2]:
    print(*tmp)
    exit()

print("UNSOLVABLE")

Tsuna lab

国の端っこで---しながら競技プログラミングなるものをしてみます