코드포스 Educational Round 89 (떡상 기념) 후기

블루 턱걸이로 들어가고 한동안 쉬다가 어제 열린 edu 코포를 참가했습니다. 아주 운이좋게 4솔을 해서 레이팅이 떡상한 기념으로 글을 씁니다!

 

(A) Shovels and Swords

요즘 뭔가 A번이 어려운거 같은 느낌이,, A번 4번 틀려서 시작부터 멘탈이 나가서 망했다 싶었는데,, 뒤에 문제가 잘풀려서 다행이었습니다.

 

이문제는 두수 a,b를 입력 받은뒤 만들 수 있는 shovle 과 sword의 최대 개수를 구하는 문제인데 작은수의 2배보다 큰수가 크면 작은수가 무조건 답이고 그렇지 않다면 저는 큰수와 작은수의 차이를 계산해서 그개수만큼 만들고,(만들 수 있다면)  남은 두 재료의 개수가 같아지므로 /3*2 한 값만큼 더해서 여차여차 했는데 b번보다 이게 더 어려운 거 같습니다,,

 

(B) Shuffle

이 문제는 배열의 각원소 1~n번째 원소가 적절한 swap을 통해 몇개가 1이 될 수 있는지 찾는 문제입니다. 입력 되는 값들을 통해 포함 할 수 있는 구간을 좌우로 계속 늘려간뒤 최종적으로 R-L+1 을 하면 답이 됩니다.

 

(C) Palindromic Paths

1,1 에서 n,m 까지 가는 모든 경로가 펠린드롬을 유지하도록 최소 개수의 원소를 바꿔야 하는 문제입니다.

 

그림을 좀 그려서 보니 대칭되는 대각선의 원소들이 모두 동일하면 위의 조건을 만족한다는 것을 알 수 있었습니다. 각 대칭되는 대각선의 원소들은 서로 각각의 경로에서 펠린드롬의 해당 위치의 원소임이 자명하기 때문입니다. 이후 구현은 1,1 n,m 에서부터 각각 대각선을 한칸씩 밀면서 최소로 바꿀 수 있는 횟수를 더해주면 됩니다. 이때 예를들어 대각선이 홀수 개수라면 중간에 해당하는 대각선의 원소는 변경 할 필요가 없으니 이부분은 처리할 필요가 없습니다.

 

이게 모양이 n*m 형태라 대각선의 시작점을 찾을 때 저는 1,1 에선 오른쪽으로 밀다가 더이상 못가면 밑으로 내려갔고

n,m에선 위로 올리다가 더이상 못가면 왼쪽으로 밀면 딱맞게 처리가 가능합니다.

 

(D) Two Divisors

이 문제는 어떤수의 두약수를 더한 값이 그수와 Gcd 가 1인지 찾아서 그러한 약수 조합이 있으면 출력하는 문제입니다.

솔직히 이문제 운이 좋아서 맞은 것 같습니다. 정해는 가장 작은 소인수를 찾아서 해당 조건을 만족하도록 처리 하는 것 같은데 저는 처음에 map 이용해서 2~ abs(10000000) 까지 다돌리면서 gcd가 1인 그런 숫자들의 약수를 저장하면서 진행 했는데 당연히 tle가 났습니다. 숫자가 천만이니 메모리가 괜찮을 것 같아서 배열로 다 바꾸고 입력 받은 숫자에 대해서만 그런 값을 찾았습니다. 그리고 한번 찾은 수도 체크를 해서 여차여차 하니 1초안에 통과가 되었습니다,, 

 

 

A에서 비록 4번을 틀렸지만 무려 85점이 올랐습니다,,

저는 현재 4학년이라 이제 취준에 집중을 해야해서 코포나 알고리즘은 당분간 쉴 것 같은데 마지막으로 점수를 많이 올려서 기분이 좋습니다. 코포는 여유가 생기면 계속 할 것 같은데 퍼플 한번 달면 정말 좋을 것 같네요 ㅎㅎ..