KimHwon

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

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까지만 확인하면 된다.

종강 후 오랜만에 버추얼을 돌았다.

A. Arithmetic Array

주어진 수열의 길이를 n, 합을 x라 하고, 새로 추가한 수들의 개수를 m, 그 합을 k라고 하면 아래와 같은 식으로 표현할 수 있다.

x - n이 0 이하이면, m=1로 하고 k가 x-n-m이면 성립한다.

x - n이 0 초과이면, k=0로 하고 (즉, 새로 추가할 모든 원소를 0으로 하고) m을 x-n이면 성립한다.

따라서 x - n이 0 이하일 때 1개, 0 초과일 때, x-n개 추가하면 항상 성립한다.

B. Bad Boy

이동 거리는 맨하탄 거리라고 할 수 있다. 따라서 경로와 무관하게 이동 거리는 가장 먼 두 점이다.

그림에서처럼 (0, 0)과 (N, M)으로 하면 이동 거리를 최대로 할 수 있다. 

C. Challenging Cliffs

일단 주어진 수열 h을 정렬한다. 첫 번째 조건인 |h_1 - h_n|이 최소가 되도록 하기 위해서, 수열을 순회하면서 인접한 원소끼리 차이가 가장 작은 원소 둘을 선택한다. 선택한 원소의 위치를 a, b라고 해보자.

두 번째로 h_i ≤ h_{i+1}인 위치가 최대한 많게 배치해보자. h_j, h_{j+1}, ... , h_n,   h_1, h_2, ... , h_i 순서로 한다면 h_n과 h_1 한 번을 제외한 나머지 모든 경우가 조건을 만족하므로 최대이다. 여기서 만약 길이가 2일 경우에는 h_j > h_i 일 수 있다. 이러한 경우도 고려해보면 h_i, h_{j+1}, ... , h_n,   h_1, h_2, ... , h_j 순서로 배치할 수 있다.

D. Deleting Divisors (업솔빙)

아직도 게임 쪽은 전혀 감이 없다. 해설을 보았으나 그만 정신이 혼미해졌다. dp로 100까지 돌려본 뒤, 규칙을 발견하였다. dp식은 다음과 같다. x의 약수 중, k != 0, k != x인 k에 대하여, dp[x][a] = !(dp[x - k_1][!a] && dp[x - k_2][!a] && ... && dp[x - k_n][!a])

n이 2의 홀수 제곱일 경우는 무조건 Bob이 승리, 그 외의 경우에는 홀수엔 Bob, 짝수엔 Alice가 승리한다.

E1. Erase and Extend (Easy Version)

사전 순 비교이므로 앞쪽의 문자가 무조건 우선이다. 따라서 두 번째 연산으로 복사해 나가기 전에, 일단 적절히 잘라내서 최적의 prefix를 만들어야 할 것이다.

길이가 1부터 n인 prefix를 만들고 복사해서 n개의 문자열들을 만든다. 입력이 충분히 작으므로, 이 문자열들을 전부 비교해보고 가장 작은 문자열을 찾아도 된다.

1+2라 생각보다 풀만 했다. 블루 수복 완료

A. Sum of 2050

문제에서 정의한 2050-number를 잘 관찰해 보면 a * 2050*10^b + c * 2050*10^d + ... 이고 여기서 2050을 묶어내면 2050 * (a*10^b + c*10^d + ...)이다. 즉, 2050에 임의의 자연수가 곱해진 모양이므로 주어진 수를 2050으로 나눠보면 된다.

B. Morning Jogging

체크포인트 사이 경로들의 최솟값을 관리해주면 된다. 일단 수열 b_i를 정렬하자. i번째 체크 포인트까지 잘 도착했다고 해보자. i+1번째 체크포인트에 가는 경로들 b_ij를 잘 배분해서 최소가 되게 만들어줘야 할 것이다. 현재까지 각 경로의 최솟값(i번째 체크포인트까지 왔을 때 각 runner의 tiredness)을 t_j라고 하면, t의 각 원소들을 가능한 최소로 만드는게 최적이다. 따라서 pair(t, j)를 내림차순으로 정렬하고, 가장 큰 t_j에 b_i+1중 가장 큰 원소를 매칭해주자. 이 과정을 2차원벡터 등에 잘 저장해서 trace해주면 된다.

