블로그 이사 중입니다 >> gumgood.github.io

COCI 2006/2007 contest #1 풀이 본문

Problem Solving/주제별 풀이

COCI 2006/2007 contest #1 풀이

gumgood 2019. 1. 31. 17:57

COCI(Croatian Open Competition in Informatics) 2006/2007 contest #1

https://www.acmicpc.net/category/detail/108

1. BOJ 3052 나머지


각 나머지에 대해 marking 해놓는다.



2. BOJ 3053 택시 기하학


유클리드 기하에서의 원 넓이는 \(\pi r^2\)

택시 기하에서의 원의 넓이는 \(2 r^2\) (한 변의 길이가 \(\sqrt{2} r\)인 정사각형 모양)



3. BOJ 3054 피터팬 프라임


구현



4. BOJ 3055 탈출


문제를 보고 BFS를 떠올릴 수 있다. 다음 시간에 물이 찰 예정인 칸으로 고슴도치는 이동할 수 없다.
따라서 BFS과정에서 물이 먼저 움직이고 고슴도치가 움직이면서 탈출할 수 있는지를 체크한다.
'먼저 움직인다'는 것은 BFS에서 queue에 먼저 들어가는 것과 같다. \(O(RC)\)



5. BOJ 3056 007


bitmask + dp
0 ~ n-1번 요원 순으로 미션을 할당 받는다고 하자. 0 ~ i-1번 요원까지 미션을 할당 받았을 때,
\(i\)번 요원은 남은 미션들 중 하나를 수행하게 된다. 이를 일반화 시켜서 다음과 같이 정의한다.

\(dp[i][state]\) = \(0\)부터 \(i\)번 요원이 할당받은 임무목록이 \(state\)일 때, 이를 성공적으로 끝낼 확률

임무 목록 \(state\)는 포함된 임무들에 해당하는 비트를 켜서 bitmask한 것이다. 생각해보면 \(i\)는 필요 없는 정보인 것을 알 수 있는데 \(state\)를 bit masking해서 표했했을 때, (켜진 bit 수) = \(i\)이다. 즉, \(state\)만으로 몇 명의 요원까지 미션을 할당받았는지 알 수 있으므로 다음과 같이 다시 정의할 수 있다.

\(dp[state]\) = 임무목록 state를 요원들이 번호순으로 미션을 할당 받았을 때, 이를 성공적으로 끝낼 확률

이때, 미션 한 개를 더 수행했을 때 \(state\)가 되는 목록을 \(prev\)라고 하자.  이 미션의 순서가 \(i\)번째, 할당받을 요원의 순서가 \(j\)번째라면 다음과 같은  점화식을 얻을 수 있다.

\(dp[state] = \underset{bit \in \forall prev}{\max}(dp[bit] *  p[i])\)


6. BOJ 3057 디버그 / BOJ 1751 디버그


 어떤 정방행렬에 대해서 180도 회전시켜보고 같은지를 확인해야 한다. \(N = \min(R,C)\)라 하면, 모든 좌표에 대해 정방행렬은 최대 \(N\)개 존재할 수 있으므로 검사해야 할 정방행렬은 \(O(N^3)\)개 존재한다. 각 정방행렬을 돌려서 비교하는데 \(O(N^2)\)으로 합쳐서 \(O(N^5)\)에 TLE를 받을 수 있다.  스퀘어 킬러인지를 확인하는 연산을 얼마나 최적화시켜야 한다.
 크기가 \(k\)인 정방행렬이 '스퀘어 킬러'라면 테두리를 제외한 크기가 \(k\)-\(2\)인 정방행렬 또한 '스퀘어 킬러'여야 한다. 거꾸로 말하면 크기가 \(k\)인 정방행렬이 '스퀘어 킬러'일 때 이를 감싸는 테두리가 180도 돌려도 같다면 크기가 \(k+2\)인 정방행렬이 존재한다. 즉, 각 정방행렬에 대해 '스퀘어 킬러'인지 아닌지를 저장해두고 테두리만 확인해주면 \(O(N)\)에 정방행렬인지 판별이 가능하다.
어떤 정방행렬의 위치에 대한 기준을 가장 아래쪽 & 오른쪽에 있는 원소의 좌표로 정하고, 다음과 같이 정의하자.

\(dp[x][y][k]\) =  기준이 좌표\(x,y\)이고 크기가 \(k\)인 정방행렬이 스퀘어 킬러이다 \((bool)\)

 테두리를 확인하는 함수를 이렇게 정의하면,

 \(cmp(i,j,k)\) = \(dp[x][y][k]\)에 해당하는 행렬의 테두리가 '스퀘어 킬러'의 조건을 만족한다. \((bool)\)

 다음과 같은 점화식을 얻을 수 있다.

\( dp[x][y][k] = dp[x-1][y-1][k-2] \land cmp(i,j,k)\)

 모든 원소가 0 또는 1이고, 테두리만 확인하면 되므로 60개 단위로 잘라 64bit 자료형에 넣고 bitwise로 비교 연산할 수 있다. \(N\)은 최대 300 이므로 가로 세로 합쳐 5+5번의 비교연산을 하면 되므로 \(cmp\) 함수는 \(O(1)\)에 수행될 수 있다. 따라서 가능한 모든 정방행렬 \(O(n^3)\)에 대해 \(O(1)\)만에 '스퀘어 킬러'를 판별할 수 있으므로 전체 시간복잡도 \(O(n^3)\)에 풀 수 있다.

※ 3057번과 1751번의 차이는 크기가 1인 정방행렬을 스퀘어킬러로 볼 것인가 아닌가의 차이

Tag
, ,
0 Comments
댓글쓰기 폼