12-22 Merry problem solving!

2018 merry problem solving!

12-22 : Day2

boj 슬랙에서 koosaga님이 진행하시는 2018년 연말 merry problem solving 스터디(앳코더 문제들 매일 목표 정해놓고 풀기)에서 푼 문제에 대한 정리글. 풀이는 내가 풀기 쉬웠던 문제부터 어려웠던 문제까지 순서대로 나열되어 있다.

APC 1A. Two Integers (100pts)

X와 Y가 주어진다. X의 배수면서 Y의 배수가 아닌 수가 있으면 아무거나 하나 출력하고, 아니면 -1을 출력하라.

풀이

만약 X를 Y로 나눈 나머지가 0이라면, X의 배수는 무조건 Y의 배수가 된다. 따라서 이런 경우는 -1을 출력하면 된다.

X를 Y로 나눈 나머지가 0이 아니라고 하자. 그러면 X는 X의 배수면서 Y의 배수가 아닌 수이다. 따라서 X를 출력하면 된다.

CODE FESTIVAL 2017 A. AKIBA (300pts)

문자열 S가 주어진다. 이 문자열 S의 원하는 위치에 문자 A를 몇 개든 끼워넣을 수 있다. 주어진 문자열을 AKIHABARA로 만들 수 있으면 Yes, 아니면 No를 출력하라.

풀이

'AKIHABARA' 문자열과 주어진 문자열을 비교하면서 현재 위치의 값이 서로 다른데 'AKIHABARA' 문자열의 현재 위치 값이 A면 그 위치에 A를 끼워넣으면 되므로 넘어간다. 그렇지 않은 경우 불가능하다. 제일 처음 위치부터 시작해서 이러한 과정을 반복해주면 쉽게 답을 구할 수 있다.

APC 1B. Two Arrays (300pts)

두 배열 A와 B가 주어진다. 이 때 아래의 연산 P를 원하는 만큼 수행할 수 있다.

P(i,j) : Ai에 2를 더하고, Bj에 1을 더한다.

이 때 연산 P를 이용해서 배열 A와 B를 완전히 동일하게 만들 수 있으면 Yes, 아니면 No를 출력

풀이

우선 주어진 연산은 항상 배열의 값을 증가시킨다. 따라서, 어떤 A[i]와 B[i]에 대해 A[i] < B[i]면 A[i]값이 B[i]와 같아질 때까지 P(i,x)를 수행해줘야 하고 A[i] > B[i]면 A[i]값이 B[i]와 같아질 때까지 P(x,i)를 수행해줘야만 한다.

이를 이용해서 A 배열에 반드시 수행해줘야만 하는 연산의 횟수와 B 배열에 반드시 수행해줘야만 하는 연산의 횟수를 각각 구해보자. 1~n-1번째 위치까지 이 값을 구하고 나면, 양쪽에 필요한 연산 횟수의 차이만큼은 n번째 위치에 반드시 수행해줘야 한다(각각 따로 구했지만 실제로는 동시에 일어나야하므로, 필요한 횟수만큼을 채워넣고 난 다음 나머지는 n번째 위치에 반드시 수행해줘야 하기 때문)

이렇게 수행한 후 n번째 위치의 A값이 n번째 위치의 B값 이하면 항상 가능하고, 아니면 불가능하다(마지막 위치에 수행해주면 한 번 수행할때마다 양 숫자의 차이가 1씩 줄어들기 때문에, A의 n번째 값이 B의 n번째 값 이하기만 하면 항상 두 값을 같게 만들어줄 수 있다).

CODE FESTIVAL 2016 FINAL B. Exactly N Points (300pts)

1~N번까지 N개의 문제가 있고, i번째 문제는 풀면 i점을 준다. 이 때 총 N점을 획득하고 싶은데, 내가 푼 문제의 점수 최댓값을 최소로 하고 싶다. 이 때 풀어야하는 문제 세트를 출력하라.

풀이

