Codeforces Round 859 (Div. 4)

A. Plus or Minus

code

 

\(a\), \(b\), \(c\)가 주어진다. \(a + b = c\) 또는 \(a - b = c\)를 만족한다. 둘 중 어느것을 만족하는 지 출력하면 된다.

문제에서 시키는대로 하면 된다.

 

B. Grab the Candies

code

 

\(N\)개의 가방이 있고, \(i\)번째 가방에는 \(a_i\)개의 사탕이 있다. 이제 가방을 특정한 순서대로 열 것이다. 만약 가방에 짝수 개의 사탕이 있다면, Mihai가 그 가방에 있는 사탕을 모두 가진다. 반대의 경우에는 Bianca가 모두 가져간다. 이제 가방을 여는 순서를 잘 배열해서 처음부터 모든 가방을 열 때까지 항상 Mihai가 Bianca보다 사탕을 많이 가지고 있도록 하게 하고 싶다. 가능하면 Yes, 불가능하면 No를 출력해야 한다.

 

간단한 그리디 문제이다. 일단 사탕이 짝수 개 들어있는 가방을 모두 열어서 Mihai에게 사탕을 주고, 남은 가방을 열어서 Bianca에게 준다. 만약 맨 마지막에 Mihai가 사탕이 더 많으면 Yes, 아니면 No를 출력하면 된다. 맨 마지막에 Mihai가 사탕이 더 많다면, 어느 시점에서든 Mihai가 사탕이 더 많게 된다.

 

C. Find and Replace

code

 

영어 소문자로 이루어진 문자열이 주어진다. 특정 알파벳을 0 또는 1로 바꿀 수 있다. 이렇게 26종류의 알파벳을 각각 0 또는 1로 바꾸었을 때, 최종 문자열이 0101010.... 또는 1010101... 꼴로 만들 수 있으면 Yes, 아니면 No를 출력해야 한다.

 

일단 문자열을 01010...으로 바꿔보자. 그럼 각 알파벳은 0 또는 1로 바뀔 것이다. 그런데 한 알파벳이 0으로도 바뀌고, 1로도 바뀌면 문제의 조건을 어기게 된다. 따라서 특정 알파벳이 홀수 번째에도 있고 짝수 번째에도 있다면 Yes, 아니면 No를 출력하면 된다.

 

D. Odd Queries

code

 

정수로 이루어진 배열 \(a\)가 주어질 때, \(q\)개의 쿼리를 처리해야 한다. 각 쿼리는 \(l, r, k\)로 구성되어 있으며 내용은 아래와 같다.

 

\(a_l, a_{l+1}, \dots, a_r\)을 \(k\)로 바꾸면 \(a\)의 합이 홀수면 Yes, 아니면 No를 출력해야 한다.

 

일단 전처리를 해두면 특정 구간을 \(k\)로 바꾸었을 때 \(a\)의 합 자체를 \(O(1)\)에 구할 수 있다. 누적합을 이용하면 된다.

\(sum_i = a_1 + a_2 + \dots + a_i \)로 정의하자. 그렇다면 \(a_l\)부터 \(a_r\)까지 \(k\)로 바꾼 배열 \(a\)의 합은 아래와 같다.

\(sum_n-sum_r+sum_{l-1}+k\times(r-l+1)\)

따라서 각 쿼리마다 위 값을 계산해서 홀수면 Yes, 짝수면 No를 출력하면 된다.

 

E. Interview

code

 

총 \(N\)개의 돌 묶음이 있고, \(i\)번째 묶음에는 돌이 \(a_i\)개 있다. 하나의 돌에는 2가 적혀있고, 나머지 돌에는 1이 적혀있다. 이제 최대 30번의 질문을 통해 2가 적혀있는 돌이 어느 묶음에 있는 지 찾아야 한다. 한 번의 질문은 아래와 같이 이루어진다.

 

\(N\)개의 묶음 중 \(k\)개의 묶음을 고른다. 그러면 \(k\)개의 돌 묶음에 적혀있는 숫자의 합을 알려준다.

 

