Magicode logo
Magicode
0
・6 min read

ABC232 解説 (A問題～C問題)

pythonABC競技プログラミング

こんにちは, こんばんは. Ruteです.

当記事は, ABC232の解説記事となっております. A問題～C問題までの解説を行います. 動画による解説は私のYouTubeチャンネルの動画よりご確認下さい.

問題問題名Difficulty
AQQ solver9
BCaesar Cipher82
CGraph Isomorphism685

この問題は, axbの形式によって成り立っている文字列SSが与えられるので,a×ba×bの値を出力する, という問題でした.

主に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")を使わない解法

実は, SSの長さは必ず33であることから, 単純に文字列を受け取り1文字目と3文字目の積を計算して出力することでも同じ処理が可能です.

#文字列Sを受け取る.
S = input()
#答えを出力する. int型にすることを忘れないこと.
print(int(S[0]) * int(S[2])

この問題は, 文字列処理の基本的な問題で, 最近のABCでは易しめであると感じました. splitというメソッドは, 文字列を分解するときに利用するので, 覚えておきましょう.

解説

問題名の英訳「シーザー暗号」は有名な暗号形式の一種です.

さて, この問題の目的は SSの各文字を非負整数回操作してTTに出来るかを判定できるようにする というものになります.

例えば, 英小文字が"a"から数えて何番目かは文字コードにより簡単に分かります.

文字コードとは

文字コードは, コンピュータ上で任意の文字列と対応させるための数値です.

一般的には, 英小文字の文字コードはこのようになっています.

abcde...z
979899100101...122

これにより,各文字が"a"から数えて何番目かは, その文字の文字コード - 97 という計算によって求める事が可能です.

本題に戻りますが, この問題では, SSを構成する全ての文字に対して, 操作を行うことによってTTに出来るかの判定を行います.

よってこれは以下のことを判定することと同じになります.

判定すること

  • ord(Si)≤ord(Ti)ord(S_i) \leq ord(T_i) の場合 : ord(Ti)−ord(Si)ord(T_i) - ord(S_i)
  • ord(Si)>ord(Ti)ord(S_i) > ord(T_i) の場合 : 26−{ord(Si)−ord(Ti)}26 - \lbrace ord(S_i) - ord(T_i) \rbrace

以下に, 正解のソースコードの例を示します. 計算量はO(∣S∣)O(|S|)です.

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")

解説

この問題は, かなり読解力によって差がついた問題だと思っています. まず, 条件を整理すると, 以下の様になります.

  • PP は (1,…,N)(1 , \dots , N) を並び替えて得られる
  • 任意の11以上NN以下の整数ii,jj,について次の条件が成り立つ.
  • 各順列PPに対して
  • 1 ~ N それぞれに対して (これを iiとする)
  • 高橋君のおもちゃにおいて, ボールiiと繋がっているボールの番号全てに対して (これをjjとする)
  • 青木君のおもちゃでボールPjP_jがボールPiP_iと繋がっているかを判断する
  • 各iiについて, 全ての条件が満たされていれば, この順列PPは問題文の条件をクリアする.

計算量は, 高橋君のおもちゃにおいて,NN個全てのボールに対して,N−1N-1個のボールが繋がっていた場合があてはまり, O(N!∗N2)O({N!} * N^{2})程度になるといえます.今回の制約では, 十分に高速です.

以下に, 正解のソースコードの例を示します.

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")

Discussion

コメントにはログインが必要です。