ABC226のA-D問題の解説。
目次
A - Round decimals
B - Counting Arrays
C - Martial artist
D - Telepotation
A - Round decimals
解説
与えられた実数Xを、小数点第一位で四捨五入して出力する問題。
pythonであれば、roundなど使ってもよいが、今回は条件分岐で説明する。
ある実数Xは小数点第三位までしかないので、整数部分はスライスして保存しておく。
条件分岐だがx[-3]などとして、小数点第一位の値を参照し、その値が5以上であるかどうかを判定する。
もし5以上であれば、保存しておいた整数部分に1を足して出力、5未満であれば、そのまま保存しておいた整数部分を出力してあげるとよい。
コード
def main():
x = input()
before_point = int(x[:-4])
if int(x[-3]) >= 5:
print(before_point+1)
else:
print(before_point)
if __name__ == '__main__':
main()
B - Counting Arrays
解説
入力された数列が何種類あるか求める問題。
重複する要素の判定は、set()をもちいることで、実装できる。
入力された数列のインデックス番号1以上の配列をスライスして、タプルに置き換える。これをset()にいれて、長さを出力したものが答えとなる。
コード
def main():
n = int(input())
kind_of_arrays = set()
for _ in range(n):
len_and_arrays = list(map(int, input().split()))
arrays = tuple(len_and_arrays[1:])
kind_of_arrays.add(arrays)
print(len(kind_of_arrays))
if __name__ == '__main__':
main()
C - Martial artist
解説
技$i$を習得するためには、時間$T_i$が必要で、技$A_{i, 1}, A_{i, 2}, ..., A_{i, K_i}$を習得している必要がある。このとき技$N$を取得するために、必要な最小時間を答える問題。
最初の文章だが、例えば入力例1を用いると、技$3$を取るためには、時間$7$が必要で、技$1$を習得している必要がある。
最小の時間をどうやって出すのか。結論、技$N$から逆算して答えれば良い。
入力例2で考えると、技$5$を習得するためには、技$1, 2, 3, 4$の習得が必要である。技$5$を習得する時間は、$1000000000$なので、事前に変数を用意して、値を足しておく。残りは技$1, 2, 3, 4$の習得が必要なので、このなかから値を一つ取り出し、技$5$でやったことと同じことを繰り返す。
こうして、習得する必要のある技がなくなるまで繰り返すことで、それまでにかかった合計時間がわかるので、これを出力すればよい。
コード
def main():
n = int(input())
techs = []
for _ in range(n):
tech = list(map(int, input().split()))
techs.append(tech)
nxt = techs[-1][2:] # 次に調べる技
time = techs[-1][0] # 必要な合計時間
get_tech = set() # 習得した技
while nxt: # 習得する必要がある技がなくなるまで
now_tech = nxt.pop() - 1
if now_tech not in get_tech: # まだ習得していない技であれば
get_tech.add(now_tech) # 技を習得済みに
time += techs[now_tech][0] # 習得する時間を足す
nxt.extend(techs[now_tech][2:]) # 習得する必要のある技を配列として追加
print(time) # 必要な合計時間を出力
if __name__ == '__main__':
main()
D - Teleportation
解説
街$i$から街$j$に移動するとき、街$i$の位置に、(a, b)をそれぞれ足してあげることで移動できる。また、他の街同士で移動するとき(a, b)を複数回足して移動しても良い。ただし、移動する際の(a, b)は1種類のみしか使ってはならない。このとき、すべての街同士を移動できる(a,b)の数を数えるという問題。
例では、街1から街2まで(a,b)=(1,2)で移動できる。
考えたいのが、2枚目の例である。このように街3から街4、街4から街5は、(a,b)=(1,1)で移動できる。街3から街5は、(a,b)=(2,2)で移動できるが、これは(a,b)=(1,1)を2回もちいても移動できる。つまり、a, bの最大公約数で互いを割ることで、最小の移動手段を求めることができる。
したがって、この3つは1種類の移動にまとめることができる。
これをすべての街に対して行い、すべての移動手段を出力すればAC。
コード
def main():
from itertools import permutations
import math
n = int(input())
towns = [] # 街の位置
town_nums = [i for i in range(n)] # 街の全番号
for _ in range(n):
x_y = list(map(int, input().split()))
towns.append(x_y)
result = set() # 結果集計用
for uv in permutations(town_nums, 2): # すべての街に対して、2つ選んで順序付きで並び替えてタプルを作成
u = towns[uv[0]]
v = towns[uv[1]]
x_dist, y_dist = v[0]-u[0], v[1]-u[1] # x軸とy軸で2つの街の距離の差を取る
xy_gcd = math.gcd(x_dist, y_dist) # それぞれの距離の差の最大公約数を取る
result.add((x_dist//xy_gcd, y_dist//xy_gcd)) # 最小移動単位で集計
print(len(result))
if __name__ == '__main__':
main()
編集後記
A問題でWAした衝撃のABC。