A問題の分析
UNICORNプログラミングコンテスト2021、AtCoder Beginner Contest 225
A問題、ディスティンクトストリングス。
問題文、A小文字のみからなる長さ3の文字列Sが与えられます。
Sの各文字を並び替えて得られる文字列は何種類ありますか?
入力例1、ABA。SイコールABAの各文字を並び替えて得られる文字列は、AAB、ABA、BAAの3通りです。
入力例2、CCC。出力例は1、1通りのみです。
入力例3、XYZ。出力例3、6。XYZの各文字を並び替えて得られる文字列は、XYZ、XZY、YXZ、YZX、ZXY、ZYXの6通りです。
パイソンだったら、確かライブラリーでデフォルトの、何て言ったっけ、順繰りでかぶりなしの与えられた文字列の組み合わせを試すみたいな方文があったと思うんですけど、コレクションかな?
ただこの場合、入力例の中で2つ同じ文字の場合、全部同じ文字の場合、全部違う文字の場合っていう全パターンが提示されているので、もうそれをやるだけですね。
なので、Sイコールセットのリストのインプット.スプリットで、if Sをもう連にしとこうか。連のセットのリストのインプット.スプリット。
いや待って、インプット.スプリットだとスプリットされないね。ちょっとコードテストしましょうか、さすがに。
Sイコール連のセットのリストのインプットで、例えば入力例がABAだった場合、プリントSは2になってますか?2になってないですね。
エラー。なんか1個多い、1個少ない。どっちだ。1、2、1個少ないですね。括弧が1個少なかったです。2が出たのでOKですね。
if Sイコールイコール1だったらプリント1、if Sイコールイコール2だったらプリント2だったら3、最後elseプリント6でOKですね。
B問題の解決
提出。ACしたのでB問題いきます。B問題。star or not 問題文。n頂点n-1辺の木が与えられます。
頂点には1からnの番号がついており、iPhone目の辺は頂点Aiと頂点Biを結んでいます。この木がスターであるか判定してください。
ただし、スターとは1つの頂点から他の全ての頂点に1本ずつ辺が出ている木のことです。
与えられたグラフがスターであるならyes、スターでないならnoと出力しよう。
入力例1。5本あって、1から4。
1と4、2と4、3と4、4と5はyes。
スター。1つの頂点から他の全ての頂点に1本ずつ辺が出ている木のことです。
だから、
1個目と2個目の中でダブってる方が永遠と続いていたらOKってことですね。
ちょっとよく理屈はわかんないけど、それが何でスターというのかは。
では、nイコールイントのインプット。
で、forインエンジン回とどうしましょうかね。
n-1にしといて、あらかじめAとBを
インプット.スプリットでいいか。
別に数字で見てるわけじゃないので。
インプット.スプリットで大文字のAとBをインプット.スプリットして
与えられるやつは全部違うやつっていう認識でいいのかな。
同じ辺は与えられることはないですかね。
で、あるならば
じゃあn-2ですね。
あらかじめ2個分はfor分の外で2個もらっておいて
小文字ABと大文字ABをもらっておいて
if小文字Aと大文字Aが一緒ならTMPはAです。
elif小文字Bが大文字Bと一緒ならTMPはBです。
elif...なんか久しぶりに泥臭いコードを書いてる気がする。
小文字Aイコール大文字BだったらTMPはAです。
elif小文字Bが...っていうかそうか。
orで書いたらよかったですね。
ifA==Aor小文字A==BだったらTMPはA。
elif小文字B==大文字Bor小文字B==大文字A。
はい、で、
for in range n-2で
if TMP==Aor...
あ、違うな。
bigly equal Aor bigly equal B
だからTMPっていうのが共通項であるはず、頂点であるはずなので
それが入力してきたものと同じじゃない場合はもうexitですね。
printのこれ
そうですね、3以上与えられるので絶対for分は1回は起動するので
特にいじる必要はなさそうです。
で、最後print
何事もなく通り抜けたならイエスって感じでどうですか。
noが出たね。
1個目noが出たね。
ん?
あ、orにしてるからだ。
ifどっちもTMPじゃないようの場合ですね。
hand
エラーが出たね。
input for
input.splitがダメ。
なんで?
何行目?
8行目。
だからfor分に入ったところですね。
んー?
leading align。
なんでや。
input.split
n-2
だから3回
n-3だ。1個少ないんだ。
n-1ペンのキーが与えられますか。なるほどなるほど。
頂点の数なんですね、nは。
はい、イエスが出ました。
入力例2はno。
no。
入力例3はyes。
はい、イエスが出ました。クリアしたので提出していきます。
あ、reが出た。
reは?
実行時エラーだっけ?
えーっと
15問中
違う
13問中2問実行時エラー
ですね。
えーどこが間違ってるんだ。
Cって言うなら
えーっと
n-3にしちゃってることかな。
変が
n頂点n-1ペンのキーが与えられます。
頂点には1,2からnの番号がついており
頂点Aiと頂点Biを結んでいます。
シンプルにリストに入れちゃいますか?
っていうパターンもちょっと試してみようかな、せっかくだから。
でどの道ちょっとB問題アウトだったので今回はここまでにしておこうと思いますが
せっかくなのでリベンジオーバー。
Aイコール
実行時エラーと最終確認
空のリスト
Bイコール空のリストにしといて
えー
あ違うえーっと
二重リストですね。空のリストの中に
n個空のリストを入れといて
かけるn
でフォーアインレンジn-1
えー小文字のABイコール
マップイントインプット
ロットスプリットして
大文字AラージAのABを一旦マイナス1しといて
いっか
いっか別にマイナス1しなくて
ラージAのA番目
ロットアペンド
B?
ラージABじゃなくても
Lでいいのか1個のリストでいいのか
ちょっとわかんなくなってきたな
LのA番目にBを入れてLの
B番目に
Aを入れる
で一回プリントLして確認してみると
どうなってますか
エラーですね
リストインデックスアウトオブレンジ
じゃあ
空のリストの数を増やしましょう
N×10とかにしといて
N×100とかにしといて
あれ?
リストインデックスアウトオブレンジ
この空のリストの作り方が間違ってるのか
ん?リスト空のリストの作り方ってこれで合ってるんじゃないの?
やれやれですね久しぶりにやるからちょっと
なまっているのかもしれない
空のリスト1個だけしか出ないですね
なんでや
空のリスト増やすのってどうやるんだったっけ
4分?
なんちゃらインレンジ
N×100
あー増えた増えた
ではコメントアウトしたものを戻していって
1,2,3,4,5,6,7,8,9
一番多いものがN-1だったらオッケーってことかな
えーっと
L
LEN L
MAX Lで取ったらどうなる?
10が出てくるだけか
サイズが一番大きいのってどうやって取るんだこれ
んーっと
サイズが一番大きいの?
いいか
フォワインレンジ
いやフォワインL
4分の前にTMP
エコール0
TMPエコールMAX
TMPか
LEN
マイ
プリント
ES
IF
TMPエコールエコールN-1
ELSE
NO
ESが出ましたね
えーっと
一番はイエス
で二番がノー
はい
提出してみましょうか
グラフとかキーって言われたらもうリストを
ノーしで作った方がいいんだろうな多分
はいACしましたので一応解説を見て今回終わりにしようと思います
グラフ理論の用語が急に出てきて戸惑った方もいたかと思うのですが
B問題でなかなかグラフの話が出ないと思うんですが
このレベルの単語はABCの中盤以降には中期なしで出てくると思うので
良ければこの機会に覚えてみてください
全ての頂点の次数
頂点から出ている辺の数を数えます
次数がN-1の頂点があるなら答えはイエスないならノー
C++なのでちょっと軽く見ますが
ベクター
カウントN-1
法文
リスト
カウント
辞書かな
辞書を作ってるっぽいですね
辞書を作って入力した与えられた辺を
全部プライチしていって
その中にN-1と合致するカウント数のものがあればイエス
なければノーという感じですかね
辞書ありですね
では今日はここまでにしておきましょう
また次回お疲れ様です
