cdjs의 코딩 공부방

드디어 염원하던 블루 재등반 성공!!

어차피 다음 div2 풀면서 다시 떨굴 것 같긴 한데, 그래도 오프라인 개학 전까지 블루 재등반이라는 목표를 달성해서 신난다.

이번 난이도는 뭔가 Div3치고는 조금 어려웠던 느낌이었다. A번부터 뭔가 Div3답지 않았던거 같기도 하고...

저 B는 YES도 출력해야 되는지 모르고 왜 안되는지 낑낑대다가 C 풀고 나서야 알아챘다;;; 저것만 바로 풀었어도 +130도 가능했을텐데;

아무튼, 풀이나 하겠다.

https://codeforces.com/contest/1343/problem/A

A. Candies

Vova는 사탕을 매일마다 구매하며, 첫날에는 x개, 둘째날에는 2x개, 셋째날에는 4x개, ... k째날에는 2^(k-1)x개의 사탕을 구매한다.

이 때, 구매한 사탕 개수 n이 주어졌을 때, k>1 (k>=2)을 만족하는 x를 구하는 문제이다.

k는 2 이상인 아무 정수나 상관이 없으니까, k=2인 경우, k=3인 경우 ... 로 나누어서 생각해 보자.

k=2인 경우, 구매한 사탕은 x+2x = 3x이므로 n이 3의 배수인 경우, x=n/3이 된다.

k=3인 경우, 구매한 사탕은 x+2x+4x = 7x이므로 n이 7의 배수인 경우, x=n/7이 된다.

계속 이런 식으로 x의 계수를 늘려주면서, n%(x의 계수)==0인 경우 x = n/(x의 계수)를 출력해 주면 된다.

또한, 무조건 입력 n은 가능한 것으로 나오고, 2^31이 넘어가는 수치는 입력으로 들어오지 않으니, 반복문은 최대 31번까지만 돌리면 된다.

등비급수를 활용하여 2^n-1으로 식을 세워도 좋고, 그냥 계속 더해줘도 좋다. 어차피 뭘 선택하든 TLE는 안뜬다.

https://codeforces.com/contest/1343/problem/B

B. Balanced Array

사실상 A보다 쉬웠고, 그만큼 A보다 풀이자도 많았던 문제.

우선, n은 모두 짝수로 주어지며, n개의 배열 중 앞부분 n/2는 짝수, 뒷부분 n/2는 홀수이면서 앞부분과 뒷부분의 합이 동일한 원소 n개의 배열을 아무거나 출력해 주면 된다.

우선, n%4!=0인 경우에는, 자명하게 원소 n개의 배열을 만들 수 없다.

n이 4의 배수가 아니면, 앞부분의 원소와 뒷부분의 원소의 개수가 홀수가 되는데,

짝수+짝수+짝수=짝수, 홀수+홀수+홀수=홀수이므로 앞과 뒤의 합이 같을 수 없기 때문이다.

그렇다면 n%4==0인 경우에 어떻게 해주면 배열을 맞출 수 있을까?

여러 가지 방법들이 있겠지만, 본인은 그냥 가장 간단한 방법으로 풀었다.

예제에서 4 -> 2 4 1 5로 주어진 것을 활용해서,

n%4==0인 n이 주어졌을 때, 출력을 2, 4, 2+6*1, 4+6*1, 2+6*2, 4+6*2, .... , 1, 5, 1+6*1, 5+6*1, ...로 내게 했다.

즉, n==8인 경우에는 2 4 8 10 1 5 7 11이 나오고,

n==12인 경우에는 2 4 8 10 14 16 1 5 7 11 13 17이 나오고, ... 로 반복되는 것이다.

어차피 이렇게 하면 n이 4씩 더해질때 마다 앞부분과 뒷부분에 더해지는 값이 같이 때문에 무조건 앞부분과 뒷부분의 합이 같게 되고,

n<=200000인데 출력할 원소는 10^9보다 작기만 하면 되므로 출력 범위를 넘어설 일도 없다.

https://codeforces.com/contest/1343/problem/C

D번보다 훨씬 풀기 쉬웠던 문제.

배열 하나가 주어지고, 해당 배열의 부분배열 중 양수와 음수가 번갈아 나오는 최대 길이의 부분배열의 합의 최대를 구하는 문제이다.

문제를 좀 축약시키느라 말이 어려워 보이는데, 풀이는 그냥 간단하다.

우선 생각해야 할 점은, 배열 처음부터 끝까지 부호가 동일한 구간의 모든 원소를 하나씩은 모두 가져와야 한다.

그렇지 않으면 부분배열의 길이가 최대가 되지 않기 때문이다.

그리고, 그 배열의 합의 최대를 구하기 위해서는, 각 구간에서 가장 큰 수를 찾아서 ans에 더해주면, 해당 값이 정답이 된다.

이를 대충 알고리즘을 설명하면 다음과 같다.

1.배열 첫번째부터 시작해서, a[i]와 a[i+1]의 부호가 같은지 다른지 먼저 체크를 해 준다.

