개인 노트

감상

abc3 완료
나는 c점 상황을 고려하는 것이 매우 번거롭다고 생각해서 미루었다. 정말 미안하다

A - Square Inequality

문제에 따라

A, B, C = map(int, input().split())

if A ** 2 + B ** 2 < C ** 2:
    print("Yes")
else:
    print("No")

B - Intersection

질문문보다 x가 전부 A 이상이고 전부 B 이하의 숫자라면
따라서 A의 최대치 이상, B의 최저치 이하의 숫자 개수는

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

print(max(0, min(B) - max(A) + 1))

C - IPFL

질문별로 설치 후 TLE(완료)
따라서 고속화가 필요하다
T=1의 조회는 O(1)에서 조회할 수 있을 것 같아서 T=2를 빨리 하려고 합니다.
문자열 S의 전반부와 후반부는 두 변수로 관리된다
T=2의 검색어에서 이 두 개를 바꾸다
T=1의 검색에서 다음과 같이 두 개를 연결하고 A와 B를 교환하는 것이 비교적 쉽다. 이렇게 하면 TLE가 된다.
4

if T == 1:
    S = first + last
    S[a], S[b] = S[b], S[a]
    first = S[:N]
    last = S[-N:]

따라서 A와 B를 연결하지 않고 스왑
A와 B가 각각 앞부분과 뒷부분을 표시하는 것을 주의하면서 교환하면 k

N = int(input())
S = list(input())
Q = int(input())

first = S[:N]
last = S[-N:]
for _ in range(Q):
    t, a, b = map(int, input().split())

    if t == 2:
        first, last = last, first
        continue

    a, b = sorted([a - 1, b - 1])
    if b + 1 <= N:
        first[a], first[b] = first[b], first[a]
    elif a + 1 <= N and N < b + 1:
        first[a], last[b - N] = last[b - N], first[a]
    else:
        last[a - N], last[b - N] = last[b - N], last[a - N]

print("".join((first + last)))

D - RGB Coloring 2

스스로 설치할 수 없기 때문에 참고한 코드는 기본적으로 모두 복제된 것이다
각 연결 성분은 독립된 것 같기 때문에 각 연결 성분에 따라 고려한다.
DFS가 각 접속 구성 요소의 색상 조건을 충족하는 경우 이 솔루션을 사용할 수 있습니다.
따라서 DFS 구현을 고려합니다.
먼저 첫 번째 정점 i를 적당한 색깔로 칠한 다음에 인접한 정점을 조건으로 가득 칠한다.
i와 인접한 정점에는 i의 색을 제외한 두 가지 색의 선택이 있다.
이상의 중복은 각 정점에서 진행되기 때문에 계산량은 O(N\times2^N)로 매우 빠르다.
이번 도표는 간단한 도표로 폐쇄될 수 있다.
나무의 DFS처럼 어떤 정점에 접근했는지 관리하는 동시에 인접한 정점으로 이동하면 정점의 접근 순서는 다르지만 색의 칠법은 같은 상황을 반복한다.
이런 상황을 피하기 위해 정점의 바르는 순서를 고정시킨다.

참고 자료

https://atcoder.jp/contests/abc199/submissions/21989290
https://atcoder.jp/contests/abc199/editorial/1163
https://kanpurin.hatenablog.com/entry/2021/04/25/054305

def search_connect(n: int):
    """連結成分をDFSで探索

    Args:
        n (int): 頂点の番号
    """
    seen[n] = True
    connect.append(n)
    for i in E[n]:
        if seen[i]:
            continue
        search_connect(i)
    return


def paint(con_i: int):
    """connect配列に含まれている頂点番号順に，頂点に色を塗っていく．
    color配列は各頂点の色，インデックスは頂点の番号

    Args:
        con_i (int): connect配列のインデックス

    Returns:
        (int): 場合の数
    """
    node_num = connect[con_i]
    # 隣接する2頂点の色が重複していないかを確認
    if any(color[node_num] == color[j] for j in E[node_num]):
        return 0

    # 全ての頂点に色を振り，重複してカウントしていないかを確認
    if con_i == len(connect) - 1:
        return 1

    # 頂点に色を塗っていく順番がconnect配列によって一意に定まっているため，
    # 次の頂点の色は必ず未定である0になっている．
    # よって，次の色が既に塗られているかどうかといった判定は不要
    res = 0
    for j in (1, 2, 3):
        color[connect[con_i + 1]] = j
        res += paint(con_i + 1)
    color[connect[con_i + 1]] = 0
    return res


N, M = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(lambda x: int(x) - 1, input().split())
    E[a].append(b)
    E[b].append(a)

ans = 1
seen = [False] * N
for i in range(N):
    if seen[i]:
        continue
    # 連結成分を探索
    connect = []
    search_connect(i)

    color = [0] * N
    color[i] = 1
    # 最初の色が何でもそれぞれの色での場合の数は一緒なので，1色の場合の数を3倍
    ans *= paint(0) * 3

print(ans)