C. Fillomino 2

주대각선에 있는 숫자만큼 계단 모양을 인접하게 색칠해야 한다. 일단 주대각선에 있는 숫자들이 permutation이고 합이 계단 모양에 있는 칸 수와 같으므로 다 칠할 수 있다고 합리적 의심을 해보자. 만약에 (i, i)에 있는 수로 (i-1, i-1)을 방해하려면 i-1줄 이상으로 올라가야 한다. 그런데 i+1줄까지 가장 많이 칠해진 경우는 N, N-1, N-2, ... 만큼 칠해진 경우일 것이며 i+1줄까지 계단 모양의 칸 수 또한 N, N-1, N-2, ... 으로 서로 같다. 즉, 항상 자신과 같은 줄이나 그 아래 줄만 사용해서 모두 색칠할 수 있다. 따라서 최대한 아래쪽으로 붙여서 칠해나가면 항상 색칠이 가능하다.

D. Explorer Space (업솔빙)

역시나 DP가 발목을 잡는다. 1시간반이나 붙잡고 있었는데 다익스트라를 사용한 풀이로 풀다가 망했다.
dichoy27의 풀이는 이러하다. 일단 갔다 와야되니까 K가 홀수일때는 항상 불가능하다. 그리고 오는 길 가는 길 똑같으니까 K/2번 가는 것만 생각하면 된다. dp[i][j][d] = (i, j)위치에서 d만큼 이동했을 때 최솟값이라 하면, dp[i][j][d] = min(dp[i][j][d], dp[i+dx[k]][j+dy[k]][d-1] + dist[i][j][k]). 즉, 직전 위치 (i+dx[k], j+dy[k])에서 상하좌우로 이동해 온 거리 dist[i][j][k]를 더한 값과 현재 값 중 최솟값을 계속 관리해준다.

역시 에듀는 마음이 편안하다. 하지만 그렇다고 엄청 잘 풀지는 못해서 블루 복구는 못했다.

A. Review Site

upvote하는 사람과 downvote하는 사람은 고정이고, 영화를 보지 않은 사람을 최대한 upvote쪽으로 몰아야 한다. 서버가 2개이므로, 한 서버 쪽으로 upvote하는 사람을 다 보내고 다른 서버 쪽으로는 downvote하는 사람을 다 보내버리자. 그리고 영화를 보지 않은 사람을 upvote만 있는 서버로 보내면, 전부 upvote를 하게 된다.

B. GCD Length

gcd(x, y)를 g, x/g = x', y/g = y'이라고 하자. x', y', g가 모두 소수라면 다른 예외사항 없이 항상 조건을 만족한다. 따라서 g를 c자리 소수, x'을 a-c+1자리 소수, y'을 b-c+1자리 소수로 정한다. 이 때, 곱셈을 해서 자리올림이 생기면 안되므로 가장 작은 소수로 정해야 할 것이다. 1~9자리 가장 작은 소수는 울프람알파로 찾아서 하드코딩하고, x'과 y'이 같으면 gcd가 달라질 수 있으므로 x'을 가장 작은 소수, y'을 두번째로 작은 소수로 정한다.

C. Yet Another Card Deck

같은 숫자가 여러 개 있어도, 가장 위에 있는 숫자만 움직이므로 인덱스만 저장해두고 좌표압축으로 줄여줄 수 있다. 압축한 수열을 b라고 하면 adj[i]를 b_i 앞에 있는 원소라고 정의해보자.