내가 풀 문제의 점수 최대를 h라고 하자. 일단 h점을 최댓값으로 두면 얻을 수 있는 최대 점수는 h*(h+1)/2인데, 이 때 1~h*(h+1)/2 사이의 모든 점수를 항상 생성 가능하다. 1~h점 사이는 각각 1번부터 h번까지 한 문제를 푸는 것으로, h+1 부터 h+(h-1)까지는 h번을 푼 다음 1~h-1번 문제중 하나를 푸는 것으로, h+(h-1)+1부터 h+(h-1)+(h-2)까지는 h, h-1번을 푼다음 1~h-2번중 하나를 푸는 것으로 ... 와 같이 순차적으로 만들어줄 수 있기 때문이다.

따라서 h*(h+1)/2가 n이상인 최소의 h를 구한 후 거기서 위에 적은 것과 같은 방식으로 풀 문제 세트를 역추적해주면 된다.

이분 탐색으로 h값을 찾으면 O(log(n))이고 처음부터 h를 올려가면서 찾으면 O(sqrt(n))인데 어차피 O(n)이라도 풀릴 범위기 때문에 아무 방법으로나 풀어도 전혀 상관이 없다.

CODE FESTIVAL 2017 B. Palindrome-phobia (400pts)

a,b,c로만 구성된 문자열이 있다. 이 문자열을 섞어서 길이 2이상인 모든 substring에 대해서 팰린드롬이 존재하지 않게 만들고 싶다. 가능하면 YES, 아니면 NO 출력.

풀이

일단 길이 2에서 서로 같은 문자가 연속하면 반드시 팰린드롬이 된다(aa,bb,cc 등). 따라서 문자열에 이러한 substring은 존재할 수 없다. 그러면 이제 ab, ac, ba, bc, ca, cb 등만 가능한데, 다시 여기에 한 글자를 붙이는 경우에 가능한 경우는 aba, abc, aca, acb, bab, bac, ... 등이 존재할텐데, 이 경우에 또 aba aca bab bcb ... 등은 길이 3짜리 팰린드롬이 되기 때문에 불가능하다. 

결국 각 길이 3짜리 substring을 생각해보면 항상 abc 세 개의 글자 순열로만 구성이 되어야 하고, 따라서 맨 처음 3글자가 결정되면 전체 문자열도 결정된다. 이 때 항상 길이 3개짜리로 잘랐을 때 모두가 순열이 되게 구성하려면 문자열에서 a의 개수,b의 개수, c의 개수 차이가 모두 1 이하여야 한다. 따라서 이 조건을 만족하면 yes, 아니면 no를 출력하면 된다.

ARC 93D. Grid components (500pts)

A와 B가 주어진다. 너비와 높이가 모두 100이하인 임의의 그리드를 검은색 흰색으로 색칠할 건데, 이 그리드에는 정확히 A개의 연결된 흰색 컴포넌트와 B개의 연결된 검은색 컴포넌트가 존재해야한다. 서로 같은 색깔인 칸만 상하좌우로 거쳐서 도달가능한 두 칸은 연결되어있다고 본다. 1 <= A, B <=500이고 이 때 조건 만족하는 그리드를 아무거나 그려서 출력하라.

풀이

몇달 전에 이 문제와 굉장히 유사한 코드포스 문제 를 못 풀어서 레이팅이 떡락한 적이 있었다. 그래서 이 문제는 굉장히 쉽게 풀었다. 일단 그리드는 크면 클 수록 쓸 수 있는 공간이 많아서 좋으므로 100 * 100 크기를 잡는다고 생각하자. 여기서 위쪽 50*100은 흰색, 아래쪽 50*100은 검은색으로 칠한다. 이러면 정확히 절반은 흰색 절반은 검은색이고 각각 연결된 컴포넌트가 하나씩 존재하는 상황이다.

여기서 흰색 컴포넌트를 늘리고 싶다면, 검은색으로 칠해진 절반에서 2칸씩 건너 뛰면서 흰색을 하나씩 색칠하면 검은 색 컴포넌트의 개수를 변화시키지 않은 채 흰색 컴포넌트의 개수만 하나씩 늘어난다. 반대도 마찬가지 방식으로 칠할 수 있다.

