solved.ac Grand Arena #1 참가 후기

 

 

※ 이 글은 대회가 종료된 직후에 작성자의 기억을 바탕으로 작성된 글로,

    그때의 감상 및 시점을 기준으로 작성되었음을 미리 알려드립니다.

 

 

 

 

* 대회 링크

 

https://www.acmicpc.net/contest/view/1065

solved.ac Grand Arena #1 · Arena #1

 

 

 

오랜만에 유저? 법인? 대회 참가 ( + 최근에 글을 못 올렸던 이유는)

 

1. 좀 놀고 싶어서

2. 커미션? 외주? 아무튼 뭐 하나 프로그램을 만드는 중이다.

 

어쨌든 그래도 솔브닥에서 아레나라는 시스템을 추가하고

 

사실 코드포스는 하기 귀찮았던 나에게는 레이팅을 얻을 방법이라 생각을 해서

 

그런김에 참가를 했다.

 

 

최종적으로 A, B, G, H를 풀고, E를 풀다가 결국 실패했다.

 

나머지 문제는 확인도 안 했다.

 

스코어보드로 어떤 것이 할만한지 찾아서 했기 때문.

 

이전에 썼던 대회 글과 비슷하게, 문제 내용의 정말 간단한 요약,

 

그리고 접근법까지만 설명할 것이다.

 

 

문제 링크는 상단의 대회 링크를 통해 확인할 수 있으니,

 

그 쪽을 통해 확인하길 바란다.

 

 

 

 

A. 양말 짝 맞추기 (해결)

 

단순 구현 문제

 

짝이 맞지 않은 양말로 인해 5개 중에 홀수 개만큼 있는 양말이

 

남는 양말일 수밖에 없다.

 

 

 

 

B. 끝말잇기 (해결)

 

이것도 단순 구현 + 문자열 이용 문제

 

끝말잇기는 알다시피 앞뒤 글자가 이어지고, 중복되는 단어를 말하면 안된다.

 

그 조건에 맞게 비교해줘서 찾으면 되는 간단한 문제다.

 

 

 

 

 

E. 배수 피하기 (실패)

 

크기가 2 이상인 집합에서 서로 다른 어떤 두 원소를 뽑아 더해도 K의 배수가 안되는 집합의 개수를 구하는 문제다.

 

딱 봐도 조합론 문제인데

 

일단 나는 전체 개수(2의 거듭제곱 꼴)에서 원소 1,0개 인 경우와

 

같이 들어가면 안되는 두 값을 포함한 집합을 중복되지 않게 잘 제외해서 더하는 식으로 구상했는데(자세히 설명은 복잡)

 

내 구상에서 오류가 있었는지, 코드 작성 중에 오류가 있었는지,

 

내가 생각한 예제는 잘 돌아가는데 반례를 찾지 못해서 결국 실패했다.

 

 

 

 

 

 

G. 막대 만들기

 

가지고 있는 막대를 그대로 쓰거나 N배 늘리는 방식으로 반복해서

 

원하는 막대를 만드는 방법의 개수를 각각 구하는 것인데,

 

처음에는 단순한 약수,배수 문제, 즉 정수론 문제로 생각했었는데

 

이 N,M... 배 하는 것의 순서가 바뀌는 경우([2배, 3배, 2배]와 [3배, 2배, 2배])는 다른 방법으로 취급을 한다.

 

 

그래서 먼저, 1을 제외한 나머지 수에 대해 1을 제외한 약수의 개수를 구해주고,

 

주어지는 막대는 길이가 모두 다르므로, 존재하는 막대에 대해

 

그 배수 길이인 막대를 만드는 방법 수에

 

(만드려는 막대 길이 / 사용하려는 막대 길이) 의 1을 제외한 약수의 개수를 더해주는 식으로 해결했다.

 

이것을 가지고 있는 모든 막대에 대해 적용하면 방법의 개수가 구해진다.

 

 

 

 

 

 

H. 행렬 연산 (행렬 계산하기)

 

행렬의 행, 열에 있는 모든 원소에 어떤 값을 모두 더해주는 것을 반복한 결과를 출력하는 문제.

 

매 반복마다 더해주면 당연히 Time Limit Exceed가 될 것이므로,

 

그냥 각 행, 열에 대해 더해줄 값을 계속 누적해놨다가,

 

출력할 때, 그 원소가 위치한 행과 열에 저장된 값을 그대로 더해줘서 출력하면 끝난다.

 

 

 

 

 

총평 및 여담

 

E를 풀었으면 더 좋았을텐데

살짝 아깝긴 하다.

 

 

그래도 결과를 보니, 퍼포먼스는 SS+이 떴고,

 

레이팅 계산법에 따라 일단 0에서 B+까지 올라갔다.

 

추후 아레나에도 참가해서 레이팅이나 한 번 높여나 보자.

 

이거 생각보다 재밌네 레이팅