ABC225のA-D問題の解説。
目次
A - Distinct Strings
B - Star or Not
C - Calendar Validator
D - Play Train
A - Distinct Strings
解説
長さが3の文字が与えられ、これを並び替えた種類は何通りあるかという問題。
もしaaaならば、並び替えてもすべて同じ文字になるので、1種類。つまり、文字の種類が1種類のときは、1種類となる。
もしaabならば、bの位置は、aabとabaとbaaとなる。したがって、文字の種類が2種類のときは、並び替えた文字列は3種類になる。
もしabcならば、すべてのアルファベットが違うので、全通りを考えなければならない。したがって、abc,acb,bac,bca,cab,cbaの6種類となる。
以上のことを実装する。
まず、同じアルファベットはどうやって判定するか。文字列を一度list()にいれて、それぞれの文字列を分割する。'aba' -> ['a', 'b', 'a']のようになる。
これをset()にいれると、重複したアルファベットはまとめられる。このset()の長さで以上のことをif文で判別し、答えを出力する。
コード
def main():
s = list(input())
if len(set(s)) == 1: # ex) aaa なら並び方は1種類
print(1)
elif len(set(s)) == 2: # ex) aab なら並び方は3種類
print(3)
else: # ex) abc なら並び方は6種類
print(6)
if __name__ == '__main__':
main()
B - Star or Not
解説
1つの頂点から、他のすべての頂点に1本ずつ辺がでている木、になっているかを判別する問題。
入力はa, bで、頂点aから頂点bへ辺が伸びているということを示す。
どうやって判別するかだが、1つの頂点からすべての頂点に辺が出ているということは、頂点aと頂点bの数を数え、ある頂点の数が、n-1個の辺と等しくなっているかどうかを判別してあげると良い。
したがって、これを実装したものが以下のコードである。
コード
def main():
n = int(input())
check = [0] * n
for _ in range(n-1):
a, b = map(int, input().split())
check[a-1] += 1
check[b-1] += 1
if (n-1) in check: # 辺の数がn-1本のものがあればOK
print('Yes')
else:
print('No')
if __name__ == '__main__':
main()
C - Calendar Validator
解説
与えられたBがAの一部であるか判定する問題。
Aは次のような形になっている。
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
...
Bがこの形になっているのをどうやって判断すれば良いか。
Aの規則性を見てみると、行は1ずつ増え、列は7ずつ増えていることがわかる。これを用いて判定する。
行と列を判定するため、それぞれに配列を作る。
行に関して、判定したい値をαとしたときに、その行数は${α-1}/7$の小数点以下切り上げの値になる。また、列に関しては、列数は${β-1}$を7で割ったあまりに1を足した値となる。
この2つに関して、以下のコードのように、規則性が崩れた場合は、Noを出力してあげると良い。
コード
def main():
n, m = map(int, input().split())
B = []
for i in range(n):
B_row = list(map(int, input().split()))
B.append(B_row)
x = [[] for _ in range(n)]
y = [[] for _ in range(n)]
for i in range(n):
for j in range(m):
x[i].append((B[i][j]+6)//7) # 6足して値を切り上げ
y[i].append((B[i][j]-1)%7+1) # 連番になっているか
ans = 'Yes'
for i in range(n):
for j in range(m):
# どれか一つでも引っかかったらアウト
if 0 < i and x[i][j] != x[i-1][j]+1: # xの列で1の差を見る
ans = 'No'
break
elif 0 < j and y[i][j] != y[i][j-1]+1: # yの行で1の差を見る
ans = 'No'
break
elif 0 < j and x[i][j] != x[i][j-1]: # xの行が等しいか見る
ans = 'No'
break
elif 0 < i and y[i][j] != y[i-1][j]: # yの列が等しいか見る
ans = 'No'
break
print(ans)
if __name__ == '__main__':
main()
D - Play Train
解説
番号のついた電車がN個あり、入力された各クエリに対して操作をする問題。
・1 x y：電車xの後部と電車yの前部を連結
・2 x y：電車xの後部と電車yの前部を分離
・3 x：電車xが含まれる電車のすべての番号を先頭から出力する
電車の前部と後部については、それぞれリストを用いて管理し、連結していない部分に関しては$-1$を代入しておく。
まず、query1の場合、backとfrontのそれぞれのインデックス番号の場所に、入力された電車の番号を代入する。
次に、query2の場合、先程車両番号をいれたが、今回は分離したいので、backとfrontどちらにも$-1$を代入する。
最後に、query3の場合、その入力された車両番号をもつ連結された電車を先頭から出力する。車両番号をある変数に入れ、frontのなかからその電車番号のインデックスに当たる数字を探し、これをさらに変数に代入する。これを、変数が-1、つまり、非連結部分まで繰り返すことで、先頭車両を探し出すことができる。
先頭車両がわかったので、先程行ったことを最後尾の車両（-1：非連結部分）まで行う。こうすることで、入力された車両番号をもつ連結された電車の先頭から値を出力できる。
コード
def main():
n, q = map(int, input().split())
front = [-1] * (n+1) # 非連結部分は-1
back = [-1] * (n+1)
for _ in range(q):
query, *xy = map(int, input().split())
if query == 1:
x, y = xy
back[x] = y # back_iは後列車を表す
front[y] = x # front_iは前列車を表す
elif query == 2:
x, y = xy
back[x] = -1 # 非連結部分は-1なので、それぞれに値を代入
front[y] = -1
elif query == 3:
x = xy[0]
while front[x] != -1: # 前列車がなくなる（先頭車両）まで探す
x = front[x] # 前列車の番号をxに代入
ret = [x] # 先頭車両の番号
while back[x] != -1: # 後列車がなくなるまで探す
x = back[x]
ret.append(x)
print(len(ret), *ret)
if __name__ == '__main__':
main()
編集後記
queryの問題をたくさん解いて練習したい...。まとめようかな。