AI Network Scholarium I

AI Network Scholarium I

서론

Hello BOJ의 악몽이 떠오르는 대회였다.

 

A - On My Way Dorm

출근 커맨드를 역순으로 출력하면 된다.

예제 입력이 이해가 잘 안돼서 조금 늦게 풀었다.

00:12 AC

 

B - aFan Event Planning

누적 합 + set

00:17 WA

사소한 구현 실수가 있었다.

00:19 AC

 

C - Appearance of the Runo (not solved)

포함 배제로 풀릴 듯 하면서도 너무 복잡해 보여서 포기하였다.

그런데 정해는 포함 배제가 맞았다.

매우 복잡한 포함 배제가 정해였다.

 

3주 전에 업솔빙하면서 풀이를 예쁘게 정리하여 test.txt 파일로 저장해놓았다.

그런데 test.txt라는 이름 때문에 디버깅용 파일로 착각하고 그만 삭제해버렸다.

그래서 그냥 대강 작성한다.

 

주어진 정보로 그래프를 구성하자.

각 조합에 대하여 2^6 = 64가지의 경우가 가능하지만 다음과 같이 11가지로 줄일 수 있다.

나의 편의를 위하여 간략히 묘사하였다.

1. 간선 0개
2. 간선 1개
3. 간선 2개, 일자형
4. 간선 2개, 분리형
5. 간선 3개, 일자형
6. 간선 3개, 트리형
7. 간선 3개, 사이클
8. 간선 4개, 길이 4 사이클
9. 간선 4개, 길이 3 사이클
10. 간선 5개
11. 간선 6개

포함 배제 계수는 (-1)^(간선의 개수)가 된다.

 

계산에 앞서 주어진 정보로 전처리를 해주자.

나의 편의를 위하여 자세한 설명은 생략한다.

• vector<int> G[5][3001][5];
• vector<ii> H[5][5];
• bitset<3001> A[5][3001][5];

이제 각 경우를 다음과 같은 시간 복잡도로 계산할 수 있다.

1. 간선 0개 -> O(1)
2. 간선 1개 -> O(1)
3. 간선 2개, 일자형 -> O(N)
4. 간선 2개, 분리형 -> O(1)
5. 간선 3개, 일자형 -> O(M)
6. 간선 3개, 트리형 -> O(N)
7. 간선 3개, 사이클 -> O(M^2)
8. 간선 4개, 길이 4 사이클 -> O(N^2 + NM)
9. 간선 4개, 길이 3 사이클 -> O(M^2)
10. 간선 5개 -> O(M^2)
11. 간선 6개 -> O(M^2)

더 빠르고 간단하게 푸는 방법도 있는 것 같은데 원리는 잘 모르겠고 나는 이 정도에서 만족하려고 한다.

 

D - Singularity of the Nim (not solved)

1번째 칸의 코인 개수는 다음과 같이 변화한다.

• 1번째 칸에서 코인을 가져오면 1~P개만큼 감소한다.
• 그 외의 칸에서 코인을 가져오면 1~P개만큼 증가한다.

따라서 C1이 (P + 1)의 배수이면 후공이 승리하고 그렇지 않다면 선공이 승리한다.

 

E - 111111111111111 (not solved)

제한이 상당히 사악하기 때문에 매우 효율적으로 풀어야 한다.

기본적으로 xor basis에 대하여 알고 있어야 한다.

자세한 풀이는 생략하며 아이디어만 간단히 설명하고자 한다.

• N은 최대 111이지만 basis의 최대 개수는 47개이다.
• 따라서 basis가 추가되는 경우에만 답을 갱신하면 된다.
• basis의 개수를 b라고 하자.
• b < 24일 때는 brute force로 처리할 수 있으며 시간 복잡도는 O(b * 2^b) 또는 O(2^b)이 된다.
• b >= 24일 때는 dp로 처리할 수 있으며 시간 복잡도는 O(b * 2^(47 - b))이 된다.

여기까지만 처리하면 TLE를 받는다.

dp를 조금 더 효율적으로 할 수 있는 방법이 있는데 비트 순서를 잘 조정하면 이전의 dp 테이블을 재활용할 수 있다.

이 방법을 이용하면 b > 24일 때 O(2^(47 - b))의 시간 복잡도로 처리가 가능해진다.

 

수상만 하고 빨리 탈출하자.

여기는 내 길이 아니다.

 

F - Decision Tree (not solved)

Pass

 

G - MiniEgg MiniGame (not solved)

Pass

 

끝

끝