따라서 이와 같은 식으로 색칠하면 항상 쉽게 답을 구할 수 있다.

그림으로 표현하면 다음과 같은 모양이 된다.

위쪽 아래쪽 흰/ 검 컴포넌트는 각자 영향을 받지 않고 한 칸짜리 검은색, 흰색을 추가할 때마다 각각의 컴포넌트 개수는 늘어난다는 것을 알 수 있다.

CODE FESTIVAL 2016 FINAL C. Interpretation (400pts)

N명의 사람과 M개의 언어가 있다. 각 사람은 자기가 구사할 수 있는 언어 목록이 있다.

이 때, 서로 다른 두 사람 A,B는 다음 두 조건중 하나를 만족하면 서로 의사소통이 가능하다.

- A와 B가 서로 같은 언어 L을 구사할 수 있다.

- A와도 의사소통이 가능하고 B와도 의사소통이 가능한 어떤 사람 X가 있다.

N명의 사람들이 각각 구사할 수 있는 언어 목록이 주어졌을 때 모든 서로 다른 사람들이 의사소통이 가능한지 아닌지 판별하시오.

풀이

일단 같은 언어를 구사하는 사람끼리는 모두 의사소통이 가능하니, 각각의 언어 L에 대해 그 언어 L을 구사할 수 있는 사람들을 한 세트로 묶는다. 여기서 언어 L을 구사할 수 있는 어떤 사람 X에 대해, 이 X가 언어 L2를 구사할 수 있다면 언어 L을 구사하는 사람들과 언어 L2를 구사하는 사람들은 모두 X를 매개로 해서 서로 의사소통이 가능해진다. 이런 방식으로 전체 집합들을 합해나가서 모든 사람들이 하나의 집합에 존재하게 되면 Yes, 아니면 No이다.

이제 이걸 어떻게 구현하느냐가 문제인데, union-find를 이용하면 쉽게 구현할 수 있다. 단순히 각 언어에 대해 그 언어를 구사하는 세트를 모두 merge해주는 것을 반복해주기만 하면 결국 각 사람에 대해 그 사람이 속한 모든 집합들을 다 합집합 하는게 되기 때문이다.

ARC 087D. FT Robot (500pts)

2차원 평면의 원점에 로봇이 x축이 증가하는 방향을 바라보고 서 있다. 이 때 로봇은 다음 두 가지 명령에 따라 움직인다.

F : 바라보고 있는 방향으로 한칸 전진

T : 바라보고 있는 방향을 시계방향 혹은 반시계뱡향으로 90도 회전

이 때 명령 시퀀스와 좌표 (x,y)가 주어졌을 때, 주어진 명령 시퀀스를 이용해 로봇이 (x,y)에 도달할 수 있는지 판별하는 프로그램을 작성하라.

풀이

T 명령으로 인해 방향을 회전하게 되는 경우를 잘 생각해보자.

+x 방향을 바라보고 있을 때 : T로 회전하면 +y 방향을 보거나 -y 방향을 보게 된다.

 -x 방향을 바라보고 있을 때 : T로 회전하면 +y 방향을 보거나 -y 방향을 보게 된다.

+y 방향을 바라보고 있을 때 : T로 회전하면 +x 방향을 보거나 -x 방향을 보게 된다.

 -y 방향을 바라보고 있을 때 : T로 회전하면 +x 방향을 보거나 -x 방향을 보게 된다.

즉, x방향을 바라보고 있었다면 T로 회전시 항상 -y 혹은 +y(y축)을 바라보고 이동하게 되고, y방향을 바라보고 있었다면 x축을 바라보고 이동하게 된다. 이 때 +방향으로 이동할지 -방향으로 이동할지도 항상 선택할 수 있다.

