Educational Codeforces Round 157

https://codeforces.com/contest/1737

시스텟 돌기 전 스탠딩

 

---

A. Treasure Chest [00:03:35]

열쇠의 위치가 상자보다 왼쪽에 있다면 상자를 굳이 옮길 필요가 없다.

상자가 열쇠보다 왼쪽에 있다면 가능한 상자를 오른쪽으로 옮겨줘야 한다. 열쇠 위치에 도달했다가 다시 상자로 와야 하기 때문이다.

https://codeforces.com/contest/1895/submission/231136403

---

B. Points and Minimum Distance [00:06:58]

$x$와 $y$ 를 분리해서 생각해도 상관이 없고, $A$를 정렬하고 시작하자.

1차원인 경우에는 단순히 $A_{2N} - A_1$이 답이 되는데, 따라서 2차원인 경우에도 비슷하게 $A_{2N} - A_{N+1} + A_N - A_1$이 답이 된다. 따라서 정렬 후 앞의 원소 절반을 순서대로 방문할 점의 $x$좌표로, 뒤의 원소 절반을 방문할 점의 $y$좌표로 두면 된다.

https://codeforces.com/contest/1895/submission/231140864

---

C. Torn Lucky Ticket [00:21:24]

티켓 개수가 $200\ 000$개이기 때문에 자릿수 합이 같은 티켓을 묶어서 계산해야 하는 문제이다. 자릿수가 같은 티켓끼리 모으고 시작하자.
1. 같은 티켓을 연속해서 붙이면 항상 조건을 만족한다. 따라서 답에는 항상 $N$이 더해지게 된다.

2. 두 티켓 $a$와 $b$가 있을 때, $a + b$는 조건을 만족할 수 있지만 $b + a$는 그렇지 않을 수 있다. 따라서 $|a| < |b|$인 경우와 $|a| > |b|$인 경우를 나눠서 각각 짜줘야 한다. 더 손이 안 가는 구현 방법이 있는지는 잘 모르겠다.

$|a| \neq |b|$인 경우의 구현에 대해서 짧게 메모하자면, $|a| < |b|$인 경우에는 $a$의 자릿수 합이 같은 것끼리 모아두고, $b$의 경우에는 $a$ 쪽에 붙어야 하는 자릿수 합과 나머지 자릿수 합을 pair로 저장하는 식으로 구현했다. 

https://codeforces.com/contest/1895/submission/231157035

---

D. XOR Construction [00:35:23, 0]

무조건 만들 수 있는 경우만 주어진다고 했기 때문에, 우선 조건을 만족하는 경우를 아무거나 하나 구해보자.

각 비트마다, $B$의 특정 비트가 켜져 있는지 안 켜져 있는지를 판단해줄 것이다. 이 여부는 $A_i$의 해당 비트가 켜져 있을 때마다 반전된다. 아래 표와 같은 느낌이다.

A		1				1		1
B	0		1	1	1		0		1

 

$B$의 어떤 값의 해당 비트가 정확하게 켜져 있어야 하는지는 알 수 없지만, 적어도 어떤 연속된 값들이 같은 비트 상태를 가져야 한다는 사실은 위를 통해 알 수 있다. 같은 비트 상태를 가지는 연속된 값들을 구간이라고 하자.

홀수 번째 구간과 짝수 번째 구간 각각에 몇 개의 원소들이 들어가 있는지를 세자. 그리고 $[0, N)$ 구간의 값들 중 해당 비트가 켜져 있는 값의 수와 꺼져 있는 값의 수도 같이 세자. 홀수 번째 구간과 짝수 번째 구간 중, 비트가 켜져 있는 값의 수와 일치하는 쪽에 모두 해당 비트가 의미하는 값 ($2^k$) 만큼을 더해주면 된다. 

 

이제 이렇게 만든 배열 $B$가 모두 $[0, N)$ 사이 구간에 들어오도록 보정해줘야 한다.

