AtCoder Beginner Contest 203（Sponsored by Panasonic）の感想

AtCoder Beginner Contest 203（Sponsored by Panasonic）に参加してきました！結果はABCの３完(perf:937)でレートが44上がりました。以下簡単にコメントしていきます。

A - Chinchirorin

atcoder.jp

3つのサイコロを投げて、出目が全て揃ったらその値、出目が２つ被ったら残りの一つの出目、出目が揃わなかったら0を出力せよという問題。

前回に引き続きサイコロ問題。if文を使って出目が２つ被ったら残りの一つの出目を出力し、それ以外は０を出力するようにしました。こうすれば３つの出目が同じ場合もカバーできるのでコード長が短くて済んで衛生的です。

ここまでで1分38秒。なかなかいいペースで解けたと思います。 

B - AtCoder Condominium

atcoder.jp

N階建てのマンションの各階にK部屋ある。i階のj部屋目の部屋番号をi0jとするとき、すべての部屋番号の総和を求めよという問題。

つまるところiとjは別々に考えてよいので、3桁目と１桁目で別々に計算して最後に和を取ることを考えました。注意すべきは1-indexにすることと、iの成分は３桁目なので100倍してから加えることぐらいですかね。

ここで5分18秒。悪くないペースだと思います。

C - Friends and Travel costs

atcoder.jp

所持金K円で村番号０の村からスタートして、なるべく番号が大きい村へ移動することを考えます。i村からi+1村へは1円のコストで移動することができ、訪れた村に友達がいる場合はB円もらうことができます。最終的にたどり着ける村を出力せよという問題。

問題文を見た瞬間この問題を思い出しました。

ABC185 B - Smartphone Addiction

atcoder.jp

今回の位置AでB円もらえるという条件は、この問題は時刻Tでバッテリーが(B-A)回復するのと同じように見ることができます。この問題ではすべての時刻でバッテリーをチェックするのではなく、バッテリーの充電タイミングでバッテリーが切れるかどうかのチェックをしていました。

そこで今回もお金を貰えるタイミングにその村にたどり着けるかのチェックを行い、

• すべての友人からお金をもらう
• 途中で所持金が0になる

タイミングで最終的な到達点を計算して出力しました。

ここまでで19分55秒。少し早いだけでパフォがかなり伸びたようなのでちょっと悔しいです。ただ類題にすぐに気づけたのは精進の成果がでたということなのでよかったと思います。

D - Pond

atcoder.jp

各マスに高さが与えられたN×Nマスのグリッド内に自由にK×Kの区画を取るとき、この区画内の最小の中央値を出力せよという問題。

中央値の扱い方が難しいなぁと思い初手でGoogle検索。「AtCoder　中央値」でggrと決め打ち二部探索法が出てきました。

決め打ち二部探索法は、競プロ典型90問やZONeコンに出題されていたのでかなり記憶に新しいですね。

【1 日目】
今日の典型問題です。解説は翌日の 7:40 に投稿されます。なお、要望が多かったので入力形式・入出力例を GitHub に追加しています。#競プロ典型90問 pic.twitter.com/cc8NTPhFLc

— E869120@公開アカウント (@e869120) 2021年3月29日

atcoder.jp

 そこで「中央値がX以下になることがあるか」という判定条件で二分探索を行うことを考えました。この判定は各マスの値がXより大きいか否かで-1,1に変換して区画内の和を取れば出来そうです。ここで区画の和は二次元imos法か二次元累積和を使えば高速化できるとTwitterで見たことがあったので、今回は二次元累積和を採用することにしました。

【28 日目】
昨日の解説と今日の典型問題です。今日は標準的な難易度（★4）となっています。なお、AtCoder ジャッジには 15 時頃に追加される予定です。（昨日と同様、入力形式・入出力例は GitHub を参照のこと） #競プロ典型90問 pic.twitter.com/6bx90GPcQb

— E869120@公開アカウント (@e869120) 2021年4月29日

 つまり流れとしては、

1. 解をｘと仮定して、各マスの高さとxを比較して-1と１に変換
2. Ｋ×Ｋの区画内の和を二次元累積和を取り、中央値がX以下になるものが存在するかをチェックする。
3. これを二分探索で知らべて条件を満たす境界の右側の値を出力

