2022 IOI 멘토교육 1주차

문제 셋: 2011 IOI day 2

 

실제 대회처럼 5시간 타이머를 해놓고 봤습니다.

 

0:00 ~ 0:24

일단 1번 문제부터 읽어봤습니다. 부모 정점을 고려해서 적당한 트리 dp를 돌리면 서브태스크 1을 맞출 수 있다는 강한 확신이 있었지만 구현과 디버깅을 빠르게 할 자신이 없어서 일단 보류했습니다. 서브태스크 1의 배점이 매우 높기 때문에 일반그래프를 트리로 줄이면 문제가 해결되지 않을까 하고 생각을 해봤지만 잘 되진 않았습니다. dp관점으로 생각해보면 답이 작은 정점부터 차례로 계산해나갈 수 있고, 이는 다익스트라와 동일한 발상입니다. 구현도 매우 간단하기 때문에 바로 코딩을 했고, 100점을 받았습니다.

 

다른 문제를 읽지 않고 한 문제의 100점 코드를 짠다는 것은 매우 위험한 전략이지만, 풀이가 셋을 시작한지 10분만에 나왔고 구현도 매우 간단해서 틀려도 아무 영향을 끼치지 않기 때문에 바로 100점을 받는 선택을 했습니다.

 

0:24 ~ 0:43

2번 문제를 읽어봤습니다. 매우 자명한 O(QN) 그리디 풀이가 존재하고, 이를 이용하면 서브태스크 2까지 맞을 수 있습니다. 서브태스크 3, 4, 5의 제한이 각각 50000, 70000, 150000이였고, 시간제한이 9초여서 매우 어려운 문제라는 생각이 들었습니다. 제한을 보면 루트 시간복잡도가 정해라는 추측을 할 수 있습니다.

 

3번 문제도 읽어봤습니다. 인덱스와 값을 수 하나에 같이 저장해서 보내는 방식으로 서브태스크 2까지 맞을 수 있지만, 서브태스크 3부터는 풀이가 잘 떠오르지 않았습니다. 그래서 일단 2번과 3번의 서브태스크 2 풀이를 각각 제출했고 점수를 긁었습니다.

 

0:43 ~ 1:52

2번 문제는 매우 어렵다고 판단을 했고, 루트질이 정해인 문제를 풀어본 경험이 거의 없었기 때문에 3번을 잡기로 했습니다. 수를 쪼개서 보내는 방식으로 오래 생각해보았지만 잘 되지 않아서, 일단 이론적으로 최적해가 얼마일지 계산을 해봤습니다. 256가지의 수를 전송할 수 있고, L개의 수를 순서없이 보내므로 H(256, L)이 표현 가능한 수의 개수입니다. (H는 중복조합) n이 64이하일 때, H(256, n*5) >= 2^{n*8}이 성립하기 때문에 n*5개의 수로 가능한 모든 경우를 반드시 표현할 수 있고, 이는 간단하게 구현 가능합니다(사전순으로 일대일대응). biginteger를 구현하는데 시간을 많이 썼고, 초기화를 안 해서 맞왜틀을 좀 하다가 100점을 받았습니다.

 

1:52 ~ 3:03

루트가 정해라는 확신은 있었지만 단순 버킷질이 아닐 수 있기 때문에 일단 여러 특징을 관찰하는 시도부터 했습니다. 답은 이전 쿼리랑 최대 1 차이난다는 관찰을 하긴 했지만 다른 유의미한 관찰이 나오진 않았습니다. 그래서 일단 버킷들로 쪼개고 생각을 해봤습니다. 버킷의 크기를 X라고 할 때, 버킷들로 쪼개서 각각의 버킷에서 적당한 dp를 돌려서 버킷끼리 연결할 수 있도록 하는 것은 O(X)에 전처리가 가능합니다. 전처리가 된 상태에서 답을 계산하는 것은 O((버킷개수) * logN)에 가능합니다. 버킷에서 원소를 추가/삭제하는 것은 O(X)에 가능합니다. 원소의 위치를 바꿀 때 한개의 버킷의 크기가 매우 커지는 현상이 발생할 수 있는데, 이는 루트번마다 전체 버킷을 rebuild하는 방식으로 간단하게 해결 가능합니다. 이를 구현하면 루트로그 시간복잡도로 100점을 받을 수 있습니다.