KimHwon

자다 일어났더니 대회가 2시간 가량 밖에 남지 않았다. solved.ac 뱃지 기준인 100점만 넘기자는 마인드로 대충 풀었다.

C. ko_orange (02:45)

[2100, 2400) 구간 내에서 이분 탐색을 하는데, 쿼리의 답이 잘못 주어질 수 있다. 그냥 같은 쿼리를 두 번씩 물어봐서 첫 번째 서브태스크만 해결했다.

A. 오렌지컵 출제하기 (03:02)

문제를 준비 시간으로 정렬하고 작은 것부터 그리디하게 골라 나갔다. 고르면서 어떤 출제자가 L개 이상의 문제를 내야 한다면 그 문제를 뛰어 넘는다. 이렇게 하여 세 번째 서브태스크까지 해결했다.

이 문제를 풀고 총 점수가 88점이었기에 100점만 만들자는 생각으로 모든 문제를 한 번 훑어보면서 찍먹했다.

D. 오렌지 섬 여행하기 (04:14)

첫 번째 서브태스크를 해결하기 위해 직접 $n=7$까지 손으로 그려 보니, 왠지 모든 n에 대하여 오렌지를 다 먹을 수 있을 것 같았다.

만약 $n=i$일 때 오렌지를 전부 먹을 수 있는 경로가 있다고 하면, $n=i+1$일 때 인접한 두 정점 사이에 $i+1$을 잘 끼워 넣으면 된다. $i+1$이 두 정점과 서로소일 때 끼워 넣을 수 있다. 또는 맨 앞이나 맨 뒤에는 인접한 한 정점과 서로소이기만 해도 된다. 이런 조건을 만족하면서 N까지 그리디하게 끼워 넣다 보면 해결할 수 있다.

혹시 몰라서 assert를 넣은 채 제출했는데 한 번에 맞았다.

I. 오렌지 키우기 (04:16)

$K=0$이라면 심는 즉시 오렌지를 수확할 수 있고, 이는 오렌지를 심을 수 있는 지점에 방문하고 돌아오는 데 걸리는 시간과 같다. 따라서 오렌지를 심을 수 있는 지점 중 가장 먼 곳의 거리를 답이다. 이렇게 하면 첫 번째 서브태스크를 해결할 수 있다.

대박났다. carrot에서 퍼플 퍼포먼스 찍힘 :blobhappy:

A. Digits Sum

interesting하지 않은 수는 맨 마지막 자리가 9인 수이다. 따라서 $\frac{(n+1)}{10}$이 답이다.

B. Reverse String

첫 번째로 주어진 문자열을 적절히 '접어서' 두 번째 문자열로 만들 수 있는지 확인하는 문제이다. 문자열의 길이가 500 이하로 매우 작으므로, '접는' 중심을 하나씩 잡아보면서 확인해볼 수 있다.

C. Penalty

페널티킥을 10번 할 때, 최대한 빨리 승패가 결정나는 횟수를 찾는 문제이다.

가능한 빨리 승패가 나는 경우로 첫 번째 팀이 최대한 많이 넣고 두 번째 팀이 최대한 적게 넣도록 ?를 채운 경우와, 첫 번째 팀이 최대한 적게 넣고 두 번째 팀이 최대한 많이 넣도록 ?를 채운 경우 두 가지를 확인해보면 된다. 각 경우에 대하여 남은 기회가 점수차보다 작아지면 승패가 결정난다. s의 길이가 10이므로 직접 시뮬레이션하면서 알아낼 수 있다.

D. Backspace

어떤 키 대신 backspace를 누른다면 그 키에 해당하는 알파벳 하나가 사라지고, 그 알파벳의 바로 앞의 문자가 지워진다. 즉, 연속한 2개의 문자를 지워서 주어진 문자열로 만들 수 있는지 확인하면 된다. 앞에서부터 순회하면서 그리디하게 진행하면 된다.

A번이 약간 말려서 당황했는데, 그래도 B, C가 잘 풀려서 다행이었다. 4솔도 노려볼 만했는데 더 풀지는 못해서 아쉽다.

A. AquaMoon and Two Arrays

두 수열이 주어지고 한 수열에 적절히 연산을 하여 두 수열이 같게 만들어야 한다. 일단, 연산을 해도 각 수열의 합은 보존되므로 두 수열의 합이 다르다면 무조건 불가능하다. 두 수열의 각 원소의 차를 구하고, 그 차가 0 초과인 원소를 0 미만인 원소에 옮겨주면 된다.

B. AquaMoon and Stolen String

n개의 문자열에서 한 개의 문자열을 없앤 뒤 남은 n-1개의 문자열을 섞는다. 이 때 없어진 문자열을 찾는 문제이다.n-1개의 문자열을 섞을 때 같은 열의 두 원소 즉, 문자열 S와 T가 있다면$S_i$ 와 $T_i$를 바꾼다. 따라서 각 열에 대하여 알파벳의 등장 횟수는 보존된다. 초기상태인 n개의 문자열에 대하여 각 열에 등장하는 알파벳의 수를 계산해두고, 섞인 n-1개의 문자열이 주어졌을 때, 각 열에 해당하는 알파벳의 수를 계산하면 사라진 알파벳 한 개를 찾을 수 있다.인터랙티브 문제인데 왜 인터랙티브인지 모르겠다.

C. AquaMoon and Strange Sort

버블정렬의 특성을 활용한 문제이다. 주어진 수열이 정렬되었을 때, 모든 원소가 처음 위치에서 이동한 거리가 짝수가 되어야 한다. 같은 수가 등장할 수 있기 때문에 이들을 적절히 재배치하는 것이 관건이다.