그러면 주어진 문자열에서 연속된 F들을 x축 방향 이동인지 y축 방향 이동인지에 따라 분류할 수 있다. 이제 이렇게 분류된 F들을 +방향으로 이동할지 -방향으로 이동할지를 임의로 골라서 주어진 (x,y)에 도착이 가능하면 YES, 아니면 NO가 답이 된다. x축과 y축은 서로 독립적이기 때문에 별개로 계산하면 되고 각 축에 대해 가능한지 판별은 DP를 이용하면 O(N^2)에 쉽게 판별이 가능하다.

ARC 092D. Two Sequences (500pts)

크기 N짜리 배열 A와 B가 주어진다. N^2개의 모든 (Ai+Bj) 쌍을 XOR한 값을 출력하시오

풀이

Ai를 고정해놓고 생각해보자. 어떤 Ai 값에 대해 그 Ai와 더해서 k번째 비트가 1이 되는 경우는 무엇일까? 일단 k번째 비트에 k+1번째 비트 이상의 값은 전혀 영향을 끼치지 않으므로, 0번째 비트 ~ k번째 비트까지의 값만 고려해보자. 두 값이 모두 2^(k+1) - 1이하라고 가정하면 두 수의 합은 2^(k+2) - 2 이하고, 이 숫자 범위에서 k번째 비트가 1인 수 x의 범위는 2^k <= x < 2^(k-1)과 2^(k+1) + 2^k <= x 두 가지가 된다. 이 범위를 만족하는 수들의 개수는 B 배열이 정렬되어있다고 가정하면 이분 탐색을 이용해 O(logn)에 찾을 수 있다.

이 때 k+1번째 비트 위쪽을 무시하는게 까다롭게 느껴질 수 있는데, bit를 큰것부터 역순으로 순회하면서, A,B 배열의 값을 모두 2^(k+1)로 모듈러해준 나머지로 만든 다음 B배열을 정렬하고 거기서 이분탐색을 수행해주면 쉽게 계산할 수 있다.

이렇게 각 비트별로 그 비트가 1이 되는 덧셈 쌍의 개수를 구했으니 이제 그 개수가 홀수면 XOR한 정답에서 해당 비트는 1이 될것이고 아니면 0이 될 것이다. 이것만 다시 순회하면서 계산해주면 된다. 모든 수의 범위가 2^28보다 작다고 되어 있기 때문에 O(28 * n log n)에 해결된다.

ARC 089D. Checker (500pts)

양변의 길이가 K인 그리드를 위와 같은 방식으로 반복해서 이차원 평면에 채워넣는다.  이 때, N개의 요구 조건이 주어진다. 각 요구 조건은 (x,y,c)로 표현되고, (x,y) 칸의 색깔이 c였으면 좋겠다는 뜻이다. 이런 K사이즈 그리드 패턴으로 색칠을 할 때 주어진 요구 조건을 최대한 많이 만족시킬 경우 몇 개의 요구 조건을 만족시킬 수 있을까?

풀이

일단, 그리드 패턴은 2*K를 주기로 반복되므로 모든 좌표도 그 좌표를 2*k로 모듈러한 값으로 변형해서 생각할 수 있다. 이제 모든 좌표는 2k*2k 사이즈의 좌표 평면에 존재하고, 4개의 k*k 사이즈 검은색, 흰색 그리드 영역만이 남아있다. 이 때 패턴은 자유롭게 좌우로 밀어서 그릴 수 있는데, 생각하기 편하게 좌표를 그만큼 시프트해준다고 생각하자. 좌표 역시 2k 이상 시프트하면 다시 원래 위치로 돌아오므로 x축 y축 각각 2k만큼, (2k*2k) 만큼 시프트 가능한 경우의 수가 존재한다.

각각의 시프트에 대해서 요구 조건을 만족하는 횟수는 2차원 부분합 개념을 이용해 O(1)에 계산할 수 있다. 각 조건은 좌표 평면 상에 사각형 영역 내에 존재하는 점의 개수로 변형해서 생각할 수 있고, 흰색은 0, 검은색은 1이라고 생각하고 각 사각형 영역에 0 개수 1개수를 구하는 걸로 만족하는 요구 조건을 구하는 걸 계산 가능하기 때문이다. 따라서 O(N + K^2) 시간에 답을 구할 수 있다.