AtCoder ABC225 個人的メモ

A - Distinct Strings

from itertools import permutations

S = input()

seen = set()
for s in permutations(S):
    seen.add(s)

print(len(seen))

B - Star or Not

全ての辺に共通して含まれている頂点があればYes

N = int(input())

common_node = set(range(1, N + 1))
for _ in range(N - 1):
    a, b = map(int, input().split())
    common_node &= {a, b}

if len(common_node) == 1:
    print("Yes")
else:
    print("No")

C - Calendar Validator

判定が必要な行列$B$は、最大でも$N\times M=7\times 10^4$マスなので全探索すればおｋ
判定は$B$の$(i,j)$成分が$(i-1)\times 7+(Bの(0,0)成分の値)$と一致するかを判定
また、行列$A$は7列なので行列$B$の右端以外に7の倍数が含まれているとNoになる

N, M = map(int, input().split())
B = [list(map(int, input().split())) for _ in range(N)]

res = B[0][0]
for i in range(N):
    for j in range(M):
        if B[i][j] != i * 7 + j + res:
            print("No")
            exit()
        if j and B[i][j - 1] % 7 == 0:
            print("No")
            exit()

print("Yes")

D - Play Train

電車$x$が含まれる連結成分に属する電車の個数を$M$とする。
最後の制約により、1番2番のクエリを計算量1で行えば3番の出力するクエリは$M$の計算量が掛かっても良いと分かる。
よって各電車の前後に連結している電車の番号を保持しておけば、3番のクエリが来たときに$x$の前後にある電車の順番を計算量$M$で求めることができる。

N, Q = map(int, input().split())

next_train = [[-1, -1] for _ in range(N + 1)]
for _ in range(Q):
    q, *M = map(int, input().split())
    if q == 3:
        x, *_ = M
        ans = [x]
        # xよりも前にある電車を求める
        now = x
        while next_train[now][0] != -1:
            ans.append(next_train[now][0])
            now = next_train[now][0]

        ans = ans[::-1]

        # xよりも後にある電車を求める
        now = x
        while next_train[now][1] != -1:
            ans.append(next_train[now][1])
            now = next_train[now][1]

        print(len(ans), *ans)
        continue

    x, y = M
    if q == 1:
        next_train[x][1] = y
        next_train[y][0] = x
    if q == 2:
        next_train[x][1] = -1
        next_train[y][0] = -1

E - 7

$(x_i,y_i)$を残す場合に、その"フ"によって占有される範囲は原点から見て$\arctan \frac{y-1}{x}$から$\arctan \frac{y}{x-1}$の角度の範囲
これらの範囲からできるだけ多くを選びたいので区間スケジューリング問題と考えれる。
浮動小数点誤差を考慮しないとwaする。

from decimal import Decimal

N = int(input())
INF = 10 ** 18

lst = []
for _ in range(N):
    x, y = map(Decimal, input().split())
    if x > 1:
        end = y / (x - 1)
    else:
        end = INF
    start = (y - 1) / x
    lst.append((end, start))
lst.sort()

ans = 0
last_end = 0
for e, s in lst:
    if last_end <= s:
        ans += 1
        last_end = e

print(ans)