2-1.만약 부호가 같다면, maxnum값을 max(maxnum, a[i])로 갱신만 해 주고 넘기면 되고,

2-2.부호가 다르다면, maxnum값을 갱신해 준 뒤 -1234567890으로 초기화 해 준뒤, ans에 maxnum을 더해주면 된다.

그냥 이렇게 진행하는 코드를 구현하기만 하면 되는 문제였다.

팁으로, 앞부분과 뒷부분의 부호가 다른지 확인하기 위해서는 간단하게 (lld)(a[i]*a[i+1])<0을 체크해 주면 된다.

저런 식으로 체크할 때 주의해야 할 점은 a의 범위를 잘 생각하고, long long을 사용해야 한다는 것이다.

또한, -1 10^9 -1 10^9 .... 처럼 배열이 주어지면 ans값이 int 자료형을 넘길 수 있다는 것도 생각해 주어야 한다.

아마도 이 문제를 틀린 사람들은 자료형이 넘어가는 것을 체크를 안해줬거나, 구현 실력 미숙이 아닐까 하고 생각한다.

https://codeforces.com/contest/1343/problem/D

D. Constant Palindrome Sum

이번 contest에서 점수 떡상이냐 떡락이냐를 결정지었던 문제였다.

다행히 머리속에 풀이가 잘 떠올라 주어서 풀 수 있었지만, 못풀었다면 정말 슬플 뻔 했다.

배열의 길이 n과 k가 주어진다. 이 때 n은 짝수로만 주어진다.

그 다음에 길이가 n인 배열이 주어지는데, 이 배열의 원소들은 k보다 작거나 같다.

이 때 a[i]+a[n-i+1]의 값이 모두 같도록 배열을 바꿔주는 것이 목표이다.

(여기서 a[i]+a[n-i+1]는 그냥 팰린드롬 형식으로 1번째와 n번째, 2번째와 n-1번째... 의 합을 의미한다.)

이 때, 배열의 원소를 바꿀 때는 한번에 하나의 원소만을 바꿀 수 있고, 배열의 원소의 크기는 최대 k이다.

이 때 배열의 원소를 바꾸는 횟수의 최소값은 얼마인지를 구하는 문제였다.

우선, 한 팰린드롬 쌍(편의상 그냥 이렇게 부르겠다.)의 합을 다른 수로 바꾸기 위해선 최소 1번, 최대 2번의 변환이 필요하다.

가령 팰린드롬 쌍이 (1, 1)로 주어진 경우, 합을 k로 바꾸기 위해선 (1,k-1)로 한번, 2k로 바꾸기 위해선 (k,k)로 두 번 바꾸어 주어야 한다.

우선 가장 간단하게 생각할 만한 풀이는, 모든 팰린드롬 쌍의 합을 (k+1)로 바꾸어 주는 것이다.

한 쌍의 숫자 두개가 어떻게 주어지든, 두 숫자 중 단 한 번의 변환을 통해 해당 쌍의 합을 k+1로 만들어 줄 수 있기 때문이다.

(참고로, k+1은 쌍의 숫자로 k,k가 주어지든지, 1,1이 주어지든지에 상관없이 무조건 만들 수 있는 유일한 숫자이다.)

그렇다면, 우리는 정답은 무조건 n/2보다 작거나 같을 것이라는 것을 알 수 있다.

이제 들어오는 팰린드롬 쌍의 경우의 수를 생각해 보자.

만약 모든 팰린드롬 쌍의 합이 모두 다른 경우, 답을 어떻게 도출하면 될까?

이럴 경우엔 모든 팰린드롬 쌍의 합을 k+1로 바꾸는 경우(ans=n/2)와,

모든 팰린드롬 쌍의 합을 특정한 팰린드롬 쌍의 합으로 바꾸는 경우로 나누어 진다.

이 때, 후자가 답이 되기 위해서는 그 특정한 팰린드롬 쌍을 제외한 모든 팰린드롬 쌍에서 단 하나만의 원소를 바꾸어 주어야 하고, 이 때 정답은 n/2-1이 된다.

그렇다면 팰린드롬 쌍의 합들 중 중복하는 경우가 있다면 어떨까?

만약 모든 팰린드롬 쌍의 합을 가장 많이 중복된 팰린드롬 쌍의 합으로 바꾸는 경우를 생각해볼 수 있다.

하지만, 이렇게 했을 경우에도 답이 되기 위해선 한 쌍의 수 두개를 모두 바꾸는 경우가 중복된 팰린드롬 쌍보다 적어져야 한다.

즉, 이 문제에서 중요한 것은 "어떤 팰린드롬 쌍의 합을 특정한 수로 바꾸어 주기 위한 최소 연산 횟수"인 셈이다.

그렇다면 가장 처음 생각해 볼 만한 풀이는 이렇다.

우선, 모든 팰린드롬 쌍의 합을 찾는다.

그리고 나서, 각각의 팰린드롬 쌍의 합에 대하여, 모든 팰린드롬 쌍을 돌면서 해야 할 최소 변환 횟수를 계산한 뒤, 그 중 최소를 찾는다.

