M-SOLUTIONSさん主催のABC232の参加記録です。
レート600台です。使用言語はPython3です。この記事には、私がABC232のA問題からC問題までを自分が理解した内容で書いていきます。
今回のB問題、C問題は特に難しく感じました。
A – QQ solver
標準入出力と型、四則演算が利用できるかを問われる問題。
私は、一度、文字列(str)型として受け取ってから、1番目の文字と3番目の文字を int() に変換して、二つの数を掛け算して提出しました。
# M-SOLUTIONS プロコンオープン2021(AtCoder Beginner Contest 232)
# A - QQ solver
S = input()
ans = int(S[0]) * int(S[2])
print(ans)公式の解説にもある通り、map() を利用すれば、非常に簡単に書くことができますね。
a,b=map(int,input().split("x"))
print(a*b)初めのうちは、map() 自体をうまく使うこと、入力は1変数のように見えるのに、敢えて2変数として受け取るのは、上級者向けのように感じてしまいますが、この辺りをうまく扱えるようにしたいですね。
B – Caesar Cipher
繰り返し処理と、周期性のあるデータの取り扱いができますか。が問われる問題。
私は、KをSとTの1文字目の差分として、Sの各文字がKずれた文字とTが一致するかを確認しました。
Kを設定するときに、26文字周期であることから、26で割った余りを忘れないようにしましょう。
途中で、一文字でも異なる場合は、”No”を出力して、プログラムを終了させる。すべての文字を処理して”No”が出力されていない場合は、”Yes”を出力すればOKですね。
# M-SOLUTIONS プロコンオープン2021(AtCoder Beginner Contest 232)
# B - Caesar Cipher
S = input()
T = input()
alphabet=["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
K = (alphabet.index(T[0]) - alphabet.index(S[0])) % len(alphabet)
# print(K)
for i in range (len(S)):
indx = alphabet.index(S[i])
indx += K
indx %= len(alphabet)
if alphabet[indx]==T[i]:
continue
else:
print("No")
exit()
print("Yes")C – Graph Isomorphism
順列の全探索が出来ますか。グラフの取り扱いは出来ますか。が問われる問題。
私には非常に難しかったです。
以下、この問題を解く方針をメモしていきます。
基本的にやることは問題文に全て書かれていますね。(それを理解して実装するのが難しかったのですが。)
- 入力で与えられるおもちゃをグラフとして受け取る
- Nまでの順列を全列挙する。
- 作成した順列 P において、2つの数字 ( i , j ) において、以下を確認する。
- 高橋君のおもちゃ i と j がつながっていれば、青木君のおもちゃは Pi と Pj がつながっていること。
- 高橋君のおもちゃ i と j がつながっていない場合は、青木君のおもちゃ Pi と Pj はつながっていないこと。
- 全ての i , j の組で上記条件に当てはまる順列が存在したら、”Yes” を出力してプログラムを終了させる。
- 全ての順列を試したが、”Yes” と出力されなかった場合は、”No” を出力する。
# M-SOLUTIONS プロコンオープン2021(AtCoder Beginner Contest 232)
# C - Graph Isomorphism
import itertools
N, M = map(int, input().split())
# おもちゃグラフ作成
Takahashi = [ set() for i in range(N) ]
Aoki = [ set() for i in range(N) ]
for _ in range (M):
A, B = map(int,input().split())
A -= 1 # 0-index
B -= 1 # 0-index
Takahashi[A].add(B)
Takahashi[B].add(A)
for _ in range(M):
C, D = map(int,input().split())
C -= 1 # 0-index
D -= 1 # 0-index
Aoki[C].add(D)
Aoki[D].add(C)
# 順列作成
P = list(itertools.permutations(range(N)))
# 順列全探索
for elem_p in P:
is_same = True # 同じ形かどうかを判定 異なる場合があればFalseにする
# 組み合わせ作成
C = list(itertools.combinations(elem_p,2))
# i, j 全探索
for i, j in C:
aoki_indx_i = elem_p.index(i) # 青木君のおもちゃは数列のindexで判定する
aoki_indx_j = elem_p.index(j)
is_takahashi_connected = i in Takahashi[j] # True or False
is_aoki_connected = aoki_indx_i in Aoki[aoki_indx_j] # True or False
if is_takahashi_connected == is_aoki_connected : # True == True or False == False
continue
else:
is_same = False
# 同じ形の場合の順列が存在したら"Yes"を出力し終了
if is_same :
print("Yes")
exit()
print("No")
コメント