Zero One Algorithm Contest 2022 Open Contest

Zero One Algorithm Contest 2022 Open Contest

A - ZOAC 5

단순 구현

00:01 AC

 

B - 전투의 신

수학

00:05 AC

 

C - 황금 칵테일

map<string, int>와 map<int, int>

00:09 WA

map 사용이 미숙하였다.

존재하지 않는 key에 [] 연산자를 사용하면 (key, default value) pair가 삽입되므로 주의해야 한다.

00:13 AC

 

D - 이 사람 왜 이렇게 1122를 좋아함?

이분 탐색

00:18 WA

중간에 답이 정해지더라도 마지막까지 모순이 생기지 않는지 확인해야 한다.

00:29 AC

 

E - 색종이와 공예

ㄱ자 모양이 등장하는지 확인하면 된다.

각 좌표당 4번씩만 검사하면 flood fill 없이 해결할 수 있다.

00:36 AC

 

H - 가장 작은 수

p, p^2, p^4, p^8, ... 중에서 가장 작은 수를 사용하면 된다.

00:54 AC

 

K - 순열 구하기

마지막 수부터 역순으로 보면 각 수는 유일하게 결정된다.

N개의 배열 A_i를 잘 관리하면서 P_i를 하나씩 복원하면 된다.

01:18 MLE

배열을 set으로 구현하였더니 MLE를 받았다.

deque<bool>로 수정하여 제출하였다.

01:23 AC

 

문제의 절차를 역순으로 수행하면 더 간단하게 풀 수 있다.

이때 N개의 배열을 모두 관리하지 말고 하나의 배열만 관리하자.

현재 A_i를 가지고 있다면 P_i를 복원함과 동시에 A_(i - 1)을 얻을 수 있다.

시간 복잡도는 위의 풀이와 동일하게 O(N^2)이지만 매우 빠르게 돌아간다.

 

F - 용 조련사 룰루

용들을 힘이 큰 순으로 정렬하자.

이때 0 < i < 4인 i에 대하여 P_(i + 1) - P_i 중 하나라도 M을 초과하면 학살이 일어난다.

그렇지 않다면 3번 용부터 N번 용까지 옮기고 2번 용과 1번 용을 옮기면 된다.

02:03 AC

 

J - 사기 주사위

next_permutation으로 모든 주사위를 완전 탐색하면 된다.

각 주사위마다 가능한 조합은 8가지인데 3d 시뮬레이션 사이트를 이용하면 쉽게 찾을 수 있다.

02:20 AC

 

M - 이게 게임이냐?

그래프 탐색 문제로 변형할 수 있다.

02:36 MLE

queue에 동일한 상태가 여러 번 들어가 MLE를 받았다.

서로 다른 상태에서 동일한 상태로 갈 수 있음에 유의해야 한다.

02:44 WA

02:48 WA

3 * N^4개의 상태를 정의하였는데 상태 전이가 조금 꼬였다.

02:53 TLE

동일한 종류의 더미의 경우 순서는 중요하지 않다.

순서를 정렬하면 본질적으로는 동일하지만 서로 다른 표현형을 합쳐서 관리할 수 있다.

02:55 AC

 

여담으로 현재 최악의 경우에 대한 데이터가 없어서 잘못된 풀이가 통과되고 있다.

 

G - map, filter (not solved)

+ 연산과 * 연산은 변수 a와 b를 관리하면 된다.

+ 연산은 b += x로 수행할 수 있으며 * 연산은 a *= x와 b *= x로 수행할 수 있다.

% 연산은 효율적으로 처리할 방법이 보이지 않는다.

여기서 x 제한이 매우 작다는 점을 이용해야 한다.

 

첫 번째 % 연산은 실제로 모듈러 연산을 수행하면 된다.

연산이 종료되면 배열의 모든 원소는 x 미만이 된다.

따라서 두 번째 연산부터는 최대 100개의 원소만 관리하면 된다.

 

filter 명령도 % 연산의 수행 여부에 따라 동작이 달라진다.

% 연산이 일어나지 않은 경우에는 이분 탐색이 필요하다.

% 연산이 일어난 후부터는 마찬가지로 최대 100개의 원소만 순회하면 된다.

 

I - 인생은 B와 D 사이의 C다. (not solved)

0 < i < 34인 i에 대하여 높이가 i인 포화 이진 트리를 모두 만들어보면 된다.

수학적으로 계산해보면 높이가 34 이상인 경우는 최적이 될 수 없음을 알 수 있다.

각 정점의 비용은 말단 정점인 경우 0이 되며 그렇지 않다면 2개의 자식 서브트리를 만드는 최소 비용이 된다.

새롭게 서브트리를 만들 수도 있고 기존 서브트리를 뚝딱뚝딱 고칠 수도 있다.

 

L - 형광펜 강민우 (not solved)

flow 문제처럼 보이지는 않았는데 flow 문제였다.

Max-flow min-cut theorem에 의하여 최소 비용은 max flow가 된다.

민우의 건물에서 현수막을 볼 수 있는지 판단하는 부분이 까다롭다.

이는 민우의 건물과 인접한 간선 e에 대하여 다음을 확인하면 된다.

• e를 제거하였을 때의 max flow가 (기존 max flow - e의 가중치)가 된다면 e는 min cut을 구성하는 간선이다.
• 이를 만족하는 e가 존재하지 않으면 민우의 건물에서는 현수막을 볼 수 없다.

의문의 WA를 많이 받았다.

flow 문제를 너무 오랜만에 풀다 보니 라이브러리 사용법을 잊어버렸다.

무향 그래프를 실수로 유향 그래프로 만들어버리고 반례만 계속 찾고 있었다.

 

끝

끝