・6 min read
ABC232 解説 (A問題～C問題)
こんにちは, こんばんは. Ruteです.
当記事は, ABC232の解説記事となっております. A問題～C問題までの解説を行います.
動画による解説は私のYouTubeチャンネルの動画よりご確認下さい.
| 問題 | 問題名 | Difficulty |
|---|---|---|
| A | QQ solver | 9 |
| B | Caesar Cipher | 82 |
| C | Graph Isomorphism | 685 |
この問題は,
axbの形式によって成り立っている文字列が与えられるので,の値を出力する, という問題でした.主に2つの解法がありますので, 順番に説明します.
解法1 S.split("x")を使う解法
python のメソッド
文字列A.split("文字列B")では, 文字列Aの文字列に対し, 文字列Bで区切った場合の分割を, リストにして取得することが可能です.例:
"3.14".split(".") = ['3', '14']今回の問題ではまさにこの関数を利用することが出来ます.
S.input("x")を用いることにより, Sをxで区切った文字列のリストを取得出来ます.あとは, この1番目の要素と2番目の要素の積を出力すれば良いのですが, リストでは各要素が文字列型となっているため, 整数型に直す必要があることに気をつけて下さい.
#文字列Sを受け取る.
S = input()
#文字列Sを'x'で区切った文字列のリストにする.
S = S.split("x")
#1文字目と2文字目の積を計算して出力. int型にすることを忘れないこと.
print(int(S[0]) * int(S[1]))解法2 S.split("x")を使わない解法
実は, の長さは必ずであることから, 単純に文字列を受け取り1文字目と3文字目の積を計算して出力することでも同じ処理が可能です.
#文字列Sを受け取る.
S = input()
#答えを出力する. int型にすることを忘れないこと.
print(int(S[0]) * int(S[2])この問題は, 文字列処理の基本的な問題で, 最近のABCでは易しめであると感じました.
splitというメソッドは, 文字列を分解するときに利用するので, 覚えておきましょう.解説
問題名の英訳「シーザー暗号」は有名な暗号形式の一種です.
さて, この問題の目的は
の各文字を非負整数回操作してに出来るかを判定できるようにする というものになります.
例えば, 英小文字が
"a"から数えて何番目かは文字コードにより簡単に分かります.文字コードとは
文字コードは, コンピュータ上で任意の文字列と対応させるための数値です.
一般的には, 英小文字の文字コードはこのようになっています.
| a | b | c | d | e | ... | z |
|---|---|---|---|---|---|---|
| 97 | 98 | 99 | 100 | 101 | ... | 122 |
これにより,各文字が"a"から数えて何番目かは,
その文字の文字コード - 97 という計算によって求める事が可能です.
本題に戻りますが, この問題では, を構成する全ての文字に対して, 操作を行うことによってに出来るかの判定を行います.
よってこれは以下のことを判定することと同じになります.
判定すること
- の場合 :
- の場合 :
以下に, 正解のソースコードの例を示します. 計算量はです.
S = list(input())
T = list(input())
#A[i] = i文字目における Xの値
A = [0 for i in range(len(S))]
for i in range(len(S)):
if ord(S[i]) <= ord(T[i]):
X = ord(T[i])-ord(S[i])
else:
X = 26 - (ord(S[i])-ord(T[i]))
A[i] = X
#この場合, すべてのAの値が同じであればYesとなる.集合で管理した。
if len(set(A)) == 1:
print("Yes")
else:
print("No")解説
この問題は, かなり読解力によって差がついた問題だと思っています.
まず, 条件を整理すると, 以下の様になります.
- は を並び替えて得られる
- 任意の以上以下の整数,,について次の条件が成り立つ.
- 各順列に対して
- 1 ~ N それぞれに対して (これを とする)
- 高橋君のおもちゃにおいて, ボールと繋がっているボールの番号全てに対して (これをとする)
- 青木君のおもちゃでボールがボールと繋がっているかを判断する
- 各について, 全ての条件が満たされていれば, この順列は問題文の条件をクリアする.
計算量は, 高橋君のおもちゃにおいて,個全てのボールに対して,個のボールが繋がっていた場合があてはまり, 程度になるといえます.今回の制約では, 十分に高速です.
以下に, 正解のソースコードの例を示します.
from itertools import permutations
N,M = map(int,input().split())
g_t = [[] for i in range(N)]
g_a = [[] for i in range(N)]
for i in range(M):
a,b = map(int,input().split())
a -= 1
b -= 1
g_t[a].append(b)
g_t[b].append(a)
for i in range(M):
a,b = map(int,input().split())
a -= 1
b -= 1
g_a[a].append(b)
g_a[b].append(a)
L = permutations([i for i in range(N)],N)
ft = 0
for _ in L:
ao = list(_)
#ao[i] = aoにおけるi番目のボール
f = 0
for i in range(N):
for m in range(len(g_t[i])):
j = g_t[i][m]
if ao[j] in g_a[ao[i]]:
continue
#i -> j と P[i] -> P[j] は同値
else:
f += 1
break
if f == 0:
ft += 1
if ft >= 1:
print("Yes")
else:
print("No")
