cdjs의 코딩 공부방

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도 풀고 풀이를 올릴 수 있는 날이 왔으면 좋겠다...