を実装しようと思っていました。

結局、二次元累積和の実装で失敗してしまい解けませんでした。

まとめ

最近精進はあまりできていませんでしたが、コンテストの復習と典型90を毎日考えることをしていたおかげか、問題文を見たときにあれ使えそうかな？みたいな発想が出やすくなった気がします。今回もD問題は解けませんでしたが解法は大きく外していなかったのでもう一息だと思います！（そう思いたいです）

エイシングプログラミングコンテスト2021（AtCoder Beginner Contest 202）の感想

エイシングプログラミングコンテスト2021に参加してきました！結果はA,B,Cの3完でしたが、低難易度の問題に時間をかけてしまいパフォーマンスは449。再び借金生活に逆戻りです；；以下簡単にコメントしていきます。

A - Three Dice

atcoder.jp

3つのサイコロを投げたとき、サイコロの裏面の数の総和を求めよという問題。

サイコロには対面の数の和が常に７になる性質があるので、サイコロの目をa,b,cとすると、(7-a)+(7-b)+(7-b)を計算して終了。

特に詰まることはなく1分ちょいで提出。いい感じ。

B - 180°

atcoder.jp

与えられる文字列を180度反転させよという問題。

入力される数字を後ろから順に選んできて、操作に書いてある通りの変換をif文で行って終了。

基本的な文法が分かっているかのチェック問題に５分かけるのはちょっとダメかも。

C - Made Up

atcoder.jp

長さNの数列A,B,Cが与えられたとき、Ai=BCjを満たす( i , j )の組を求めよという問題。

まずiとjを全探索する方針が簡単そうだけど制約が10^5なので間に合わなそう(O(N^2)となるため)。これは工夫して全探索のパターンだと思い典型90問を思い出してみると、変数が複数存在するように見えても実は1つの変数に注目するだけで解けるケースがあったなーと気づいた。そこで今回はiに対して全探索を行う方針を取ることにした。

今回は条件が複雑そうな数列Bに注目してみた。iが定まると

• B[i]の数
• 数列Cのうち、i (index)を指定する項数（＝C[j]の項数）
• 数列Aのうち、B[i]を指定する項数(＝A[i]の項数)

の３つを得ることができる。下2つはそれぞれA.count(B[i]) C.count( i )で求められるのでこの積をとってAC！！

 ？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？？

O(N)なのでTLEにはならないと思ってたんだけどこの方針間違ってた？？？なんて思って迷走していたら、

 for文の内側でのカウントが原因でした。for文の外側で collectionsのCounterを用いて前もって計算を済ませて置き、for文の中では掛け算するだけに変更したら無事AC。

ここまで46分。PythonとPyPyでそれぞれ誤答を投げてしまったので計2ペナで合計56分です・・・。

D - aab aba baa

atcoder.jp

A個のaとB個のbを並び替えてできる文字列のうち、辞書順でK番目のものを求めよという問題。

制約が小さければ中高の入試で出題されてもおかしくない重複順列の典型問題。基本方針は文字列を左から決めていき、一番左の文字がaの時に後ろに来る文字列のパターン数がKより大きければaで確定される。そうでなければbが一番左の文字となる。これを文末まで繰り返していけば解けそう。

問題に取り組んで5分ほどでこの方針に行きついてサンプル１は合わせられたものの、サンプル２が全く合わせられずにコンテスト終了。

公式解説はDPによる実装でしたが、ユーザー解説は同じ方針を取っていたのであとは実装力ですね。

blog.hamayanhamayan.com

まとめ

前回のようなD問題で手も足もでないような状況ではなかったので、あまり感触は悪くありませんでした！（パフォはあまり出ていませんが💦）それにしても今回のC問題はあまりに多くの人が解いててびっくりしましたね。Bまではそこそこのペースで解けていたせいもあり、やっとのことでCをACしたもののほとんど順位が上がらなくてちょっと悲しかったです・・・。

マイナビプログラミングコンテスト2021（AtCoder Beginner Contest 201）の感想

マイナビプログラミングコンテスト2021に参加してきました。B問題でWAが出た瞬間、プログラミング自体が2週間ぶりだったことを言い訳にしようとかアホなことを考えていましたが気合で3完。以下簡単にコメントしていきます。

