ABC198 D-Send More Moneyをやさしく理解する！
問題はこちらからどうぞ～
ざっくりなイメージ
本文には難しいことが色々書かれていますが、概要はこんな感じで捉えてもらえれば大丈夫です。与えられる文字列に含まれる各アルファベットに数字を当てはめたときに、足し算が成立するような組み合わせを出力してください。ということです。
解答への手がかり
今回注目すべきは、
- 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")
AtCoder Beginner Contest 198の感想
AtCoder Beginner Contest 198に参加しました。先週はABCが開催されなかったので、2週間ぶりのコンテストということでかなり緊張していました。結果はA,B,Cの3完で無事レートを伸ばせて一安心です。以下、簡単にコメントしていきます。
A問題 - Div
基本的にABCは前から解いていく方針を取っているので、一番最初に手を付けました。区別のないN個のモノを2人（ヒトは区別する）で分ける方法は何パターンあるのか？という問題。1問目ということでガチガチに緊張しており、N-2個の〇と1本の棒を描いてN-2+1C1と計算しました。
実は、2人で分けっこするので片方が貰う個数が確定した時点でパターンが確定し、その貰い方が1個～N-1個で解答のN-1通りが一瞬で求まるみたいです。最速の人は10秒で提出していたのでまだまだ無駄が削れそうです（）
B問題 - Palindrome with leading zeros
整数Nは回文か？ただし、先頭に0を付け放題。という問題。最初に思い付いたのは、Nの先頭に1個ずつ0をつけ足していって、その都度回文かどうかの判別をする方針。しかし、問題文をよく読んでみると「付け足す０の数」は問われていなかったので、Nの後ろにくっついている0を全部削除した時に回文の判定をする方針に変更。サンプルケースも一発であってたので、かなりいい感じに実装できたと思います！
ちなみに、公式解説は前者の解法、ユーザー解説は後者の解説をされていました。Nは高々10桁なので前者の方針で問題ないみたいです。ぐぬぬ
C問題 - Compass Walking
一回の操作で一定距離離れた場所にしか移動できない高橋君が目的地にたどり着く最小回数を求めよという問題。基本的に目的地までの最短距離＜(一回の移動距離)*(移動回数)となる最小の移動回数を求めればいいわけですが、C問題だと何かしら罠が敷かれがちなのでまだ安心はできません。ここで、円の定義が定点 Oからの距離が等しい点の集合でできる曲線なことを思い出して、1回の移動では原点中心の円上に目的地がないとたどり着けない（つまり円の内側に移動するには2回の移動が必要）ことに気づきました。（こちらのツイートが分かり易かったので引用させていただきます）
アライグマ「ABC198のwriterだったのだ！ C問題は、(X,Y)までのキョリをDとして、だいたいceil(D/R)が答えなのだ。D<Rのときは1歩じゃ行けないから、場合分けするのだ。2歩で行けることの証明は……この図を見たらわかるのだ！」 pic.twitter.com/QGLDCXHwy7
— 競技プログラミングをするフレンズ (@kyopro_friends) 2021年4月11日
かなりペナを出してる方が多かったのでノーペナで出せたのは結構嬉しかったです。
D問題 - Send More Money
覆面算をプログラミングで解きなさいという問題。方針が立たなかったので色々ググってみると、プログラミングの練習としては一般的（？）な課題らしく特定のケースでの実装例がたくさん出てきました。そんなこんなで、「各文字に対して0-9を割り当てて全探索すればいけそう！」というところまで行き着きましたが、与えられた文字に数字を割り当てる段階で実装に詰まってしまいそのままコンテスト終了。
E問題 - Unique Color
グラフということで飛ばしました。最短、電車、村、道あたりのワードが見えただけで目を逸らしたくなっちゃいます・・・。
順位表を眺める限り、D問題よりも解いている人が多いのでグラフの問題にも取り組んでいきたいです。
F問題
見てません。いつか全完してTLでのんびり余生を過ごしたいものです。
まとめ
今回はCからDで難易度の差があったので速解きで良いパフォーマンスが出ましたが、そろそろできることを増やさないと停滞しそうな感じがしています。その対策もこのブログを始めた目的の１つなので本業に影響しない程度に頑張ります！
