pseong

Problem - E - Codeforces codeforces.com 먼저 x가 y를 이긴다라는 것을 x에서 y로 가는 간선이 존재한다고 하자. 그리고 어떤 그래프에서 다른 모든 노드로 갈 수 있는 노드를 후보라고 하자. Lemma 1. 토너먼트의 승자는 최소 한 명은 존재한다. (후보는 무조건 한 명 존재한다.) Proof. 먼저 n이 1 또는 2일 때를 생각해 보자. 1 또는 2일 때는 무조건 어떤 한 노드는 다른 모든 노드를 방문할 수 있다. 여기서 노드를 하나씩 추가해 보자. 지문에 나온 대로 완전 그래프여야 하기 때문에 노드 하나를 추가할 때마다 기존에 있던 모든 노드와 연결되어야 한다. 여기서 기존에 있던 노드 중에서 모든 노드를 방문할 수 있는 노드를 x라 하자. 새로 추가하는 노드를 y라..

A번은 문제를 처음에 잘못 읽어서 조금 헤멨다. L과 R이 자기 자신도 포함해서 불빛을 밝혀 주는 줄 알았는데 아니었다. 아무튼 문자열에 R 다음에 L이 나오면 0이고 RL 문자가 있으면 R의 위치고 그게 아니라면 -1이다. B번은 구성적 문제고 배열을 만드는 문제다. 짝수일 땐 -1 0 -1 0 반복해서 출력해 주면 되고 홀수일 땐 식 잘 세우면 답이 나온다. C번은 또 배열 문제인데 관찰이 생각보다 간단해서 순조롭게 풀었다. m번째 원소 포함 왼쪽 구간에서 어떻게 두 개로 자르던 m번이 포함된 조각이 음수가 되게 해야 한다. m번째 원소 다음부터 끝까지 구간에서는 구간을 어떻게 두 개로 자르던 m번째 다음 원소가 포함된 구간이 양수여야 한다. 이 사실을 알았으면 우선순위 큐를 써서 잘 구현하면 된다...