A - Tiny Arithmetic Sequence

atcoder.jp

長さ３の数列を等差数列にできますかという問題。等差数列は後ろの項の方が大きいので、まず小さい順にソート。そして1項目と3項目の和が2項目の2倍に等しいかで等差数列かどうかの判定をしました。

最初は問題文の「数列を並びかえて」の部分を読み飛ばしており、ソートを忘れて少し時間をロスしてしまいました。急がば～って感じです。

B - Do you know the second highest mountain?

atcoder.jp

二次元配列のうち、2つ目の要素が二番目に大きい要素を出力せよという問題。2次元配列を2つ目の要素で小さい順にソート（pythonではkeyとlambda式）して後ろから2番目の要素を出力しました。

コンテスト開始5分で提出したところまさかのWA。原因が全く分からなかったので一旦C問題を先に取り掛かりました。どうやら数字を文字列として受け取ってソートしたことが原因だったみたいです。

strでの大小は辞書式順序での大小になるので, '123'<'23' になってしまい, 希望通りになりません.

— Kazun ◢͟⁴⁶ (@Kazun_kyopro) 2021年5月15日

C - Secret Number

atcoder.jp

４桁の暗証番号を作成する。0-9までの数字がそれぞれ「絶対に使う数字」「使わない数字」「使ってもよい数字」に分類されているとき、4桁の暗証番号のパターン数を求めよという問題。

最初は「絶対に使う数字」を先に配置し、その後に「使ってもよい数字」を残った場所に並び替える方法を考えました。しかし、どうやっても1個目のサンプルが合わず数学で求めるのを諦めました。

今回の問題のポイントは「暗証番号が４桁」というところで、全パターンを試しても10^4通りしかないんですよね。そこで全パターンを試して、

1. 「絶対に使う数字」の集合が「暗証番号に使った数字」の集合に包含されるか
2. 上の2つの差集合が「使ってもよい数字」の集合に含まれるか

の2つの条件を満したパターンを数えました。Pythonのsetを使うと集合の管理が楽でした。

D - Game in Momotetsu World

atcoder.jp

+マスと-マスが設置してある2次元平面上のコマを2人で交互に最善手で操作するとき、どっちが勝つか求めよという問題。ただし、コマは左上からスタートし、右or下にしか移動できない。

最善手をどうやって求めるのかがわからず終了。こういった問題にも対応できるようになりたい。

まとめ 

 今回はCの全探索に気づくのに時間がかかってしまいパフォーマンスがあまり伸びませんでしたが、気づいてからはノーペナで実装できたのはよかったと思います。もう少し自分の使える手法を増やしていくともっと対応できる範囲が増えそうだなーと感じたABCでした。

【随時更新】AtCoderで過去に詰まった発想・知識集

コンテストや精進中に使えそうな知見を得る度に追加していきます。正確性は保証しません。

文字列操作

・反転操作→反転している状態かどうかだけを記録し、実際には反転を行わない

・文頭, 文末に対する追加削除操作→listではなくdequeを用いると早い

・辞書順でK番目のものを求める→左の文字から決めていく

グリッド

・はみ出るか否かの処理→S[max(0,i-1) : min(W,i+2)]で if 文の省略

数列

・A-BがKの倍数→AをKで割ったあまりとBをKで割った余りが同じ

・区間の和→累積和orいもす法

グラフ

・AからBにいけるか（無向グラフ）→UnionFindが使える

・2回の移動で～→真ん中の街を基準に考える

〇〇探索

・操作が難しいけど制約が小さい→全探索

・3変数の全探索だと間に合わない→式変形して2変数の全探索（整数条件に持ち込む）

・調べたいデータに単調性（昇順or降順）がある→二分探索

・二分探索したいデータがリストで与えられている→bisectの利用

・最大値の最小化→決め打ち二分探索

全般

・AからBを作れるか判定せよ→Bから逆の操作をしてAに出来るか考えてみる。

・2択（ある・なし）で管理がしたいとき→bitで管理

・bit管理下で複数の要素が条件を満たしているか調べたい→AND/ORの利用

・問題を解くのに不必要な情報の簡略化→bitでの管理/座標圧縮

・for文のループが遅い→前計算の検討

ZONeエナジー プログラミングコンテスト “HELLO SPACE” の感想