마지막으로, 그 최소값과 2/n값 중 작은 값을 정답으로 택한다.

하지만, 문제를 보면 알겠지만 팰린드롬 쌍은 최대 10만개까지 주어지고, 위 풀이는 O(n^2)이므로 시간 제한을 넘어가게 된다.

그래서 내가 생각한 풀이는, 다음과 같다.

우선 모든 팰린드롬 쌍을 돌며, 해당 팰린드롬 쌍의 합과 한 번 변환 시의 합의 최소 / 최대값을 구한다.

가령, 팰린드롬 쌍이 (3, 4)이고 k=7인 경우, 합 = 7, 합의 최소값은 (3,1)로 변환했을 경우의 4, 최대값은 (7,4)로 변환했을 경우의 11이다.

이렇게 주어진다면, 변환해야 할 합이 4이상 11이하이면 한번의 변환으로 맞출 수 있다는 뜻이고, 그렇지 않다면 두번의 변환을 거쳐야 한다는 것을 쉽게 알 수 있다.

그리고 이 최소값, 최대값을 저장해 준다.

본인같은 경우엔, map<int, int>에 key값으로 최소/최대값을 저장하고, value값으로는 최소일 경우 1, 최대일 경우 -1을 저장했다.

그리고 나서, 각각의 최소/최대 쌍에 대해, 다음과 같은 연산을 해 준다.

1. 오름차순으로 정렬된 팰린드롬 쌍의 합의 첫번째 원소를 골라서 저장한다.

2. sum+=map[key]로 sum을 구해 준다. (이 때, sum은 한번의 변환으로 해당 팰린드롬 쌍의 합을 만들 수 있는 쌍의 개수이다.)

3. 만약 현재 고른 팰린드롬 쌍의 합이 현재 key값보다 작다면, ans값을 갱신해 준다.

4. 반복이 끝나면, ans = min(ans, 2/n)으로 최종 답을 구해준다.

이 때, ans값은 다음과 같이 계산이 된다 :

ans = min(ans, sum - (해당 합을 만드는 쌍의 개수) + (n/2-sum)*2);

이렇게 해 주면, 훨씬 빠르게 ans값을 찾을 수 있다.

사실 본인이 코딩 실력이 좀 딸려서 비 효율적인 자료구조와 방법을 택했을지도 모르지만, 아무튼 뭐 풀렸으니 됐다 ^^

다른 사람의 코드를 보니 우선순위 큐를 사용할 수도 있고, 다양한 방법들이 있는 것 같다.

E,F는 그냥 읽자마자 "이건 내가 아직은 못푸는 문제다"라고 생각하고 때려쳤기 때문에 못풀었다.

언젠가 트리와 그래프 공부를 더 한 뒤에 풀어봐야겠다 ㅎㅎ

망 했 다!

B까지는 A한번 실수로 틀린거 빼면 기분좋게 10분컷 냈는데, C 보자마자 머리가 하얘져버렸다..

대략 1시간정도 C 잡고 있다가 때려치고 hack이나 하러 갔었는데, 조금만 더 했으면 C,D 둘다 풀 수 있었을텐데 하는 아쉬움이 남아 있다.

다음 Div3 대회가 곧 있으니까 그거 하려고 일부러 블루 안간거임 ㅎㅎ 아무튼 그런거임 ㅠㅠ

아무튼 간단하게 풀이나 해보겠다.

https://codeforces.com/contest/1337/problem/A

A. Ichihime and Triangle

a,b,c,d를 입력받고, a<=x<=b<=y<=c<=z<=d를 만족하고 각각 x,y,z를 변의 길이로 하는 삼각형이 존재하도록 x,y,z를 출력하는 문제였다.

이 문제는 사실 삼각형의 존재 조건(중학수학)만 알면 쉽게 풀린다.

가장 긴 변의 길이가 다른 두 변의 길이보다 작아야 한다는 조건 말이다.

그런데, 이걸 어떻게 x,y,z에 적용할까?

물론 여러 가지 방법이 있을 수 있지만, 가장 확실하고 적절한 방법은 가장 긴 변을 두개를 만드는 것이다.

가장 긴 변의 개수가 두개라면 무조건 삼각형이 만들어지기 때문이다. (1, 100, 100으로도 삼각형이 만들어진다.)

그러면 이제 문제풀이는 끝났다. y<=c<=z이므로, y==z==c로 놓는다면 x는 a<=x<=b를 만족하는 어떤 수를 고르더라도 x,y,z로 무조건 삼각형이 만들어진다.

즉, 간단하게 a,c,c 또는 b,c,c를 출력하면 정답이다.

https://codeforces.com/contest/1337/problem/B

B. Kana and Dragon Quest game

적 몬스터의 체력 h가 주어지고, Void Absorption 스킬의 사용횟수 n, Lightning Strike 스킬의 사용횟수 m이 주어진다.

이 때, 최대 n,m번 스킬을 사용하여 적 몬스터를 죽일 수 있는지 (h<=0으로 만들 수 있는지) 여부를 출력하는 문제이다.

