SUAPC 2022 Summer, 신촌지역 대학생 프로그래밍 대회 동아리 연합 여름 대회 Open Contest 참가 후기

최종 결과 : 6솔 (그리고 6솔 중에서 순위 가장 낮음)

B번 내비게이션 : 그냥 함수 구현 문제다. std::abs 쓰면 됨.

0:11 B Accepted

F번 차의 개수 : 구성적 문제다. 그냥 등비수열이랑 등차수열 출력하면 됨...

0:18 F Accepted

C번 패스 : 이것도 구성적 문제다. 간단한 관찰을 통해, 홀수일 때는 항상 불가능하다는 사실을 알 수 있다. 공이 항상 첫 패스한 사람에게 돌아오기 때문. 근데 짝수일 때가 문제였다. 나는 간단한 관찰을 통해 n이 2^k 꼴일 때 2^k부터 1까지 역순으로 출력하면 그게 언제나 답이 된다는 사실을 알았다. 그리고 증명은 안 했지만 "이런 문제는 왠지 곱산술 성질을 가지고 있을 것 같음"이라는 생각을 했다. 그러니까 n=p일 때 참이고 n=q일 때 참 iff n=pq일 때 참일 거라고 추측했다는 소리임. 그러면 n = 2^k일 때만 정답이 있을 거라는 결론을 내릴 수 있음. 이 추측을 코드로 구현해 proof by AC를 시도했고 장렬히 전사했다.

A번 수 맞히기 게임 : 기댓값의 선형성을 단순 구현하면 되는 실버 수준 재귀 문제라고 생각했는데, DP 문제였다. 그러니까 지문 읽은 사람은 당연히 저 사람이 이분 탐색 전략을 쓸 거라고 추측하게 되는데, 그러면 낚이는 거임. 저 사람이 머리 상태가 영 좋지 않은지 pivot을 중앙값으로 잡는 게 아니고 쓸데없이 중앙 +- 1로 잡기 때문이다. 그런데 그 차이가 이 문제가 실버 수준 재귀 문제냐 DP 문제냐를 가른다... 결국 나는 이 문제가 DP라는 것을 깨닫지 못하고 장렬히 전사했다.

그리고 한 30분? 정도 C와 A를 깔짝거리고 있었다. 그러나 아무런 소득도 얻지 못했다.

J번 김밥 : 보자마자 스위핑 써야 한다는 사실은 알았다. (보통 저렇게 생겼으면 스위핑 아닐 수가 없음.) 그러나 스위핑의 정렬 기준은 무엇으로 잡고 자료구조는 무엇을 써야 하며... 같은 걸 생각하다 시간을 날렸다. 갈수록 답이 안 나오니까 '이거 세그먼트 트리인가?' 하는 생각이 들었다. (근데 당연히 세그먼트 트리로도 풀 수 있겠지...) 그러나 결국에는 정렬 2번 + 우선순위 큐로 해결함. 그러나 3번째 AC를 얻기까지 3번의 WA를 바쳐야 했고, 그동안 멘탈이 살짝 나갔다. 왜냐면 그때 내 상태가 2솔 3WA였으니까...

3:11 J Accepted

다시 C번 패스 : 간단한 관찰을 통해, n이 짝수이면 공은 마지막 순간에는 항상 첫 주자의 반대편에 도착한다는 사실은 알고 있었다. 이 사실을 십분 이용해서 대칭성을 이용해서 구성을 해 보자는 발상을 했고, 성공해서 n = 6일 때 해를 찾았다! 그리고 그 해가 상당히 깔끔했기 때문에 그걸 모든 짝수 n에 대해 확장하는 데 성공함.

3:22 C Accepted

I번 딸기와 토마토 : 많은 조건 분기 문제를 좋아하는 프로그래머는 아마 없을 것이다. 나도 그 중 하나여서 처음 이 문제 봤을 때 "으악 X발 이게 뭐야" 하면서 넘겼는데, 슬슬 이 문제를 풀어야 할 때가 온 것 같다는 직감이 들기 시작함. 솔직히 이 문제는 할 말이 없다. 예... 열심히 케이스 나누시길 바랍니다...

4:11 I Accepted

다시 A번 수 맞히기 게임 : 사실 재귀를 이미 짜 놨으면 그걸 DP로 바꾸는 일은 어렵지 않다. 그냥 리턴값 왼쪽에 memo[i][j] = << 이것만 추가해 주면 됨. 그러나 그럼에도 TLE가 났고, 상상 가능한 모든 최적화를 시도해봤지만 모두 실패했다. 그러다가 마지막 순간에 극적으로 원인을 찾았는데, 출력부에서 개행을 std::cout << std::endl로 하고 있었음. 근 3개월 넘게 하지 않은 실수인데 여기서 마주하다니 정말 빡치는 일이 아닐 수 없다.

4:45 A Accepted