240128 팀 연습 (Yokohama 2023)

동일하게 원격 1컴 체제로 진행했다. 연세대의 SCC, Cookie팀과 연락이 닿아서 시간을 맞춰 진행하였다. 

 

셋 : https://codeforces.com/gym/104832 (https://www.acmicpc.net/category/detail/4070)

 

 

petamingks가 앞, 내가 가운데, kwoncycle이 뒤를 보고 시작했다.

 

~0:06

A가 많이 풀려서 구현이 가장 빠른 내가 잡고 풀었다. 

 

~0:21

나는 그대로 B를 봤고, 그 동안 petamingks가 F를 풀었다고 해 바로 코딩에 들어갔다. 뭔가 실수가 있었는지 1번 틀리고 맞았다. 그 사이 B 풀이를 대충 완성할 수 있었다. kwoncycle은 자기쪽 문제가 다 어렵다고 하면서 문제를 계속 읽었다. 후에 이는 사실이었음이 밝혀졌다.

 

~0:25

B를 바로 짜서 맞았다. 이후 D를 봤는데 그냥 웰노운 DP 같아서 바로 코딩에 들어갔다.

 

~0:57

D는 구현이 좀 필요해서 열심히 짠 후 냈더니 틀렸다. 코드가 완벽하다고 생각해 문제를 다시 읽었더니 숫자가 9 이하여야 한다고 한다. 살짝 고쳐서 AC를 받았다. 이후 K를 풀었다고 한 kwoncycle에게 컴퓨터를 넘겼다.

 

~1:49

kwoncycle이 약 50분간 이어진 K와의 힘든 사투 끝에 AC를 받았다. 원래 많이 틀리는 타입은 아닌데 음수 나눗셈에 문제가 있었다고 한다. K는 첫 코딩이 빨리 끝나서 눈으로 주로 디버깅했고, 그 사이에는 petamingks가 J 코딩을 조금씩 진행하였다. 이 과정에서 modint 구조체가 필요하다고 해 팀노트에서 복붙해 주었다.

 

~2:11

J 코딩이 잘 끝났고, 제출했지만 TLE를 받았다. 다행히 간단한 상수최적화로 바로 AC를 받을 수 있었다. 문제는 이 시점에서 컴퓨터가 비었다는 점이다. 나는 많이 풀린 E를 1시간 가량 보았지만 감을 잡지 못했고, 문제를 읽는다는 핑계로 H~J를 읽었지만 각각 다음과 같은 결론을 얻었다. 
H - 플로우가 아닌 것 같은데 까보면 플로우일 것 같다

I - 플로우같이 생겼는데 까보면 아닐 것 같다

J - 웰노운같이 생겼는데 하나도 모르겠다

결국 그나마 수학에 가까운 I를 남은 둘에게 던져준 후 어떻게든 풀어야 했던 E를 다시 잡았다.

 

~3:58

둘이 뭔가 토론하더니 I 풀이가 나왔다고 했다. 일단 컴퓨터가 비는 상황은 막았으니 나는 E에 최대한 집중하였다. 여러 시행착오 끝에, 뭔가 맞아보이는 DP 정의를 찾을 수 있었다. 문제는 느리다는 점이었는데, 제한도 그렇고 일본 셋이다 보니 뭔가 SOS DP 스러운 전처리 계산이 필요할 것 같아서 이쪽으로 접근하였다. 그러던 중 I 코딩이 끝났고, 파이썬 코드를 C++로 내서 1번, Yes를 YES로 써서 1번 틀린 후 맞았다.

 

~4:25

더 이상 풀 수 있는 문제가 E밖에 없었기에 일단 컴퓨터를 넘겨받았다. 다행히 타자를 치다 보니 어떻게 해야 할지 감이 좀 잡혔고, 예제가 나와서 제출한 후 다행히 1번에 맞았다. 남은 시간동안은 J를 좀 보다가 끝났다.

 

문제별 요약

A (S1, solved by leo020630) : 제한이 작아서 브루트포스로 해결할 수 있다.

B (P5, solved by leo020630) : 분수는 식정리를 잘하면 보통 분리가 된다. 이후에는 그리디한 구현을 통해 \(O(N)\)에 해결할 수 있다.

C (R, Not solved) : 일본의 성명절기 다항식 조합론이다. 솔브수도 그렇고 필요한 배경지식도 그렇고 다이아는 아니어 보인다.

D (P5, solved by leo020630) : 그냥 흔한 구간 DP 문제이다. 해싱은 써도 되고 안 써도 되는 듯 하다.

E (D5, solved by leo020630) : 사용할 숫자를 정하고 하나씩 쌓아 나가자. \(state\)에 \(bit\)가 추가될 때, 다음의 조건을 만족해야 전이가 가능하다. \(bit\)를 중간으로 하는 모든 \(a,c\)에 대해, \(state\)에 \(a,c\)가 모두 있거나 모두 없으면 안된다. 이를 빠르게 확인해야 하는게 중요한데, \(f[b][state]\)를 \(b=bit\)에 대해 \(state\)에 \(a,c\)가 모두 포함되었는지 여부로 정의하자. 이 테이블이 있으면 두 조건을 모두 어렵지 않게 확인할 수 있고, 이는 SOS DP로 채워줄 수 있다. 이 테이블의 값이 0 또는 1이므로 \([b]\) 차원을 0/1 대신 \(N\)비트 정수를 사용하는 것으로 대체할 수 있다. 결과적으로 전처리 \(O(N2^N)\), DP \(O(N2^N)\)에 해결할 수 있다.

F (G3, solved by petamingks) : 재미있는 애드혹 문제다. 어렵지 않아서 업솔빙했는데 좋은 문제라고 생각한다.

G (P1, solved by petamingks) : 뭔가 수학적 관찰을 통해 차원을 잘 줄이는 DP라고 한다. 이런 유형을 앳코더에서 좀 봤는데 일본 리저널 아니랄까봐 바로 나오는 것이 신기했다.

H (D3, Not solved) : 식을 잘 만지면 민컷 문제로 바꿀 수 있다고 한다. 이런 유형에 나름 익숙하다고 생각했는데 호되게 당했다.

I (D4, solved by kwoncycle) : 뭔가 복잡한 그리디라고 한다. 섣불리 시도하기 힘든 문제라고 생각했는데 잘 맞아왔다.

J (D5, Not solved) : 트리 문제라 열심히 읽어봤는데 감을 잡지 못했다. 업솔빙 예정

K (P5, solved by kwoncycle) : 더러워 보이는 기하 인터랙티브 문제다.

 

 

느낀 점 + 피드백

확실히 쉬운 문제가 많지 않은 셋에서는 중후반 운영이 어려운 것 같다. 풀이를 내지 못해 컴퓨터가 비는 경우가 꽤 발생하였다.

 

이번에는 어떻게 잘 넘어갔지만, 다이아 이상 문제들 풀이 내는 연습을 꾸준히 해야겠다는 생각이 들었다.

 

연습을 열심히 하자.

 

연습을 같이 돌리는 팀이 있으니 자극도 되고 좋았던 것 같다.

 

+팀연습 같이 하실 팀 연락주세요