이 문제는 이분 탐색을 통해 풀 수 있다. 먼저 D번 문제처럼 누적합을 이용해 1번부터 \(i\)번 묶음까지의 돌의 개수를 계산해두고 이를 \(sum_i\)라 하자. 이제 \(l\)과 \(r\) 사이에 2가 적혀있는 돌이 있다고 하자. 그렇다면 한 번의 질문을 통해 이 범위를 절반으로 줄일 수 있다. 먼저 \(mid = \frac{l+r}{2}\)라 하자. 이제 질문을 통해 \(l\)번째 묶음부터 \(mid\)번째 묶음까지 돌에 적혀있는 숫자의 합 \(x\)를 알 수 있다. 만약 \(x = sum_{mid} - sum_{l}\), 즉 돌의 개수와 합이 동일하다면 2가 적혀있는 돌은 \(mid+1\) ~ \(r\) 구간에 있다는 것이고, 돌의 개수와 합이 동일하지 않다면 2가 적혀있는 돌은 \(l\)~\(mid\) 구간에 있다는 것이다.

 

\(N\)이 최대 20만이기 때문에 약 20번의 질문 만으로도 돌의 위치를 찾을 수 있다.

 

F. Bouncy Ball

code

 

\(N\times M\)의 판에서 공이 대각선 네 방향으로 이동한다. 또한 벽에 부딪히면 반대 방향으로 이동한다. 이제 \(t\)개의 질문에 답을 해야 한다.

만약 \(n \times m\)의 판에서 공이\( (i1, i2)\)위치에 있고 처음 이동 방향이 \(d\)일 때, 최소 몇 번 벽에 부딪혀야 \( (j1, j2)\)로 이동하는지 출력해야 한다. 만약 이동할 수 없다면 -1을 출력해야 한다.

 

문제 조건을 보면 판의 크기인 \(n\times m\)이 \(5\times 10^4\)를 넘지 않는다는 것을 알 수 있다. 따라서 \(O(NM)\)풀이도 허용된다.

 

현재 상태를 \( (r, c, d)\)로 정의하자. 이는 지금 \( (r, c)\)의 위치에 있고, 이동 방향이 \(d\)라는 것이다. 그리고 바로 현재 상태 바로 다음의 상태를 \(nxt(r, c, d)\)라 하자. \(nxt\)함수만 잘 구현해두면 문제를 풀 수 있다.

 

먼저 방문 확인 용 배열인 \(visited\)를 만들자. \(visited[r][c][d] = 1\)이라는 것은 현재 상태가 \( (r, c, d)\)로 변한 적이 있다는 뜻이다. 이제 \(nxt\) 함수를 이용하여 계속해서 다음 상태로 이동하자. 그리고 상태를 이동할 때마다 \(visited[r][c][d]\)를 1로 바꾸자. 만약 이렇게 다음 상태로 이동하다가 \( (j1, j2)\)로 이동했다면, 지금까지 벽에 부딪힌 횟수를 출력하면 된다. 벽에 부딪힌 횟수는 \(nxt\)함수에서 세주도록 하자. 하지만 만약 \(visisted[r][c][d]\)가 1로 바꾸지 않았는데 이미 1이었다면, 이는 이전에 \( (r, c, d)\)라는 상태가 된 적이 있었다는 뜻이다. 즉, 지금까지 \( (j1, j2)\)로 이동하지 못했다면 앞으로도 이동하지 못할 것이라는 의미이다. 따라서 이 경우에는 -1을 출력하면 된다.

 

G. Subsequence Addition

code

 

이 문제는 easy 버전과 hard 버전이 있는데, hard 버전을 기준으로 풀어보자. (사실 easy는 읽지도 않았다.)

 

먼저 배열 \(a\)가 있다. 이 배열 \(a\)에는 1이라는 숫자 하나만 있다. 이제 아래 과정을 여러 번 반복할 것이다.

 

\(a\)에 있는 숫자 중 몇 개를 고른 뒤 합 \(x\)를 구한다. 이제 \(x\)를 배열 중간에 넣는다. (맨 처음이나 끝에 두어도 된다.)

 

입력으로 배열 \(c\)가 주어진다. \(a\)를 \(c\)로 만들 수 있으면 Yes, 아니면 No를 출력하면 된다.

 

이 문제를 풀기 위해서는 중요한 관찰이 두 개 필요하다. 먼저 첫 번째 관찰은 무조건 숫자를 작은 숫자에서 큰 숫자 순으로 만드는 게 좋다는 것이다. 배열 \(a\)에 숫자 \(x, y\)를 추가할 것이라고 하자. \(x\)가 \(y\)보다 작다. 그렇다면 \(y\)를 만들 때 \(x\)를 사용할 가능성은 있지만 \(x\)를 만들 때 \(y\)를 사용할 가능성은 없다. 따라서 무조건 \(x\)를 먼저 만들고 \(y\)를 만드는 것이 좋다.

 