만약에 쿼리가 3이 들어왔다면, 저장해 두었던 3의 (압축하기 전) 인덱스를 출력한다. 그리고 맨 앞으로 옮겨야 하는데, 인접 리스트로 모델링하면 손쉽게 핸들링할 수 있다. 그림에서처럼 3의 앞에 있는 원소는 adj[3]의 멤버들(초록)이다. 이들 뒤에 있던 3이 앞으로 이동했으므로, 각 멤버들의 인덱스를 +1 하고, adj[]도 업데이트해준다.(파랑)  각 쿼리에 대해 같은 방식으로 계속 진행해 나가면 된다.

D. Min Cost String

인접한 두 문자 한 쌍을 한 요소로 생각해보자. 이 한 쌍을 간선으로 모델링해보면 다음과 같다.

세 개의 문자가 있을 때 나올 수 있는 모든 요소들은 aa, ab, ac, ba, bb, bc, ca, cb, cc로 총 9가지이다. 이들을 간선으로 만들면 루프+완전그래프 형태가 된다.(파랑)  따라서 문제를 재해석하면 루프+완전그래프에서 가능한 같은 간선을 지나지 않으면서 순회하는 방법을 찾는 문제가 된다. 각 정점마다 짝수개의 간선이 추가되므로 이 그래프는 무조건 한붓그리기가 가능하고, 오일러 경로가 답이 된다. dfs등으로 오일러 경로를 따라가면서 문자열을 만들고 조건에 맞는 길이만큼 출력하면 된다. 문자열보다 더 긴 길이가 필요하면, 문자열을 한 번 순회하는 것을 한 사이클로 생각하고 여러 번 순회하면 된다.

아이디어는 금방 떠올랐으나 오일러 경로를 순회하는 방법을 몰라서 복잡하게 구현했는데, Hierholzer's Algorithm이라는 dfs 비스무리한 아주 웰노운한 방법이 있다고 한다.

E. Colorings and Dominoes (업솔빙)

Green55의 해설을 듣고서야 이해했다. 풀이는 다음과 같다. 먼저 어떤 연속된 두 블록을 딱 고정해놓고 생각해보자. 세로로 두 칸을 고정했다면 파란색으로 칠하고 1점을 얻는게 확정이고, 나머지 칸은 상관이 없다. 따라서 모든 경우의 수에서 저 두칸에서 얻을 수 있는 점수는 2^(남은 o의 개수)이다. 당연히 서로 겹치는 사건이 존재하는데, 여기서 "가로 두 블록을 R로 고정했음"이라는 사건과 "세로 두 블록을 B로 고정했음"은 겹치지 않으므로 서로 독립적이다. 왜냐하면 어떤 한 칸이 가로 두 블록을 채우면서 세로 두 블록을 채울 수는 없기 때문이다. 그러면 결국 겹치는 사건들은, 연속되게 존재하는 칸에서만 발생한다는 것을 알 수 있다. 그럼 결국 우리가 궁금한 것은 "n칸이 연속되게 존재할 때, 이 칸에서 얻을 수 있는 점수의 합"이 된다. 백트래킹으로 완전탐색을 짜서 돌린 후 oeis에 치면 예쁜 점화식이 나오니까 가져다 쓰자. 찾은 점화식을 f(n)이라 하면, 결과적으로 답은 f( (연속된 o의 갯수) - 1 ) * 2^( (o의 총 갯수) - (연속된 o의 갯수) ) 의 합이 된다.

애초에 겹치는 사건 분류를 못해서 풀진 못했지만, oeis를 활용한 답이라니 정신이 혼미해진다. 에디토리얼 뜨기 전에 댓글들을 살펴보니 다들 oeis로 풀은 것 같았다. 에디토리얼의 정해는 마찬가지로 완전탐색 돌린 후, 규칙을 잘 찾으란건데... 확률이 1/4, 1/4 - 1/8, 1/4 - 1/8 + 1/16, 1/4 - 1/8 + 1/16 - 1/32, ... 이런 형태로 나타난다고 한다.

