[AtCoder] Beginner 399

https://atcoder.jp/contests/abc399

A

O(N) 으로 해결 가능하다.

B

동순위를 고려하여 출력하는 문제.
마지막 출력을 잘 해야해서 index 관리가 귀찮아서 객체로 관리했다.

import sys
r=sys.stdin.readline

class IINT:
    def __init__(self, x):
        self.value = x
        self.rank = 1

n=int(r())
p=list(map(int,r().split()))
p=[IINT(x) for x in p]
tmp = sorted(p, key=lambda x: -x.value)
rank = 0
prev = tmp[0]
for i in range(n):
    v = tmp[i].value
    rank += 1
    if prev.value == v:
        tmp[i].rank = prev.rank
    else:
        tmp[i].rank = rank
    prev = tmp[i]

for i in range(n):
    print(p[i].rank)

C

보통 Beginner면 C번까지는 쉬운데..
Forest, Tree로 만들라고 하니 $N$개의 노드가 Tree이려면 간선이 $N-1$개라는 성질을 사용하여 N, M 만으로 해결하려 했더니.. 모든 노드가 연결되어 있지 않을 수 있다.
=> disjoint set 사용

import sys
r=sys.stdin.readline

n,m=map(int,r().split())
parent = [i for i in range(n+1)]
rank = [0]*(n+1)
nodes = [1]*(n+1)

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

def union(x,y):
    x = find(x)
    y = find(y)
    if x == y:
        rank[x] += 1
        return
    merge(x,y)

def merge(x,y):
    parent[y] = x
    rank[x] += rank[y] + 1
    nodes[x] += nodes[y]

for i in range(m):
    u,v=map(int,r().split())
    union(u,v)
    
ans = 0
for i in range(1,n+1):
    if i == find(i):
        ans += max(0,rank[i] - (nodes[i] - 1))
print(ans)   

D

adjacent한 원소들끼리 확인해주면 되는데..

1 2 2 1
1 2 1

이런 케이스를 잘 처리해줘야했다.
구현을 못해서 많이 틀린 문제

import sys
r=sys.stdin.readline

T = int(r())
for _ in range(T):
    N = int(r())
    A = list(map(int, r().split()))
    addjacency = [0]*(N+1)
    for i in range(2*N-1):
        if A[i] == A[i+1]:
            addjacency[A[i]] = 1

    s = set()
    ans = 0
    prev_pair = None
    for i in range(2*N-1):
        if addjacency[A[i]] or addjacency[A[i+1]]:
            prev_pair = None
            continue
        a,b=A[i],A[i+1]
        if a > b:
            a,b = b,a
        pair = (a,b)
        if prev_pair and prev_pair == pair:
            prev_pair = None
            continue
        if pair in s:
            ans += 1
        else:
            s.add(pair)
        prev_pair = pair
    print(ans)

E

사이클이 발생할 경우 특이 케이스가 생긴다.
사이클이 존재하더라도 inDegree가 존재하면 우회해서 갈 필요가 없다.
a-z까지 전부 사이클이라면 우회할 곳이 없어서 -1일 것이다.
단방향 그래프이므로 SCC로 풀려했지만.. 구현력이 딸려서 못풀었다.
대회가 종료되고, 1시간을 더 투자해서 업솔빙했다.
https://boj.kr/27558 에 같은 문제가 있었다.
나만 모르는 웰노운이지..

SCC와 inDegree 개수로 문제를 해결했다.

import sys
r=sys.stdin.readline
sys.setrecursionlimit(10**6)
from collections import deque

N=int(r())
S=r().rstrip()
T=r().rstrip()

alpha = 26
arr = [-1] * alpha
rev_arr = [-1] * alpha
def convert(c):
    return ord(c) - ord('a')

for i in range(N):
    if arr[convert(S[i])] == -1:
        arr[convert(S[i])] = convert(T[i])
        rev_arr[convert(T[i])] = convert(S[i])
    else:
        if arr[convert(S[i])] != convert(T[i]):
            print(-1)
            exit(0)
flag = 1
vertex = 0
unused = 0
for i in range(26):
    if rev_arr[i] == -1: unused = 1
    if arr[i] == -1:
        continue
    if arr[i] != i: 
        flag = 0
        vertex += 1
if flag:
    print(0)
    exit(0)

if unused == 0:
    print(-1)
    exit(0)

# SCC
ans = []
finished=[0]*alpha
stack=[]
d=[-1]*alpha
id=0
def dfs(cur):
    global id, ans
    id+=1
    d[cur]=id
    stack.append(cur)
  
    parent = d[cur]
    adj = arr[cur]
    if adj != -1:
        if d[adj]==-1: 
            parent=min(parent, dfs(adj))    
        elif not finished[adj]:
            parent=min(parent, d[adj])

    if parent==d[cur]:
        scc=[]
        while 1:
            x = stack.pop()
            finished[x]=1
            scc.append(x)
            if cur==x: break
        ans.append(sorted(scc))
    return parent

for i in range(alpha):
    if arr[i]==-1: continue
    if d[i]==-1: dfs(i)

inDegree=[0]*len(ans)
for i in range(len(ans)):
    for j in range(i+1, len(ans)):
        for a in ans[i]:
            for b in ans[j]:
                if arr[a] == b:
                    inDegree[j] += 1
                elif arr[b] == a:
                    inDegree[i] += 1

count = 0
for i in range(len(ans)):
    if len(ans[i]) == 1: continue
    if inDegree[i] == 0:
        count += 1

print(count + vertex)

SCC를 만들어주고 SCC Node의 inDegree가 0이면 우회해서 가야한다.
inDegree가 0인 알파벳이 존재한다 iff 우회할 수 있는 알파벳이 존재한다.