Void Absorption 스킬은 적 체력을 반으로 깎고, 10을 회복시켜준다. (h = h/2 + 10)

Lightning Strike 스킬은 적 체력을 10만큼 깎는다. (h = h - 10)

우선, 어떤 순서로 스킬을 사용해야 최적의 스킬 사용일지를 생각해 보아야 한다.

체력을 반으로 줄이는 것은 상대방의 체력이 높을수록 효과적이므로, 적의 체력을 반으로 줄이는 것은 최대한 먼저 실행해야 한다.

두 번째로 생각할 점은, Void Absorption 스킬은 적의 체력을 회복시켜 줄 수도 있다는 것이다.

그렇다면 어떤 경우에 Void Absorption 스킬로 적 체력이 회복될까?

간단한 식으로 보자면, h < h/2 + 10, h/2 < 10, h < 20 즉 체력이 20 미만인 경우 Void Absorption 스킬을 사용하게 되면 적의 체력을 회복시킬 수도 있다는 것이다.

그리고 결국 적의 체력을 최대한 줄이는 것이 중요하므로, 적의 체력을 회복시키는 것은 결코 최적의 움직임이 될 수 없으므로, h<20인 경우에는 Void Absorption 스킬을 사용하면 안된다.

정리하자면, h>20인 경우에는 Void Absorption 스킬을 최대한 많이 사용하고, 그 뒤에 Lightning Strike 스킬을 최대한 많이 사용해 주면 된다.

코드로 나타낼 때는, 다음과 같이 나타내면 된다.

while (h>20 && n>0) h = h/2 + 10, n--;

if (h - m*10 <=0) printf("YES");

else printf("NO");

여담으로, 이 문제를 hack을 해보려고 여러 코드를 살펴봤는데, 문제가 워낙에 간단해서 hack을 하기가 힘들었다.

실제로, "먼저 n번 나누고 그 후에 m번 뺀 값"과 "먼저 m번 뺀 값" 중 하나만 0 이하이면 정답이라는 코드도 pass하게 되니..

https://codeforces.com/contest/1337/problem/C

C. Linova and Kingdom

위 결과에서 보면 알겠지만, 대회 시간 안에 못풀었다.. ㅠㅠ

풀만했던 문제였는데 트리를 다루는게 아직 미숙해서 못푼 것 같다. 앞으로 좀 더 연습해야겠다 

아무튼 풀이를 해 보도록 하겠다. (대회 끝나고 바로 다음날 일어나서 풀었다)

간단하게만 문제 설명을 해 보자면,

n개의 도시와 n-1개의 도로가 주어지고, 모든 "산업 도시"에서 수도로 사람이 올 때, 각각의 사람이 지나가는 "관광 도시"의 개수의 합의 최대값을 구해야 한다.

이 때, 산업 도시는 k개이고 나머지 모든 도시 (즉, n-k개의 도시)는 관광 도시이다.

사실 풀이는 설명만 들어보면 무척 간단하다.

일단, 1번 도시가 최종 목적지이므로 1번 노드가 루트인 트리를 만들어 준다.

일단 처음엔 간단하게, 단 하나의 산업 도시만을 고른다고 생각해 보자.

그럴 경우, 어떤 도시를 산업 도시로 골라야 할까?

그렇다. 1번 도시로 가는 길이 가장 긴 도시를 고르면 된다.

즉, 부모 노드의 개수가 가장 많은 노드들을 고르면 된다는 뜻이다.

위 예시에서는, 5, 6, 7중 하나만 고르면 될 것이다.

그리고 그렇게 산업 도시를 3개까지 고르면 5, 6, 7을 고르면 될 것이다.

그러나 4번째 산업 도시를 고를 때, 고려해야 하는 것이 하나 더 있다는 것을 알게 된다.

만약 3번 도시를 고르게 되면, 이미 골랐던 5번, 6번 도시에서 1번 도시로 가는 데 만나는 관광 도시의 개수가 하나 줄어들어 버리기 때문이다.

그리고, 어떤 노드를 고르게 되면 최대로 얻을 수 있는 점수는 해당 노드의 자식 수 만큼 줄어들게 된다.

(즉, 3번 노드를 고르게 되면 자식 노드의 개수인 2만큼 최대 점수가 줄어들게 된다.)

반면에 2번 도시를 산업 도시로 고르게 되면, 2번 노드는 자식 노드가 없으므로, 가장 최적의 상태가 완성된다.

또한, 어떤 노드의 자식 노드가 산업 도시가 아니라면, 해당 노드를 고르는 대신 무조건 자식 노드를 골라야 최적의 점수를 얻을 수 있다.

(조금 더 쉽게 말하면, 우리는 무조건 산업 도시를 리프 노드 근처부터 시작해서 천천히 루트 노드에 가까운 쪽으로 골라야 한다는 것이다.)

이는 자명한데, 만약 어떤 산업 도시의 자식 노드가 관광 도시라면, 해당 도시의 자식 노드를 산업 노드로 만들면 1점 더 높은 점수를 얻을 수 있기 때문이다.