(홀수 번째 구간과 짝수 번째 구간에 포함되는 원소 수가 같을 때 배열 $B$가 유일하게 결정이 되지 않을 수 있기 때문에 보정을 해줘야 하는 경우가 생긴다. 구현 방식에 따라 다를 수 있겠지만, 나는 예제 2번이 그런 경우에 해당했다.)

모든 비트에 대해, 배열 $B$에서 비트가 켜져 있는 값의 수와 $[0, N)$ 구간에서 비트가 켜져 있는 값의 수가 다르다면 $B$ 전체에 해당 비트가 의미하는 값을 xor 해주면 된다. 

https://codeforces.com/contest/1895/submission/231166173

---

E. Inifinite Card Game [01:09:25, -1]

Monocarp가 처음에 내는 카드의 공격력은 중요하지 않다. 처음에 내는 카드의 방어력만 중요하다.

Monocarp와 Bicarp의 최적 전략은 동일하다. 상대가 낸 방어력보다 높은 공격력을 가지면서, 그 중 가장 방어력이 높은 카드를 내는 것이다. 따라서 한 사람이 어떤 카드를 냈을 때, 어떤 방어력을 가진 카드가 답신으로 돌아올지는 정해져 있다. 여기서 Functional Graph의 향기를 약간 느낄 수 있다.

 

카드의 공격력과 방어력을 싹 모아서 좌표 압축을 하고 시작하자. 그리고 Monocarp와 Bicarp가 낼 수 있는 모든 방어력에 대해, 해당 방어력을 가진 카드를 냈을 때 어떤 방어력을 가진 카드가 돌아올 지를 계산한다. 대충 계산을 하려면 공격력을 index로, 방어력을 value로 가지는 최대 세그먼트 트리를 이용해서 구할 수도 있고, 어차피 필요한 모든 쿼리가 $[k, SZ]$와 같이 Suffix Max 형태에 해당한다는 점을 이용하면 그냥 $O(N)$에 구해도 된다. 이 값들을 모두 구해두면 Functional Graph 형태를 하나 얻을 수 있다.

 

이제 두 가지 방법으로 문제를 해결할 수 있는데,

1. Functional Graph에서 DP를 한다. 중간에 사이클을 만나면 무승부, 마지막으로 이동한 간선이 Monocarp면 승리, Bicarp면 패배이다. 짜보진 않았지만 별로 쉽지 않을 것 같다.

2. 승패가 갈리는 구간이 단조성을 가진다는 점을 이용한다. $LLLLDDDDDWWWW$ 의 형태에서 $LD$에 해당하는 구간을 찾고, $DW$에 해당하는 구간을 각각 이분 탐색으로 찾는다. 이기고 지는 건 직접 Functional Graph를 따라가보면서 확인한다. 무승부 여부를 잘 처리해줘야 하는 것 같다.

 

$M$을 써야 하는 곳에 $N$을 썼다가 한 번 틀렸다.

https://codeforces.com/contest/1895/submission/231182104

---

F. Fancy Arrays [Not Solved]

풀이의 큰 틀을 어렵지 않게 생각할 수 있다.

1. $||a_i - a_{i+1} \le K||$ 와 $a_i \le 0$을 만족하는 수열의 개수를 구한다.

2. 모든 값이 $[0, X)$ 구간에 있으면서, 조건을 만족하는 수열의 개수를 1에서 뺀다.

3. 모든 값이 $[X+K, INF)$ 구간에 있으면서, 조건을 만족하는 수열의 개수를 3에서 뺀다.

 

2에 해당하는 부분은 $X \le 40$ 이라는 점을 이용하면 대충 행렬 제곱으로 구할 수 있다. 1-3에 해당하는 값을 잘 구하는 게 관건이다. 

1-3을 다른 표현으로 정리하면, $[0, X+K)$ 구간의 수를 하나라도 포함하는 수열의 개수를 세는 문제가 된다. 이 개수는 $(X+K)^{2K-1}$ 이다. https://codeforces.com/blog/entry/121963?#comment-1082794

 

구현은 귀찮다...