ABC232のA-D問題の解説。
目次
A - QQ solver
B - Caesar Cipher
C - Graph Isomorphism
D - Weak Takahashi
A - QQ solver
解説
文字列Sは、axbという形になっており、これの$a \times b$を求める問題。
aとbを文字列からインデックスを指定して、整数型int()にしてから、かけ合わせればAC。
コード
s = input()
a = int(s[0])
b = int(s[2])
print(a*b)
B - Caesar Cipher
解説
文字列Sをアルファベット順に1文字ずつ動かしたとき、SはTに一致するかを求める問題。
pythonでは、アルファベットはord()を用いると数値化できる。ord('a')は97、ord('z')は122である。
今回の問題は、SとT、それぞれの文字の距離がすべて等しいかを求めれば良い。
入力例1でいうと、aとiの距離は、$9 - 1 = 8$、b,jとc,kも等しく$8$である。したがって、すべての距離が等しいのでYesを出力する。
では、文字が折り返すz, aのときはどうだろう。$97 - 122 = -25$でこれでは距離が正しくない。このようなときに対して、$26$を足して、$26$で割ったあまりを出してあげれば、正しい距離である$1$が出力される。
あとは、すべての文字に対して行えばいいので、set()を利用して重複をなくし、set()の要素が1つであれば、Yesを出力してあげればよい。
コード
s = list(input())
t = list(input())
st = set()
for i in range(len(s)):
k = (ord(t[i])-ord(s[i])+26)%26
st.add(k)
if len(st) == 1:
print('Yes')
else:
print('No')
C - Graph Isomorphism
解説
AとB、CとDのボールを、それぞれひもで結ぶおもちゃが2つある。おもちゃのボールに書かれている数を入れ替えてもよいとき、それぞれのおもちゃの形は等しいかどうかを求める問題。
おもちゃの形が等しいかどうかは、各ボール同士をつなぐひもが、各おもちゃで等しければよい。
したがって、ボールの番号を振りかえる、N!（N*N-1*...*1）とおり試せば良い。
これを管理するには、隣接リストを用いる。
ひもで繋がれている各ボールをリストのインデックス番号に追加する。その後、N!通りに対して、全ボールの組み合わせを考える。隣接リストの各要素は、0か1に限定されるので、すべてのひもの組み合わせが2つのおもちゃにおいて等しければ、flagは立ったままなので、Yesを出力してあげれば良い。
コード
from itertools import permutations
n, m = map(int, input().split())
ga = [[0]*n for _ in range(n)]
gb = [[0]*n for _ in range(n)]
for _ in range(m):
u, v = map(int, input().split())
u -= 1
v -= 1
ga[u][v] = ga[v][u] = 1
for _ in range(m):
u, v = map(int, input().split())
u -= 1
v -= 1
gb[u][v] = gb[v][u] = 1
ans = False
for p in permutations(range(n)):
flag = True
for i in range(n):
for j in range(n):
if ga[i][j] != gb[p[i]][p[j]]:
flag = False
if flag:
ans = True
break
if ans:
print('Yes')
else:
print('No')
D - Weak Takahashi
解説
H$\times$Wのグリッドがあり、マス$(i, j)$にいるとき、マス$(i+1, j)$かマス$(i, j+1)$に動くことができるとする。マス$(1, 1)$にいるとき、最大で移動できるマスの数を答える問題。
結論から言うと、DPを利用して問題を解く。
DPについて詳しく知りたい方は、アルゴ式を参考にしていただきたい。
DPとは、「問題全体を部分問題に分解し、各部分問題に対する解をメモしながら、小さな部分問題からより大きな部分問題へと順に解を求めていく手法」である。主に、この問題では、メモを右下から行っていく。
今回の問題では、右か下にしか進むことができないので、メモの仕方としては、max(dp[i][j], dp[i+1][j]+1)、max(dp[i][j], dp[i][j+1]+1)となる。
これを右下から左上にかけて、各行各列に対して行っていくことで、すべてのマスに対して最大の移動距離を求めることができる。
このとき、マス$(1, 1)$からの最大移動距離なので、dp[0][0]を出力させれば、ACである。
コード
h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]
dp = [[0]*w for _ in range(h)]
for i in range(h-1, -1, -1):
for j in range(w-1, -1, -1):
if s[i][j] == '#':
continue
dp[i][j] = 1
if i+1 < h:
dp[i][j] = max(dp[i][j], dp[i+1][j]+1)
if j+1 < w:
dp[i][j] = max(dp[i][j], dp[i][j+1]+1)
print(dp[0][0])
編集後記
授業でやったDPが理解できるようになったのが嬉しい。
DPまとめとかやろうかな。