2022 Sogang Programming Contest Open (Master)

2022 Sogang Programming Contest Open (Master)

서론

Champion Divison 풀다가 늦참하였다.

 

A - WARBOY

단순 수학

01:46 AC

 

B - 유통기한

조금 귀찮은 구현

01:56 AC

 

C - DPS

첫 글자 빈도수만 잘 세면 된다.

Champion B번 문제와 완전히 동일하여 그냥 복붙하였다.

01:57 AC

 

D - 효구와 호규 (Easy)

모든 카드를 없애려면 다음 조건을 만족해야 한다.

• 0 카드와 1 카드 모두 짝수 개여야 한다.
• 동일한 숫자를 가진 인접한 카드쌍이 존재해야 한다.

초기 상태에서 임의의 카드쌍을 없애면 두 개의 빈칸이 생긴다.

이 빈칸들을 이용하면 어느 카드쌍이든지 인접하게 만들 수 있다.

02:00 WA

첫 번째 조건을 확인하지 않았다.

02:01 AC

 

본래 출제자가 의도한 풀이는 비둘기집 원리라고 한다.

검수 과정에서 지문이 수정되면서 위의 풀이도 가능해졌다.

사실 Easy 버전에서는 아무런 영향이 없다.

 

E - 어려운 스케줄링

Champion F번의 약화 버전이다.

차이점으로 실시간 query가 삭제되었으며 마지막에 k개의 query를 연속하여 처리해야 한다.

Champion F번과 동일하게 두 개의 deque과 한 개의 set을 이용하여 풀이할 수 있다.

약화 버전이라서 더 간단한 풀이가 존재할 수도 있다.

복붙하고 살짝 수정하여 제출하였다.

02:04 AC

 

G - 효구와 호규 (Hard)

D번에서 없애는 방법만 추가적으로 출력하면 된다.

02:12 WA

스페셜 저지에 문제가 있어 위의 풀이는 WA를 받는다.

현재는 에디토리얼에 나온 비둘기집 원리로 풀어야 AC를 받는다.

02:22 AC

 

대회 중에는 그냥 반례가 있다고 생각하였다.

오늘 대회 운영진 분들께 여쭤보니 검수 과정에서 지문에 오류가 생겼다고 한다.

스페셜 저지가 수정될 예정이다.

 

F - 피보나치와 마지막 수열과 쿼리

여러 풀이가 존재하지만 정해 외에는 시간 제한이 빡빡하다.

 

첫 번째 풀이는 Segment Tree with Lazy Propagation

02:38 TLE

나처럼 대충 구현하면 TLE를 받는다.

업솔빙 하면서 확인한 결과 효율적으로 잘 구현하면 AC를 받는다.

 

두 번째 풀이는 set + offline query

각 인덱스에 대하여 마지막으로 수행되는 query만 중요하다는 것을 알 수 있다.

따라서 query를 반대 순서로 처리하면 된다.

이때 query를 한 번도 수행하지 않은 원소만 고려한다.

이는 set으로 판단할 수 있다.

02:44 TLE

예전에 set에 원소를 순차적으로 넣을 때 빠르게 넣는 법을 본 적이 있다.

insert 함수에 hint iterator를 제공하는 방법인데 실제로 쓸 줄은 몰랐다.

02:46 AC

여담으로 출제자는 이 풀이를 막기 위하여 노력하였다고 한다.

 

세 번째 풀이는 Union-Find + offline query

두 번째 풀이에서 query를 수행하지 않은 원소를 고려할 때 set 대신 Union-Find를 사용하면 된다.

자세한 설명은 10775번 풀이를 참고하자.

 

시간이 부족하여 뒤의 두 문제는 풀지 못하였다.

시간만 있었으면 풀 수 있었을 것 같다.

 

H - 트리 다듬기 (not solved)

25924번과 유사하다.

트리의 지름을 구한 후 그리디하게 붙여 나가면 된다.

출제자 분께서 홍보를 부탁하여 열심히 홍보하였으나 난이도가 있어서 그런지 아무도 손을 안 댔다.

 

I - 완전한 수열 리버스 (not solved)

초기 수열에는 0 하나만 존재한다.

M번의 연산을 수행하는데 i(0 <= i < M)번째 연산은 다음과 같다.

• i % 3 == 0인 경우 수열의 모든 수에 대하여 2와 xor 연산을 수행한다. 수열의 맨 뒤에 0을 추가한다.
• i % 3 == 1인 경우 수열의 맨 뒤에 2를 추가한다.
• i % 3 == 2인 경우 수열의 모든 수에 대하여 2와 xor 연산을 수행한다.

나머지 원소는 4로 채우면 된다.

이 풀이가 가장 깔끔한 것 같다.

 

끝

끝