2022 청정수컵 새내기 Round 간단한 풀이 + 후기

78분 만에(백준 채점 현황에 그렇게 뜨니까 맞겠지?) 올솔을 하고 1등상으로 키보드를 받았다. 기분이 매우매우 좋다! 내가 푼 순서대로 풀이를 쓰겠따

 

 

-----------

 

 

1분정도 A를 보다가 지문이 약간 이해가 안 돼서 B로 넘어갔다.

 

 

B 청정수열 (Easy) (00:04)

1부터 n까지, 11223344...nn 으로 나열하면 최소이다. 이때, 11,22,33,nn의 n개를 나열하는 경우의 수는 n! 이다.

 

 

C를 보자마자 압도적인 지문 길이를 보고 바로 D로 넘어갔다.

 

 

D 두라무리 휴지 (00:10)

그냥 구현하면 된다. 단어의 글자들을 재배열해서 어떤 단어를 만들수 있는지는 글자의 등장 횟수를 비교하면 된다.

 

 

F번을 보다가, 18로 나눈 후 케이스 나누는 것이 귀찮아서 E로 넘어갔다.

 

 

E 베스킨라빈스~N~귀엽고~깜찍하게~ (00:14)

(N - 1) % (M + 1)이 0인지 확인하는 문제. 보자마자 바로 코드를 짰다

 

 

F 썸 팰린드롬 (00:19)

9999?9999꼴로 만드는 것이 무조건 이득이다. 이때 (N mod 18)이 9보다 크면 홀짝을 나누어 풀고, 9보다 작거나 같다면 그냥 +1하면 된다.

 

 

A 두~~부 두부 두부 (00:30)

(k + m - 3) % n

 

 

C 서강의 역사를 찾아서 (00:35)

B_i - A_i의 최댓값을 구하면 된다.

 

 

G (00:48) WA

뇌절을 좀 했다...

 

 

H로 도망갔다.

 

 

H 청정수열 (Hard) (00:54)

단순하게, N=4일때, [1, 2, 3, 4, 1, 2, 3, 4]로 만든다고 생각해보자. 두 숫자 사이에 모든 수가 들어오기 때문에 이건 최대를 가진다고 확신했다. 그러나, 예를 들어 오른쪽 2와 오른쪽 3의 위치가 바뀐다면, 이것도 최대일까?

 

[x, y, S, x, y]를 [x, y, S, y, x]로 바꾸어보자. x와 y가 자리를 바꿨으니, x에 대한 점수는 xy만큼 증가한다. 그리고 Y에 대한 점수는 xy만큼 감소한다!

 

수열의 우측 절반에서 인접한 두 원소를 바꾸는 것이 점수에 영향을 주지 않음을 찾아냈다. (왼쪽에서 바꾸는 것도 당연히 영향을 주지 않는다.) 그러면 수열의 절반은 마구잡이로 순서를 구성할 수 있다는 말이 된다.

 

다시 정리해보자.

 

순열 A, B가 [1, N]의 정수로 이루어져있다고 해보자. 점수?가 최대가 되려면 수열은 A와 B를 이어붙인 형태여야 할 것이다. A와 B를 만드는 경우의 수는 각각 N!이므로, 경우의 수는 (N!)² 가 된다. 점수의 합은.. 그냥 적절히 구현하면 된다.

 

신나서 풀이를 좀 길게 썼다.. 대회 중에는 두 원소를 바꾸는 것이 값에 영향을 주는지에 대한 엄밀한 증명을 안했다. 확신이 섰고, 그렇게 제출한 코드는 AC를 받았다.

 

 

G Swap the elements (01:18)

수열 A를 정렬하자. 이때, 원래 있던 인덱스를 기억해둘 것이다. 가장 많이 등장하는 수의 등장 횟수를 c라고 하자. 비둘기집 원리에 따라 2c > n이면 답은 존재하지 않는다. 이제 답이 존재하는 경우를 생각해보자. (정렬된) 수열 A를 오른쪽(혹은 왼쪽)으로 c칸 shift하면 겹치지 않게 만들 수 있다. ([1, 2, 3, 4]를 오른쪽으로 1칸 shift하면 [4, 1, 2, 3]이다.) 이렇게 만들어진 수열의 원소를 각각 원래 인덱스의 위치에 넣어주면 끝이다.

 

 

----------

 

 

남은 시간동안 너무 심심해서 죽는 줄 알았다. 앞으로의 ps, cp 계획도 짜고, sparse table도 오랜만에 구현해보고, 엎드려서 자보려고도 하고 (근데 잠이 안 왔다 ㅎㅎ)

 

결국에는 스코어보드를 띄워놓고 3초마다 f5를 열심히 누르고 있었다.

 

H번은 골1로 예상하셨다고 했는데, 난이도는 G번이 훨씬 어려웠다... H는 골4정도라고 느꼈고 G는 골2정도 되는 것 같았다

 

끝나고 고기도 맛있게 먹었습니다. Dong_gas(dong_gods)님의 창피했던 건배사도 잘 들었습니다.청춘은바로지금!청바지!!

 

----------

 

ㄷㄷ