따라서, 우리는 그리디하게 (부모 노드 개수 - 자식 노드 개수) 가 가장 큰 도시부터 하나씩 골라가면 된다.

이제 어떻게 해야할지는 알았으니, 이를 구현하면 된다.

우선, DFS를 사용하여 각각 노드의 부모 노드 개수와 자식 노드 개수를 구한다.

그런 뒤, (부모 노드 개수 - 자식 노드 개수)를 한 배열을 내림차순으로 정렬하여 앞에서부터 k개를 더하면, 그게 정답이다.

//여기서부턴 여담임 ㅎ

사실 대회 시간에 풀 때, 여러 문제점들이 있었다.

우선, 가장 처음 생각한 풀이는 그냥 부모 노드의 개수만을 생각한 풀이였다.

사실 그래서 그냥 나한테 조금 더 익숙한 BFS 방식으로 훑으면서 부모 개수를 채웠다.

그러고 나서 봤더니, 자식 노드에도 신경을 써야한다는 사실을 그제서야 깨닫게 되었고, 뇌절이 시작되었다;;

일단 "그리디하게 짜면 안되지 않을까?" 라는 생각으로 고민을 엄청 했었다.

그리고, "우선 리프 노드를 고른 뒤 해당 노드의 모든 부모 노드를 돌면서 점수를 1씩 깎자"라는 매우 비효율적인 생각을 하게 되었고,

당연히 n<=100000인 조건 안에서는 TLE가 뜰 것이 분명했기에, 문제를 던지기에 이르렀다.

차라리 그냥 처음부터 DFS로 짰으면 더 쉽게 풀었을 것도 같은데, 아쉽다.. ㅠ

https://codeforces.com/contest/1337/problem/D

D. Xenia and Colorful Gems

솔직히, 얘가 C보다 훨씬 쉬웠던 것 같다.

사실 대회 시간엔 얘를 볼 생각을 딱히 못했는데, 대회 다음날 금방 답이 나와서 허탈했다...

다음부터 뇌절오면 그냥 다음 문제로 거르는 습관을 들여야 되는건가? 싶기도 하다..

아무튼! 풀이나 하도록 하자.

우선 red, green, blue 각각의 색깔의 보석의 개수 nr, ng, nb가 주어진다.

그리고 나서, 각각의 보석의 크기가 순서대로 nr, ng, nb개씩 주어진다.

각 색의 보석을 하나씩 고른 것을 순서대로 x, y, z라고 할 때, (x-y)² + (y-z)² + (z-x)²의 최소값을 구하는 문제이다.

(아래에서는 편의상 그냥 위 연산을 '거리'라고 하도록 하겠다.)

일단 r, g, b 배열을 오름차순으로 정렬을 해 놓고, ans를 r[0], g[0], b[0]의 거리로 놓는다.

그 뒤 r[1], g[0], b[0]의 거리, r[0], g[1], b[0]의 거리, r[0], g[0], b[1]의 거리 중 가장 작은 놈을 찾고, ans를 ans와 해당 값중 작은 값으로 바꿔주고, 가장 작았던 색의 index값을 1 올려서 위를 반복한다.

즉, 가장 거리가 작은 경우를 그리디하게 하나씩 골라주면서 진행하는 것이다.

말이 좀 어려운데, 그냥 대충 예시를 하나 들어서 설명을 하는게 나을 것 같다.

입력은 input case 1의 예시와 동일한,

2 2 3

7 8

6 3

3 1 4

로 하도록 하겠다.

우선 각각을 오름차순 정렬을 해 준다.

r : 7 8

g : 3 6

b : 1 3 4

그 뒤, ans = (7-3)^2 + (3-1)^2 + (1-7)^2 = 16 + 4 + 36 = 56으로 설정해 두자.

r[1], g[0], b[0] : (8-3)^2 + (3-1)^2 + (1-8)^2 = 25 + 4 + 49 = 78

r[0], g[1], b[0] : (7-6)^2 + (6-1)^2 + (1-7)^2 = 1 + 25 + 36 = 62

r[0], g[0], b[1] : (7-3)^2 + (3-3)^2 + (3-7)^2 = 16 + 0 + 16 = 32

그러므로, ans = min(ans, 32) = 32가 되고, b의 index를 1 올려준다.

다음 단계로 넘어가 보면,

r[1], g[0], b[1] : ...

r[0], g[1], b[1] : ...

r[0], g[0], b[2] : ...

이런 식으로 계속 진행하다 보면, 결국 nr+ng+nb번 반복 후에는 끝나게 된다.

그리고, 그렇게 나온 ans의 값이 최적의 해가 된다.

그런데, 어째서 이렇게 하면 정답이 도출될까? 저 알고리즘의 반례가 없을까?

오랜만에 그림판을 켜서 그림을 그려서 설명해 보도록 하겠다.

보석의 크기를 위치로 변환해서 그린 수직선이다.

위 그림을 보면 어느 정도 직관적으로 이해가 되지 않는가?