두 번째 관찰은 배열 \(a\)의 모든 원소의 합을 \(sum\)이라 하자. 그렇다면 1부터 \(sum\)까지의 모든 숫자를 \(a\)의 일부 숫자들을 합해서 만들 수 있다. 이를 증명하기 위해서는 귀납법을 이용해야 한다.

 

먼저 초기 상태에서 모든 원소의 합은 1이고, 1을 만들 수 있으므로 위의 명제가 성립한다.

이제 귀납적인 과정을 거쳐보자. 먼저 배열 \(a\)의 합이 \(sum\)이고 1부터 \(sum\)까지의 모든 숫자를 \(a\)의 일부 숫자들의 합으로 만들 수 있다고 가정하자. 이제 배열 \(a\)에 원소 \(x\)를 추가한 배열인 \(b\)도 위 명제가 성립하는 지를 보이면 된다.

 

먼저 추가된 숫자인 \(x\)는 1이상 \(sum\)이하인 수이다. 이는 \(x\)가 \(a\)의 일부 숫자들의 합으로 만든 숫자이기 때문이다. 이제 \(b\)의 일부 숫자들을 합해 1이상 \(sum + x\)이하인 수를 모두 만들 수 있는 지를 보이면 된다. 먼저 \(b\)는 \(a\)의 숫자들을 모두 가지기 때문에 1이상 \(sum\)이하인 수를 만들 수 있다. 또한 배열 \(b\)에 \(x\)가 추가되었으므로, \(1\)이상 \(sum\)이하인 수를 만드는 과정에서 \(x\)를 추가해 \(x + 1\)이상 \(sum + x\) 이하인 수를 만들 수 있다.

 

그렇다면 \(b\)에서 만들 수 없는 수는 \(sum\)보다 크면서 \(x+1\)보다 작은 수이다. 그런데 \(x+1\)은 \(sum+1\)이하인 수이다. 즉, \(b\)가 만들 수 없는 수는 \(sum\)보다 크면서 \(sum+1\)보다 작아야 한다는 것인데, 이를 만족하는 정수는 없다. 따라서 \(b\)는 \(1\)이상 \(sum + x\)인 수를 모두 만들 수 있다.

 

위의 두 관찰을 끝냈다면 배열 \(c\)를 만들 수 있는지는 쉽게 확인할 수 있다. 먼저 \(c\)를 정렬하자. \(c\)의 순서는 의미가 없기 때문에 정렬을 해도 된다. 일단 맨 처음 원소는 1이어야 하므로 \(c\)의 첫 번째 원소가 1인지를 확인한다. 만약 1이 아니라면 No를 출력하면 된다.

 

이제 \(a\)를 \(c\)로 만들 때, \(c\)의 2번째 원소부터 마지막 원소까지 순서대로 만들 것이다. \(c\)의 \(i\)번째 원소를 만들기 위해서는 \(c_1 + c_2 + \dots + c_{i-1} \ge c_i\)를 만족해야 한다. 따라서 이 조건을 모든 \(i\)에 대해 만족하는 지 확인하면 된다.

 

후기

div4는 항상 40분 정도 걸려서 푸는 거 같다. 이번에는 F에 시간을 오래 잡아먹었다. 문제 자체를 잘못 읽어서 한 10분정도 날린 거 같다. 또한, 몇몇 문제들이 int 범위에서 overflow나는 것들이 있어서 이런 것들도 주의해서 풀어야 한다.

 

div4의 제출 현황을 보면 초당 10개의 제출이 약 2시간동안 이어진다.... (대회 초반엔 사이트 접속도 힘들다.) 따라서 내 제출이 채점될 때까지 짧아도 10분, 길면 20분이걸린다. 즉, 구현할 때 틀리지 않고 한 번에 맞추는 것이 중요하다. 특히 이런 환경에서 구현 실수라던지 long long 이슈라던지 발생하면 억장이 무너진다. 그러니까 꼼꼼하게 구현하고 제출하도록 하자. 제출 한 번만 틀려도 순위가 엄청나게 내려간다.