ZONeエナジー プログラミングコンテスト “HELLO SPACE”に参加してきました；；このコンテストは新発売の"ZONe mad_hacker Ver.1.0.0"の広報も兼ねているということで、ちゃんと近所のセイコーマートで購入して参加しました。結果はA,B問題の2完で少しレートが上がりましたが、残念ながら前回失った分の借金は返せませんでした；；

A - UFO襲来

ストーリー：UFOのせいでコンテスト中止→ZONeを買いに行く

atcoder.jp

与えられる文字列の中に"ZONe"という文字列が何個含まれるか出力せよという問題。pythonではcountという関数で特定の文字列が何個含まれるか調べることができるので秒殺。(1分38秒) やっぱりpythonしかかたん。

B - 友好の印

 ストーリー：UFOの操縦プログラムをKARATEで破壊する

atcoder.jp

 自分とUFOの間に障害物が何もなくなるように自分の高度を変えるとき、その高さの最小値を出力せよという問題。自分のいる位置は一番高い障害物とUFOの位置によって定まるため、すべての障害物とUFOを結ぶ線分のうち一番大きいy切片を出力。二点を通る直線の傾きを(xの増加量)/(yの増加量)と書いていることに気づかず時間を溶かしてしまいました。ここまでで12分5秒。もうすこし縮められたはず・・・！

C - MAD TEAM

ストーリー：MADな仲間が欲しい→AtCoder上の競プロer

atcoder.jp

５つのパラメータが与えられたN人から3人選んでチームを作る。チームの能力は各パラメータの最大値で定義され、チームの能力のうち最小のパラメータが最大値を出力せよという問題。最小値の最大化は決め打ち二分探索だと競プロ典型 90 問の1問目でやったので実装しようとするも、二分探索のcheck関数で各能力をどう評価するかのところで詰まってしまい、D問題へ移動しました。二分探索だと気づけただけでも成長できてると思います！

【1 日目】
今日の典型問題です。解説は翌日の 7:40 に投稿されます。なお、要望が多かったので入力形式・入出力例を GitHub に追加しています。#競プロ典型90問 pic.twitter.com/cc8NTPhFLc

— E869120@公開アカウント (@e869120) 2021年3月29日

D - 宇宙人からのメッセージ

ストーリー：メンバーがそろった（揃えられませんでした）→暗号解読しよう

atcoder.jp

今回の戦犯

与えられる文字列に従って操作を行い、得られる文字列を出力せよという問題。今回の操作は、文字が"R"だった場合は文字列の反転、そうでない場合はそのまま追加。ただし、生成した文字列に連続する文字があればそこを削除する。

 文字列の反転する操作がある場合は、実際に反転はせずに反転しているかの記録だけ行うと早く計算できるやつだと気づきとりあえず実装。（先週のABCでもでてた）連続する2文字を消す操作は問題文通り文字列の生成を行った後に行いました。300点問題ならこれで通るだろうと思って投げるもTLE。

文字列での操作が遅いのかと思いリストに変更してもう一回投げる。これもTLE。これはどこかのパートが根本的におかしいと思ったので、文字列の生成のパートを見直し始める。ここで、与えられる文字列を"R"で分割して配列に入れ、その配列のサイズの偶奇によって文字の削除前の配列が簡単に生成できることに気づく。この生成した文字列を元にさっきと同じ削除の操作を行って投げてみる。ちょっとだけ早くなるも結局TLE。

TLEの原因が削除操作だと気づき文字列の生成する操作と同時に削除する操作も行うことを考えるも、時間がたりずにコンテスト終了。ちなみにこの回答もTLEでした。

正解するためには

• 文字が連続するときは文字を追加する代わりに削除（これは気づいた）
• 反転操作は実際に行わずに追加位置を変更する(これも気づいた)
• dequeで生成する文字列を管理することで文頭文末の操作を高速化(全く気づけなかった)

の3つが必要だったみたいです。dequeは何度か見かけたことはあったのですが、いまいちその恩恵が分からず使う発想に至りませんでした…。これで次回から使える武器が増えたので儲けものです！

まとめ