map을 사용하여 짝수 번째 위치에 나타나는 수와 홀수 번째 위치에 나타나는 수를 각각 센다. 정렬 한 후에 다시 짝수 번째 위치에 나타나는 수와 홀수 번째 위치에 나타나는 수를 센다. 두 상태에서 센 수가 같다면 ok이다. 이는 짝수 번째 위치에서 다시 짝수 번째 위치로 이동하고, 홀수 번째 위치에서 다시 홀수 번째 위치로 이동했기 때문에 조건을 만족한다. 반대로 두 상태에서 센 수가 다르다면 짝수 번째 위치에서 홀수 번째 위치로 이동하거나, 홀수 번째 위치에서 짝수 번째 위치로 이동한 수가 있다는 뜻이므로 불가능한 경우이다.

컨디션이 다시 올라왔고 잘 풀어서 기분이 좋다.

A. Exciting Bets

두 음이 아닌 정수 a, b가 주어졌을 때 적절한 연산을 하여 gcd(a, b)를 최대로 하는 문제이다. 먼저, 문제에 제시된 대로 0, 0이라면 INF라고 하니 $a = b$인 경우는 0, 0으로 만들면 될 것이다. $a \ne b$인 경우, $gcd(|a-b|, 0)$ 인 상태가 최대이다.

이는 $gcd(a, b) = gcd(a-b, b)$임을 통해 확인할 수 있다. 라운드 중에는 위의 등식이 생각나지 않아서 직접 예제를 만들어보다 보니 우연찮게 발견했다. 맞았으니 다행이긴 한데 많이 아쉬웠던 풀이.

B. Customising the Track

수열이 주어졌을 때 $\sum_{i=1}^n \sum_{j=i+1}^n | a_i - a_j |$이 최소가 되도록 적절히 연산을 하는 문제이다. 연산을 했을 때 수열의 원소의 합은 보존되기 때문에, 수열의 원소들에 최대한 균등하게 분배할 때가 최선이다. 따라서 n-reminder개의 sum/n과, reminder개의 sum/n+1가 구성된다.

C. Need for Pink Slips

$0.1 \leq v$이므로 c, m, p에 대하여 각각 최대 10번씩 밖에 선택되지 않는다. 따라서 완전탐색으로 모든 경우를 확인해볼 수 있다. 풀이 자체는 매우 쉬운데, 실수오차를 잘 핸들링하는 것을 의도한 문제 같다.

D1. RPD and Rap Sheet (Easy Version)

Easy version의 k=2 조건에서는 bitwise XOR과 동일하다. 1부터 n-1까지 모두 한 번씩 시도해 볼 수 있다. xor은 교환법칙과 결합법칙이 성립하므로, 이전에 시도해 본 값을 모두 xor해서 들고 다니다가 현재 시도할 값과 xor해서 시도하면 된다.

바닥을 모르고 떨어지고 있다. 사실 이전 포스트 사이에 참여한 라운드가 좀 있지만 엄청나게 망하고 멘탈이 다 갈려버려서 후기도 못썼다. 정신 좀 차려보자.

A. Odd Set

길이가 2n인 수열에서 적절히 원소를 둘씩 짝지어 각 쌍들이 모두 홀수가 되도록 할 수 있는지 확인하는 문제. 두 자연수의 합이 홀수가 되려면, 홀수+짝수 형태야 한다. 따라서 수열 내에서 홀수의 개수와 짝수의 개수를 세서 같으면 Yes 다르면 No이다.

B. Plus and Multiply (업솔빙)

첫 번째 연산인 x * a는, 두 번째 연산 x + b로 치환될 수 있다. b = x*k (k는 자연수) 이라면 a = k+1인 x * a 연산과 동일하다. 따라서 첫 번째 연산을 적당히 하고 n까지 두 번째 연산을 적용하면 된다. 여기서 첫 번째 연산을 할 때마다 x가 a씩 증가하므로, 최대 log_a(n) 번 연산한다. 두 번째 연산도 모듈러를 통해 O(1)에 가능하다. 최종적으로 O(log n)에 가능하다.

첫 번째 연산과 두 번째 연산이 서로 치환될 수 있지 않을까 하는 경험에 근거한 의심을 금방 떠올렸지만 예시 입력을 잘못 계산하면서 모든게 꼬여버렸다.

C. Strange Function (업솔빙)

f(x)의 값을 고정하고 x가 어떤 수여야 하는지 관찰해보면 다음과 같은 규칙을 찾을 수 있다.

• 어떤 x가 f(x) = 2이려면, 1의 배수이면서 2의 배수가 아니어야 한다. 즉, x | lcm(1) 이다.
• 어떤 x가 f(x) = 3이려면, 1의 배수이면서 2의 배수이면서 3의 배수가 아니어야 한다. 즉, x | lcm(1, 2) 이다.
• 어떤 x가 f(x) = 4이려면, 1의 배수이면서 2의 배수이면서 3의 배수이면서 4의 배수가 아니어야 한다. 즉, x | lcm(1, 2, 3) 이다.
• ...
• 어떤 x가 f(x) = k이려면, 1의 배수이면서 ... k-1의 배수이면서 k의 배수가 아니어야 한다. 즉, x | lcm(1, 2, ... , k-1) 이다.

따라서 n 이하의 수 중 f(x) = k인 수의 개수는 ⌊ n / lcm(1, ... , k-1) ⌋ 개이다.

한편, lcm(1, 2, ... , 37) > 1e16 이다. 따라서 37까지만 확인하면 된다.