약간의 부연설명을 해 보도록 하겠다.
우리의 목적은, 저 중에서 각각의 색의 점 하나씩을 골라 가장 거리가 가까운 조합을 찾아야 하는 것이다.

알고리즘을 진행시키다 보면, 조금씩 더 점들이 밀집하게 된다.

그리고 임계점을 넘어가게 되면, 즉 더 이상 현재까지 구한 최적해보다 최적의 값을 찾을 수 없다면, ans값은 다시 조금 커진다.

그리고 나서 다시 ans를 최적에 맞게 줄이고, 어느 순간 또 커지고 ... 를 반복하게 된다는 것이다.

따라서, 위 방식으로  그리디하게 수행해 나가면, 최적해를 찾을 수 있게 된다.

하지만 직관을 도저히 믿을 수 없다면, 조금 엄밀하게 증명을 해 보도록 하겠다.

최적해가 위 알고리즘을 통해 나오지 않기 위해서는, 아래 두 조건을 만족하는 r,g,b가 존재해야 한다.

1) b[x],g[y+1],r[z]의 거리가 b[x],g[y],r[z]의 거리, b[x+1],g[y],r[z]의 거리, b[x], g[y], r[z+1]의 거리보다 더 작다.

2) b[x+1], g[y], r[z+1]의 거리가 b[x+1], g[y+1], r[z+1]의 거리보다 작다. (즉, g가 더 작은 값에서 더 최적의 값이 존재한다.)

이런 경우가 존재한다면, 그리디하게 선택했을 경우 최적해를 보장할 수 없다.

하지만, 이런 경우가 과연 존재할까?

2)번 조건이 만족하기 위해선, 1)에 의하여 b[x+1], g[y], r[z+1]의 거리는 무조건 b[x+1],g[y],r[z]의 거리보다 작아야 한다.

    (b[x+1], g[y], r[z+1]의 거리 < b[x],g[y+1],r[z]의 거리 < b[x+1],g[y],r[z]의 거리)

그리고, r[z+1]은 r[z]보다 무조건 크기 때문에, r[z]는 b[x], g[y], r[z] 중 가장 큰 수는 아니어야만 한다.

또한, b[x+1], g[y], r[z+1]의 거리는 b[x], g[y], r[z+1]의 거리보다도 작아야 한다.

마찬가지로, b[x+1]은 b[x]보다 무조건 크기 때문에, b[x]는 b[x], g[y], r[z]중 가장 큰 수는 아니어야 한다.

따라서, g[y]가 b[x], g[y], r[z] 중 가장 큰 수가 되어야 한다.

그런데, 이는 1) 조건인 "b[x],g[y+1],r[z]의 거리가 b[x],g[y],r[z]의 거리보다 작아야 한다"에 위배된다.

따라서, 위 조건을 만족하는 r,g,b의 값은 존재하지 않고, 따라서 최적해는 위 알고리즘을 통해 항상 구할 수 있다.

사실 이걸 이렇게까지 엄밀하게 증명하고 풀었던 것은 아니라, 증명하는데 꽤 애먹은 것 같다 ㅎㅎ;

이렇게 했는데도 아직 좀 꺼림칙하다면, 에디토리얼의 풀이를 보기를 권한다.

사실 본질적으로 동일한 풀이이긴 하지만, 이해하기는 더 도움이 될 것이다.

이렇게 Codeforces Round #635 (Div. 2)의 A~D풀이를 끝내도록 하겠다.

E,F는 언젠가 실력이 되면 그때나 풀어보도록 하고 ㅎㅎ...

다음 Div3에서 꼭 블루 갔으면 좋겠다. 위 C 문제 덕에 DFS, 트리 공부도 더 할 수 있게 되기도 했고 말이다.

E 풀수 있을것 같은데? 아니 안되나? 으악!!

하고 터져버린 contest...

어차피 D까지는 거의 다 풀었겠지만 그래도 후기 쓰는 느낌으로 푼 문제들의 풀이를 해보도록 하자.

https://codeforces.com/contest/1335/problem/A

A. Candies and Two Sisters

문제가 무척이나 간단하고 쉬웠다.

숫자 n이 주어지고, 해당 n을 a>b (a>0, b>0, a+b=n)을 만족시키게 나누어 주는 경우의 수를 물어보는 문제였다.

경우를 두 가지로 나누어 보자.

1. n%2==0, 즉 n이 짝수일 때,

경우의 수는 정확히 n/2 - 1번이 나오게 된다. 가령 n이 6일 때, (5,1), (4,2)로 두 가지 경우가 존재한다.

2. n%2==0, 즉 n이 홀수일 때

경우의 수는 정확히 n/2번 나오게 된다. 가령 n이 7일 때, (6,1), (5,2), (4,3)으로 세 가지 경우가 존재한다.

이를 식 하나로 정리하면,

ans = (n-1)/2 로 정리할 수 있다.

그래서 그냥 n을 입력 받아서 (n-1)/2를 출력하면 되는 문제였다.

https://codeforces.com/contest/1335/problem/B

B. Construct the String