ウッキウキでZONeの新商品まで買いに行ったのに2問しか解けなくて若干恥ずかしいですね。今回は数学的な考察が出来なかったわけではなく、単純な知識不足だったので精進していけば全然克服できると思うのであまり負の感情は湧いていません。知識を定着するためにもコンテストで得られた知見もブログにまとめていこうかなぁと思っています。

おまけ

コンテスト中、隙あらばエナジードリンクってカフェイン と一緒にアルギニンが入ってるけど、どんな作用機序で覚醒作用につながるんだろうと考えてたんですが、アルギニンによって産生されたNO(一酸化窒素)が１．脳の血管を拡張して血流改善２．神経伝達物質として働くことが原因と考えるのが今のところ妥当っぽいですね。（そんなんでいいのか）ちょっと調べたかぎりでは、カフェインと一緒に加える理由としてはカフェインがアルギニンの分解を抑制することでアルギニンがちゃんと働けるようにするためって感じでした。この論文、2009年のものだけど現在は作用機序がちゃんと解明されているんでしょうか？（そもそもそんな状態で製品化ってできるんですかね？）

アルギニンとカフェインを一緒に加えるとNOの量が増えるよという論文↓

pubmed.ncbi.nlm.nih.gov

アルギニンとカフェインを一緒に加えるとアルギニン分解酵素の活性が落ちるよという論文↓

pubmed.ncbi.nlm.nih.gov

第二回日本最強プログラマー学生選手権の感想

第二回日本最強プログラマー学生選手権に参加しました！結果はA,B問題の2完で見事レートを下げました！勉強代と思えば-25なんて安いものです（泣）以下簡単にコメントしていきます。

A - Competition

初見：A問題だしちゃちゃっと片付けちゃおう

atcoder.jp

与えられるお肉の価格設定より少しだけ安い値段設定をしろという問題。与えられるお肉の価格設定を元に自分が価格設定するパックの価格を計算して、

1. その値が小数だったら切り捨て
2. 整数だったら「その値 - 1」

を出力しました。小数怖いなぁと思いつつ工夫せずに通ってくれました。A問題にしては若干考えることが多い問題でしたが、８分は少し手間取りすぎましたね。

B - Xor of Sequences

初見：Xor!?うっ、頭が・・・!

atcoder.jp

２つの数列が与えられるので、どちらか一方のみに含まれる数字(対称差集合というらしい)を出力する問題。集合の計算はpythonのsetを使えば簡単にできることを知っていたので秒殺できました。

C - Max GCD 2

初見：最大公約数の問題はここ↓でたくさんやったし今回も３完は堅いな！()

AtCoder 版！マスター・オブ・整数 (最大公約数編) - Qiita

atcoder.jp

A以上B以下の数字から選んだ２つの数字の最大公約数のうち最大なものを求める問題。まず初めに考えたのは考えたのはBから１に向かって答えを決め打ちして、その数で割り切れる数が2つ以上いればその値を出力するというもの。しかし、ここの実装でA以上B以下のすべての数に対して割り切れるかのチェックをしてTLE。ここで、答えを決め打つ方針は間違ってると思い、愚直に問題文通りに素直に実装してみた。つまり、2数の組み合わせを全パターン調べて最大公約数を更新していく方法。でもこれってO(N^2)なので今回の制約では間に合うはずがないですね；；

結局決め打ちの方法で工夫する発想には至らず、用事のため１時間強で撤退しました。一回切り捨てた解法に戻れなかったのは頭が固すぎましたね。きちんと計算量に則った解法の選択を心掛けます！

D - Nowhere P

初見：C解けないけどわんちゃんある？

atcoder.jp

問題文もあまり読み込めていませんでした。入力が10^9と大きいこと、同じ倍数、約数系の問題ならCを先に解くべきだと思いC問題に戻りました。

全体の感想

 順位表を見る限り、ABCまでは大半が解かれていたので、せめてここまではおさえておきたかったな～というのが正直な気持ちです。解けない問題は格好の成長材料なのでありがたく復習させていただきます！

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

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

atcoder.jp

ざっくりなイメージ

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

解答への手がかり

 今回注目すべきは、

1. 1つの文字には1桁の数字があてられる
2. 異なる文字には同じ数字をあてることができない

の２つです。

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

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

実装の流れ

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

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

いざ実装(Python)

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

from itertools import permutations

入力をリストで受ける

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

ここでは

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

という操作を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")