hirohirohirohirosのブログ

地方国立大学に通う情報系学部4年

Atcoder ABC225,224,223 振り返り

競技プログラミング
A - Distinct Strings【AC】

　S=3と決まっているのでそれぞれで場合分けすれば良いです．S=Nと固定されていなくても，同じ文字の個数がx個y個z個...あったら， \frac{N!}{x!y!z!...}で求められます．

a = set(input())
if len(a) == 1:
    print(1)
elif len(a) == 2:
    print(3)
else:
    print(6)
B - Star or Not【AC】

　隣接リストを作り，自分以外の全てのノードが隣接していたらスター型になります．

N = int(input())
tree = [[] for _ in range(N)]

for _ in range(N-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    tree[a].append(b)
    tree[b].append(a)
    
for t in tree:
    if len(t) == N-1:
        print("Yes")
        break
else:
    print("No")
C - Calendar Validator【AC】

　一番左上の数字を取得し，正しいカレンダーを作成します．それを受け取った値と比較します．[7,8,9],[14, 15, 16]のようなパターンも入力としてあり得ることに気がつくのに時間が掛かりWAを連発してしまいました……

N, M = map(int, input().split())
a = []
ok = True
for _ in range(N):
    a.append([int(i) for i in input().split()])

i = a[0][0] // 7
j = a[0][0] % 7

if j == 0:
    i -= 1
    j = 7

if j + M > 8:
    ok = False

aa = []
for i in range(i, i+N):
    aa.append([i*7 + k for k in range(j, j+M)])
    
if ok and aa == a:
    print("Yes")
else:
    print("No")
D - Play Train【AC】

　(なんでこれがdiff778もあるんだろう……)それぞれの車両について前，後ろに連結してる車両をリストで記録します(初期化は自分の車両番号にします)．クエリごとにリストを更新し，表示するクエリが来たら，まず前川の車両の情報を使って先頭車両に移動し，後ろの車両の情報を使って順に表示していきます．初期化は自身の車両番号としているので，自身の車両番号に一致したら，それが両端だということになります．

N, Q = map(int, input().split())
train = [[i, i] for i in range(N+1)]

for _ in range(Q):
    q = [int(i) for i in input().split()]
    if q[0] == 1:
        train[q[1]][1] = q[2]
        train[q[2]][0] = q[1]
    elif q[0] == 2:
        train[q[1]][1] = q[1]
        train[q[2]][0] = q[2]
    else:
        x = q[1]
        while train[x][0] != x:
            x = train[x][0]
        
        ans = []
        while train[x][1] != x:
            ans.append(x)
            x = train[x][1]
        ans.append(x)
        print(len(ans), " ".join(map(str, ans)))
A - Tires【AC】

　文字列を末尾から取得するにはマイナスを付けます．先頭が0はじまりなのに対し，末尾は-1はじまりなのに注意します．

a = input()
if a[-2:] == "er":
    print("er")
else:
    print("ist")
B - Mongeness【AC】

　H, W＜＝50であることから，全探索でも間に合うことが予想つきます．

H, W = map(int, input().split())
A = []
for _ in range(H):
    A.append([int(i) for i in input().split()])

ok = True
for i1 in range(H):
    for i2 in range(i1, H):
        for j1 in range(W):
            for j2 in range(j1, W):
                if A[i1][j1] + A[i2][j2] > A[i2][j1] + A[i1][j2]:
                    ok = False
if ok:
    print("Yes")
else:
    print("No")
C - Triangle?【AC】

　3頂点を選んでそれぞれを直線で結んだとき，3辺のどれか二つでも傾きが一致していたら三角形にはなり得ません．逆にそれ以外の時は三角形になります．if a != b!= c!: としたとき，a=bやb=cの時はFalseとなりますが，a=cの時はTrueになってしまうことに注意します．

N = int(input())
point = []
for _ in range(N):
    point.append([int(i) for i in input().split()])

ans = 0
for a in range(N-2):
    for b in range(a+1, N-1):
        for c in range(b+1, N):
            if point[a][0] == point[b][0] == point[c][0]:
                pass
            elif point[a][0] != point[b][0] != point[c][0] and point[a][0] != point[c][0]:
                line1 = abs(point[a][1] - point[b][1])/abs(point[a][0] - point[b][0])
                line2 = abs(point[a][1] - point[c][1])/abs(point[a][0] - point[c][0]) 
                line3 = abs(point[b][1] - point[c][1])/abs(point[b][0] - point[c][0])
                if not line1 == line2 == line3:
                    ans += 1
            else:
                ans += 1
print(ans)
A - Exact Price【AC】

　100円硬貨が1枚以上入っていることから0円はあり得ないことに注意します．

x = int(input())
if x != 0  and x % 100 == 0:
    print("Yes")
else:
    print("No")
B - String Shifting【AC】

　右シフトを何回かすれば，左シフトを何回かした時と同じ文字になるので，左シフトをする場合のみを考えれば良いです．制約は1000以下なので，恐らくキューを使わなくても間に合うと思いますが，popleftするのでキューを使いました．

from collections import deque
a = deque((input()))
a_list = ["".join(a)]
for _ in range(len(a)-1):
    a_pop = deque.popleft(a)
    a.append(a_pop)
    a_list.append("".join(a))

a_list.sort()
print(a_list[0])
print(a_list[-1])
C - Doukasen【AC】

　(なんでこれはdiff354しかないんだろう……)各導火線で進む早さが異なっても，最終的に末端に到達するのは，左右どちらから火を付けても時間は同じになります．よって一本の導火線が燃え尽きる時間を計算し，その和がすべて燃え尽きるのにかかる時間になるため，その半分の値が二つの火がぶつかる時間になります．

from ast import Pass


N = int(input())
fuse = []
time = 0
for _ in range(N):
    a, b = map(int, input().split())
    time += a/b
    fuse.append([a, b])
time /= 2

i = 0
passed_time = 0
length = 0
while True:
    if passed_time + fuse[i][0]/fuse[i][1] >= time:
        rest_time = time - passed_time
        print(length + rest_time*fuse[i][1])
        break

    else:
        length += fuse[i][0]
        passed_time += fuse[i][0]/fuse[i][1]
    
    i += 1