n, a, b를 입력받아서 크기 a의 substring에서 정확히 b개의 distinct한 글자가 들어가게 string을 만들어야 하는 문제였다.

풀이 방법이 여러 가지가 나올 수 있는 문제였다.

일단 내가 처음 생각해서 제출한 방법은 다음과 같았다.

1. 우선 크기 a-b+1만큼 모두 'a'로 채운다.

2. 그 뒤, b-1만큼 b,c,d,...으로 채운다.

3. 반복한다.

라는 생각으로 문제를 풀었다.

그런데 내 친구들이 푼걸 보니, 그냥 더 간단하게 처음부터 끝까지 b번만큼 abcdabcd...으로 반복하면 되더라...

어떻게 풀었건, 이런 방법들로 풀면 OK일것같다.

https://codeforces.com/contest/1335/problem/C

C. Two Teams Composing

한 쪽 팀에는 같은 능력치를 보유한 사람만, 다른 한 쪽 팀에는 서로 다른 능력치를 보유한 사람만으로 채울 때 최대 몇명까지 팀을 채울 수 있는지를 물어보는 문제였다. (양쪽 팀의 사람 수가 같다는 전제 하에)

어떻게 나눠야 최대 인원으로 팀을 나눌 수 있을지 생각해보자.

우선, 모두가 동일한 능력치를 가진 팀의 최대 인원은, 입력받은 숫자 중에 가장 자주 나온 숫자의 개수와 동일하다.

즉, 1 2 3 4 4 4 가 입력으로 주어지면 동일한 능력치 팀은 최대 3명이다.

모두가 다른 능력치를 가진 팀의 최대 인원은 반대로, 입력치의 서로 다른 숫자의 개수가 될 것이다.

즉, 1 2 3 4 4 4 가 입력으로 주어지면 서로 다른 능력치 팀은 최대 4명이다.

여기서 주의해야 할 점은, "서로 다른 숫자"에는 "가장 많은 개수의 숫자"도 포함된다는 것이다. 

자, 이제 서로 다른 숫자의 개수와 가장 자주 나온 숫자의 개수를 구한 뒤 어떻게 해야 할지 경우를 나눠보자.

1. 서로 다른 숫자의 개수 > 가장 많이 나온 숫자의 개수인 경우

ex) 1 2 3 4 5 5 5

이 경우, 최대로 많이 나눠도 가장 많이 나온 숫자의 개수 (5 5 5로 3개)까지만 팀이 나눠지므로, 가장 많이 나온 숫자의 개수가 정답이 된다.

2. 서로 다른 숫자의 개수 < 가장 많이 나온 숫자의 개수

ex) 1 2 3 3 3 3

이 경우, (1, 2, 3), (3, 3, 3)으로 나눌 수 있으니, 서로 다른 숫자의 개수가 정답이 된다.

3. 서로 다른 숫자의 개수 == 가장 많이 나온 숫자의 개수인 경우

ex) 1 2 3 3 3

이 경우, (1, 2), (3, 3)으로 최대 2명까지만 나눌 수 있으니, 서로 다른 숫자의 개수 - 1 이 정답이 된다.

이렇게 경우의 수를 세 가지로 나누면 손쉽게 정답을 구할 수 있다.

참고로, "서로 다른 숫자의 개수"에 "가장 많이 나온 숫자"를 포함하지 않으면 문제를 풀기 무척 까다로워 진다.

가령, 입력이 1,2,3,3,3,3으로 주어진 경우, 분명 서로 다른 숫자와 가장 많이 나온 숫자의 개수는 각가 2,4이지만 정답은 3이 되야 하기 때문이다.

https://codeforces.com/contest/1335/problem/D

D. Anti-Sudoku

솔직히 C보다 쉬운것 같은데;;

완성된 스도쿠를 최대 9개의 숫자를 바꿔서 각 줄과 블럭에 두 개 이상의 숫자가 겹치게 해야 한다.

일단, 각 블럭과 각 줄에 딱 하나씩만 죄다 숫자를 바꿔보자.

일단 나는, 저렇게 동그라미 친 부분의 숫자를 바꾸도록 했다.

해당 a[i][j]를  a[i][j]%9+1로 바꾸면 무조건 다른 숫자로 바뀌게 된다.

또한, 이렇게 하면 모든 줄, 블럭에 각각 숫자가 하나씩 바뀌므로 무조건 안티-스도쿠가 완성된다.

근데 다른 사람 코드 보다가 알았는데, 이렇게 할 필요도 없이 그냥 모든 숫자 '1'을 '2'로 바꾸면 완벽하게 해결되더라;

똑똑한 사람은 참 많은 것 같다.

딱 이렇게 40분컷 내고 장렬히 전사하고 말았다.

사실 E1을 풀 작정으로 1시간 20분동안 달렸으면 풀 수 있을만 했는데,

E2를 풀 작정으로 생각을 해버려서 그만...

E1 풀었으면 블루 갈만도 했는데 ㅠㅠ

