A. EhAb AnD gCd

문제

예시

[input]
2
2
14

[output]
1 1
6 4

답1 – 이곳을 클릭하면 정답이 보입니다
def answer(n) :
  return str(1) + " " + str(n-1)

testCount = int(input())
for _ in range(testCount) :
  n = int(input())
  print(answer(n))

답2 – 이곳을 클릭하면 정답이 보입니다

설명

B. CopyCopyCopyCopyCopy

문제

예시

[input]
2
3
3 2 1
6
3 1 4 1 5 9

[output]
3
5

답1 – 여기를 클릭하면 정답이 보입니다
def answer(arr) :
  return len(set(arr))

testCount = int(input())
for _ in range(testCount) :
  n = int(input())
  arr = list(map(int, input().split()))
  print(answer(arr))

답2 – 여기를 클릭하면 정답이 보입니다

설명

C. Ehab and Path-etic MEXs

문제

예시

[input]
3
1 2
1 3

[output]
0
1

[input]
6
1 2
1 3
2 4
2 5
5 6

[output]
0
3
2
4
1

답1 – 여기를 클릭하면 정답이 보입니다
def answer(nodeCount, edges) :
  labels = [-1] * len(edges)
  threeAboveConnectedNodeNumber = 0
  labelNumbers = [i for i in range(3, len(edges))]
  mins = [0, 1, 2]
  tree = [[] for _ in range(nodeCount+1)]
  for i in range(len(edges)) :
    u, v, li = edges[i]
    tree[u].append(li)
    if len(tree[u]) == 3 :
      for j in range(0, 3) :
        labels[tree[u][j]] = mins.pop()
      break
    tree[v].append(li)
    if len(tree[v]) == 3 :
      for j in range(0, 3) :
        labels[tree[v][j]] = mins.pop()
      break
  if len(mins) == 3 :
    labels = [i for i in range(len(edges))]
  else :
    for i in range(len(labels)) :
      if labels[i] == -1 :
        labels[i] = labelNumbers.pop()
  return "\n".join([str(i) for i in labels])

nodeCount = int(input())
edges = []
for i in range(nodeCount-1) :
  u, v = map(int, input().split())
  edges.append([u, v, i])
print(answer(nodeCount, edges))

모든 MEX(u, v)중 분명 최대값이 있을건데, 이거를 가능한 작게 만드는게 핵심이다. 그러면 작게 만들기전에, 크게 만들려면 어떻게 해야할까? 크게 만드는짓을 안하면 작게 만들 수 있지 않을까?

이미지에 대체텍스트 속성이 없습니다; 파일명은 SmartSelect_20200401-185838_S-Note.jpg 입니다.

위 그림에서 가장 큰 MEX(u, v)가 4정도 될 것 같은데,,, 4로 만드려면 어떻게 해야할까?

이미지에 대체텍스트 속성이 없습니다; 파일명은 SmartSelect_20200401-190045_S-Note-791x1024.jpg 입니다.

그러면 작은 값들(0, 1, 2, 3)을 일열로 놓으면 안되겠구나!
작은수들을 가능한 흩뿌려 놔야겠다.

이미지에 대체텍스트 속성이 없습니다; 파일명은 노트13_3-1024x537.png 입니다.

이렇게 흩뿌려 놓으면 어떤 MEX(u, v)도 최대 2를 넘을 수 없게된다.

근데! 정말 다양한 graph가 나올텐데 작은수들을 어떻게 무슨 기준으로 흩뿌려 놓으며, 작은수들을 고르는 기준은 무엇일까?… 이 방향은 조금 아닌것같다.

다시 돌아가서 작은값들(0, 1, 2, 3)을 일렬로 놓으면 안된다는 아이디어에서 시작해보자.

일렬로 놓지 말라는거는, 작은값들을 동시에 다 지나지 못하도록 해야한다는 말이다.
다시 말해서, 모든 경로에 대해서 0, 1, 2, 3(예를들어) 중에 하나 두개 정도만 빼놓고 지나가도록 만들어야 한다는 거다. 그 빼먹은 놈(지나지 않은 점)이 MEX를 돌렸을때 작은놈이 되기 때문이다.

이렇게 생각하는게 ‘흩뿌린다’ 라는 말보다 덜 애매하다.

어떻게 해야 다 못지나게 할까?

일단 그래프가 1자로 생겼다면 어림도 없다. 모두 지나가게 될것이다.

이미지에 대체텍스트 속성이 없습니다; 파일명은 노트13_41-1024x537.png 입니다.

아! 아래와 같이 하면 0, 1, 2를 모두 한번에 못지나가게 할 수 있다.

이미지에 대체텍스트 속성이 없습니다; 파일명은 노트13_5-1024x537.png 입니다.

더군다나 이렇게 하면 그래프가 아무리 복잡해도 절대로 0, 1, 2를 한번에 지날 수 없다. 왜냐하면 Tree는 순환되지 않는 그래프이기 때문이다.

다시말해서, 저렇게 3갈래길에 0, 1, 2를 배치하고 모든 노드에 대해서 MEX(u, v)값을 구해도 최대값이 2를 넘지 못한다는 의미이다. 끽해야 2가 될것이다(0과 1을 같이 지나는 경우).

이 아이디어를 바탕으로 위의 코드를 읽으면된다.

답2 – 여기를 클릭하면 정답이 보입니다

설명