오늘의 PS (20) - 220708

13:00~15:30 모비스 본선

16:30~18:30? 천코대 오픈콘

23:35~01:35 에듀코포

를 쳤다. 모비스 대회에 대한 후기는 생략하도록 하겠다.

 

제6회 천하제일 코딩대회 본선 Open Contest

2시간 늦게 참여하기도 했고 중간에 자리를 몇 번 비워서 진지한 마음으로 치지는 않았다. 아마 종료때까지라도 했으면 F는 풀었을 것 같다.

 

A. Gravity Hackenbush

지문 낚시 문제이다. 각 플레이어가 초록색 간선을 최대한 많이 쓰는 것이 최적이므로 이를 토대로 비교해주면 된다.

 

C. Merge the Tree and Sequence

Split the SSHS 문제와 세팅이 비슷하다. 간선을 묶는 것은 그때와 같이 하면 되고, 남은 부분은 간선을 묶는 것에 비하면 크게 어렵지 않다.

 

D. 바지 구매

입력 제한이 굉장히 친절하다. 따라서 그냥 주어진 좌표가 함수 위에 있는지만 확인해주면 된다.

 

E. 반전 수와 쿼리

1번 쿼리가 inversion의 홀짝을 바꾼다는 것은 널리 알려져 있다. 2번 쿼리도 이를 바탕으로 조금만 잘 생각해주면 된다.

 

G. 인공 신경망

주어지는 신경망들의 계수를 잘 합쳐주면 된다.

 

H. 최대 최소공배수

GCD를 곱/LCM의 형태로 보면, \(N\)이 홀수일 때는 \(N-2, N-1, N\)을 선택하는 것이 최적이다. 곱이 최대이며 LCM이 최소이기 때문이다. 같은 이유로, 짝수이면 \(N-3, N-2, N-1, N\) 중 3개를 선택하는 경우를 다 해보면 된다.

 

I. 최장 최장 부분 증가 수열

그냥 2차원으로만 바꿔주면 된다.

 

J. 행성 정렬

모든 수의 LCM을 구해주면 된다. 이 역시 제한이 친절하다.

 

Educational Codeforces Round 131

A. Grass Field (0:01, +)

다 1이면 2, 다 0이면 0, 아니면 1이다.

 

B. Permutation (0:04, +)

\(d=2\)일 때가 최적이다. 이를 가능한 한 많이 채워주면 된다.

 

C. Schedule Management (0:10, +)

일이 가장 많은 사람과 가장 적은 사람의 차가 2 이상이라면 많은 사람의 일을 적은 사람에게 주어도 된다. 각 사람이 가진 일의 양의 최댓값이 줄어들거나 같기 때문이다. 이를 반복해주면 문제를 해결해 줄 수 있다. 이는 일의 범위가 작아서 적용 가능한 풀이이고, 대부분은 파라메트릭으로 푸신 것 같았다. 여기까지 풀고 스탠딩을 켰는데 1페이지가 떠서 기분이 좋았다.

 

D. Permutation Restoration (0:28, +2)

부등식을 잘 풀면 각 자리에 대해 가능한 해의 구간을 알 수 있다. 이를 회의실 배정 문제처럼 잘 배정해주면 된다. 불가능 여부를 따지는 것도 어렵지 않아서 같이 주어도 되었을 것 같다.

 

이후 E를 이상한 그리디로 열심히 비비다 틀린 풀이라는 것을 깨달았다. E나 F중 하나는 풀었어야 한다고 생각하긴 하는데, 그래도 어떻게 오렌지를 가긴 한다. 두 대회에서 알 수 있듯 쉬운 문제는 진짜 엄청 빨리 푸는데 (천코대 오픈도 잘 보면 22분동안 6문제 풀었다) 일정 난이도 선 위와 아래의 갭이 굉장히 큰 것 같다. 이런 문제점을 느낀지 꽤 됐는데도 잘 안 고쳐진다.. 다음 Div.1에서는 꼭 오르면 좋겠다.