사실 끝나고 나서 다른 문제들도 조금 풀긴 했는데, 에디토리얼 보고 푼거라 풀이로 울리긴 좀 그렇다 ㅎ;

https://codeforces.com/contest/1339

이번 코드포스는 A 문제 이해를 못하겠어서 거르고 B,C풀고 A를 풀었다.

그 대신 B,C를 1시간만에 풀고 A도 1시간 언저리에 해결했는데 D,E를 건드리지를 못하겠어서 그냥 gg친 대회 ㅠㅠ

c++ 트리 공부 언젠가 꼭 해야겠다. 트리 문제 나올때마다 풀지를 못하니;;

https://codeforces.com/contest/1339/problem/A

A. Filling Diamonds

문제에서 주어진 공간을 다이아몬드로 채우는 경우의 수를 출력하면 되는 문제였다.

대체 왜 이걸 이해를 못한건지;;

아무튼 문제 이해했다고 치고, n=3일때 부터 생각을 해 보면...

위 도형을 다이아몬드 모양으로 채우기 위해선 어떻게 해야 할지 생각을 해 보자.

일단 위쪽 줄과 아래쪽 줄의 삼각형 갯수가 5개인 홀수이므로 적어도 한 다이아몬드는 세로로 서 있는 형태여야 한다.

그런데 한 다이아몬드가 서 있는 형태이면, 나머지 자리는 무조건 한 가지 경우로 고정되게 된다.

그리고 이러한 점은 n=4, 5, 6, ... 일때도 동일하게 적용이 된다.

따라서, 정답은 그냥 서 있을 수 있는 다이아몬드의 갯수이고, 이는 n값과 동일하다.

https://codeforces.com/contest/1339/problem/B

B. Sorted Adjacent Differences

배열 하나가 주어졌을 때, 해당 배열을 |a1−a2|≤|a2−a3|≤…≤|an−1−an| 을 만족하도록 바꾸는 문제이다.

어렵게 생각하면 무척이나 어려워질 수 있는 문제이다. 특히 두 번째 input example이

4

8 1 4 2

---------

1 2 4 8

이렇게 들어오는지라 문제 풀이 방식을 생각하기 이전에 이 예제에 너무 현혹되었으면 풀기 까다로웠을 것 같다.

일단 풀이먼저 말하자면, 무척이나 간단하다.

우선, 배열을 정렬해 준다.

5 -2 4 8 6 5  --> -2 4 5 5 6 8

그 뒤, 가운데 원소를 출력한 뒤, (n이 짝수여도 그냥 n/2번째 원소를 출력하면 된다.) 해당 원소의 한칸 오른쪽 원소, 한칸 왼쪽 원소, 두칸 오른쪽 원소, 두칸 왼쪽 원소 ... 를 출력해 주면 된다.

위의 예시에서는, 5, 5, 4, 6, -2, 8이 되겠다.

이렇게 해 주면, 배열이 정렬되었으므로 중앙에서 멀어질수록 당연히 중앙의 원소와의 거리 (|a1−a2|)가 커지게 되고, 이를 오른쪽, 왼쪽을 반복해주면 자명하게 절댓값의 크기가 커지게 된다.

추가) 에디토리얼에 이해가 쉬운 사진이 있어 첨부한다.

https://codeforces.com/contest/1339/problem/C

C. Powered Addition

다른 Div2 C번 문제보다는 쉬웠던 것 같다.

(그래서인지 푼 사람도 5000명이 넘어가고 ABC다풀어도 점수가 별로 안올랐다 ㅠㅠㅠ)

우선 문제에서 관찰할 수 있는 것들을 살펴보자면,

1) x초 동안 더할 수 있는 최대 수는 2^x - 1이다. (1초 후엔 1, 2초 후엔 1+2=3, 3초 후엔 1+2+4=7...)

2) x초 동안 더할 수 있는 수는 0~2^x - 1이다. 즉, x초가 지났을 때, 0~ 2^x - 1 중 원하는 수만큼 더해줄 수 있다. (5=1+4, 1+2+4 등으로 표현할 수 있으므로)

3) 1),2)를 통해 알 수 있는 점으로, 만약 aₙ > aₙ₊₁ 이면,  aₙ₊₁ - aₙ만큼 더하는 것이 가장 빠르게 aₙ <= aₙ₊₁를 만드는 방법 중 하나이다.

4) 3)에 의하여, non-decreasing 배열로 만들 때 가장 최적의 방법 중 하나는 aₙ > aₙ₊₁이면 aₙ₊₁ - aₙ만큼 더해주는 것이다.

따라서 정답을 구하는 알고리즘은 다음과 같다.

i=0부터 n-1까지,

if aᵢ > aᵢ₊₁ :  max_t = max(max_t, aᵢ₊₁ - aᵢ);

ans = log2(max_t) + 1;

언제나 그렇지만, 이런 문제들을 풀고 나면 "엄청 쉬운 문젠데, 왜 이렇게 오래 걸렸지..?" 하는 생각이 들곤 한다.

언젠가 D,E도 풀고 풀이를 올릴 수 있는 날이 왔으면 좋겠다...