업솔빙 도중에 오버플로우가 안잡혀서 여러 번 틀렸는데, 템플릿을 구해서 사용했더니 바로 AC 받았다.

어려웠고 결과적으로 망했다. 역시 외부 연계 라운드는 무섭다. 민트로 똑떨함

A. Array and Peaks

일단 가능한 많은 peak이 존재하려면 peak 좌우에 더 작은 값들이 위치해야 한다. 그러면 한칸 걸러 한칸씩 peak이 등장하는 상태가 최대이고, 따라서 최대 floor( (N-1)/2 )개의 peak이 존재할 수 있다. 반대로 가장 적게 peak이 존재하는 경우는, 정렬된 상태면 하나도 없는 상태가 된다. 주어진 peak 갯수만큼, 최대로 만드는 전략으로 채운다. 빈 자리들에 오름차순으로 남은 수들을 채워 넣으면 된다.

B. AND Sequences

제일 극단적인 케이스를 생각해보면 a1 = a2 & ... & an 또는 a1 & ... & an-1 = an 일 것이다. 그런데 and 연산을 잘 생각해보면 비트가 꺼질 수는 있어도 켜질 수는 없다. 즉, a1 = a2 & ... & an 이면서 a1 & ... & an-1 = an를 만족하려면 a2 & ... an-1을 a1 또는 an과 and 연산 했을때, a1이나 an의 비트를 꺼서는 안된다. 따라서 a1 = an이 만족하고, a1 = an = a1 & ... & an-1 = a2 & ... & an 이다. a1 & ... & an-1 = a2 & ... & an 이면 a1 & ... & an = a1 & ... & an-1 = a2 & ... & an 이다.
여기까지 관찰을 하고, 구현을 하면 된다. a1 & ... & an을 구하고, 각 원소의 등장 횟수를 센다. a1과 an을 고정하고 a2~an-1에 잘 채워 넣는다고 생각해보면, a1과 an에 하나씩 원소를 배정해보면서 구할 수 있다. 어떤 원소가 2개 이상이면서 a1 & ... & an와 같으면 (즉, a1 = an = a1 & ... & an-1 = a2 & ... & an) 조건에 일치한다. 이 상태의 경우의 수는 (cnt)P(2) * (N-2)! 이다. 페르마 소정리 등을 사용해 경우의 수를 잘 계산하면 된다.

분명 B번인데 뭔가 잘못돼가고 있다는 느낌이 들었다... 체감은 한 C번인데 그냥 A번 풀지 말고 탈주할까 싶었다.

C. Add One (업솔빙)

각 숫자들이 변하는 형태는 독립적이므로, 따로 떼어놓고 생각해도 된다. 또한 어떤 숫자 'k'는 '0'이 k번 연산을 한 후와 동치이므로, 0으로 시작할 때의 규칙만 찾으면 된다. 완전탐색 코드를 짜보면 증가량이 이항계수 모양으로 나타난다... 까지 관찰을 하고 못풀었다.
Green55의 풀이는 다음과 같다. 여기서 '0'은 10번 연산을 하면 '1' 과 '0'으로 쪼개지니까 ('0'이 m초 지난 자릿수) = ('1'이 m-10초 지난 후 자릿수) + ('0'이 m-10초 지난 후 자릿수) 이다. ('1'이 m-10초 지난 후 자릿수) 는 위에서 말했다시피 ('0'이 m-9초 지난 후 자릿수) 이다. 그러면 ('0'이 m초 지난 자릿수) = ('0'이 m-9초 지난 후 자릿수) + ('0'이 m-10초 지난 후 자릿수). 이를 dp식으로 표현하면 dp[m] = dp[m-9] + dp[m-10]이다. 그에 더해, naive한 수열이 이항계수 비스무리한 형태면, 점화식이 선형일 확률이 매우 높으므로 벌래캠프로 해결할 수 있다.

대충 규칙이 있을거라곤 생각했지만, DP를 확실히 못하긴 한다. 연습 좀 더 해야겠다.