Pinely Round 4 (Div. 1 + Div. 2)

 

한동안 PS를 안하고, 여러 가지 개발공부를 시작했다. HTML + CSS + JS 를 일주일안에 켠왕을 한다던지, 선형대수학을 한번더 파본다던지, 다양한 분야를 탐닉중이였다.  (아무것도 안하니, 뭐든 해보자는 생각이었다..) 그래도 코포는 무조건 꾸준히 참가해서 이런 환경의 문제를 푸는 것에 익숙해지려 했다. 이번 결과는 그래서, 4솔도 못했다. 4번째 문제는 심지어 레이팅이 낮았던 문제라서, 푸는 내내 당황만 계속했던 것 같다.

 

A, B, C는 보자마자 어떻게 풀어야 할 지 알았고, 그냥 한 번에 통과할 수 있도록 예외정도만 잠깐씩 깊게 살펴봤었다.

D에서 그냥 막혔다. A, B, C는 보자마자 정답이 튀어나왔는데, D에서 갑자기 난이도가 수직 상승해서, 무지 당황했다...

 

중간 중간.. 이건 쉬운문제다... 어떻게 그리디하게 깔끔하게 떨어지는 방법이 있을 것이다... 라며 세뇌하며... 노력했지만.. 정해에 근접도 못했다...

 

나머지 시간 2시간 30분가량을 D만 풀기 위해 썼는데도 근접도 못한 걸 보면, 그냥 이런 비트 관찰류 그리고 수학적 관찰을 요구하는 문제를 많이 풀어봐야겠다는 생각이 들었다.

 

이런식으로 언제.. 퍼플 오렌지나 찍어 볼 수 있을까..

D. Prime XOR Coloring

정답은 $6 \leq N $ 이상부터, $i$번째 노드에는 $(i \mod 4) + 1$의 값을 할당하는 것이 정답이다.

이게 왜 정답이냐면, 집합 $A_K$ 에 대해, $\text{A}_K = \big\{ x \; | \; x \mod 4 \equiv K \big\}$ 라고 하자.

 

집합 $A_K$에 속한 원소들 끼리 같은 번호를 부여했다고 해보자. 이 집합의 원소들의 Bitwise XOR 값은 소수가 될 수가 없다. 왜냐면, 최하위 비트 2개가 동일하여, 무조건 2보다 큰 짝수가 되기 때문이다.

 

그럼? 이 나누는 값을 2로 하여, 최대 지정 가능 색깔을 2로 해도 되지 않을까?

일단 예제가 그렇지 않지만, $\text{A}_K = \big\{ x \; | \; x \mod 2 \equiv K \big\}$ 라고 했을 때, 

$A_K$에 속한 원소들끼리 Bitwise XOR을 진행하면, 2 이상의 수 짝수가 나온다.

 

소수인 2가 나올 수도 있기 때문에, $A_K$에 속한 원소들에게 같은 수를 부여하면 안 된다.

여기서 관찰하고 생각해야 했던 것은, 또 역시, 닫혀있는 계에서의 수의 변화에 관찰을 더 했어야 했다는 점이다.
지금까지 한 번도 생각하지 않았던 부분은, $2^i$ 의 나머지 연산에서, 나머지가 같은 수들은 최하단 비트 $i+1$개가 같다는 관찰이다.

E. Coloring Game

이 문제는 읽지도 않았었다. 다음 대회부터는 안풀리는건 그냥 안잡고 다른걸 잡아야겠다. 이문제는 업솔빙으로 그냥 풀린 케이스다.

 

Alice와 Bob이 일반적인 Graph내에서 게임을 한다. Alice 는 색깔 1, 2, 3중에 두개를 제시하고, Bob은 원하는 노드에 Alice가 제시한 두 색깔중 하나를 칠할 수 있다.

 

Bob이 연결된 두 노드가 같은 색깔을 가지지 않게 하면 Bob이 이기고, 그렇지 않으면 Alice가 이긴다.

일단, Alice의 최선의 전략은, 그냥 색깔 두개만 제시하는거다.

 

그럼, Bob의 최선의 전략은 그냥 운명이다. 색칠을 할 수 있었으면 이기는거고, 그렇지 않으면 지는거다. Bob이 어떤 상황일 때, 이길 수 있을까? 그건 그래프가 이분그래프를 형성하고 있었을 때 이긴다.

 

자 그럼, 누가 이기는지 결정할 수 있으므로, 우린 그 사람을 선택해 진짜로 게임을 진행하면 된다.

 

Bob이 이길 때, Alice는 두 색깔만 주는 것이 아니다. 세개의 색깔을 주는데 어떻게 이분적으로 나뉜 그래프를 3색으로 연속되지 않게 색칠 할 수 있을까?

 

일단 이분적으로 1번으로 색칠할 노드와, 2번으로 색칠할 노드를 정해놓는다. 그 다음, Alice가 주는 번호가 1번 혹은 2번이 있다면, 우선적으로 칠한다.

 

후에 1번이나 2번으로 색칠할 노드가 더는 없을 경우, 나머지는 3번으로 색칠 해도 된다.