글 위치가 적절치 않으면 옮겨주세요. 후기에 써야 하나 여기에 써야 하나 고민..
SRM 368은 제 세번째 SRM이었습니다. 바로 지난 SRM 367 DIV 1에서 -50.00을 기록하며 고향별 안드로메다에 갔었거든요. 그래서 이번엔 DIV 2에 참가하게 되었습니다.
10위권 안에는 한국인으로 저 ryuwonha, normit, plum101 이렇게 세 명이 있네요. 레이팅이 오르긴 올랐는데 하필이면 딱 1199에 걸린 karthik123이 불쌍할 따름입니다 :'(
Easy problem (300 pts.)
문제
원점에서부터 주어진 순서에 따라 이동하였을 때 원점과 최종 위치의 euclidean distance를 구하는 것이 목적. 이동은 방향과 거리로 주어지며, 방향은 8방향 (EAST, WEST, NORTH, SOUTH, SOUTHWEST, SOUTHEAST, NORTHWEST, NORTHEAST)으로 주어지고 거리는 항상 정수로 주어진다.
풀이
떠올리기가 어려워서 못 푸는 문제는 아니라고 보고, 어떻게 하면 짧은 코드로 고득점을 할 수 있을지 고려해보면 제 생각에 가장 좋은 방법은 string을 key로 하는 map을 만들어서 EAST => 0, NORTHEAST => 45 degree, ... 와 같은 식으로 mapping해놓고 쭉 더해나가는 것이 가장 빠를 것 같습니다.
floating point operation으로 인한 오차를 문제에서 1e-9 이내(상대 오차, 절대 오차)로 인정하고 있는데요, 무식하게 매 번 계산하더라도 1e-13? 정도의 오차밖에는 발생하지 않기 때문에 걱정하지 않아도 될 것 같습니다.
Medium problem (500 pts.)
문제
R*C boolean matrix가 주어질 때, (0, 0) - (i, j) 까지의 직사각형 영역에 xor 연산을 수행하는 것을 1회의 연산이라고 할 때, 전체 matrix를 1로 채우기 위한 최소 연산은?
풀이
같은 위치에 두 차례 이상의 연산은 당연히 무의미하니까 제외하고 나면, '최소 연산'이 곧 '유일한 연산'이 됩니다.
(r, c)라는 위치에 0이 있다고 합시다. 이 때 (r, c)를 제외한 (r, c) - (R-1, C-1) 직사각형 영역이 전부 1로 채워져 있다면 (r, c)를 1로 만들 수 있는 방법은 (0, 0) - (r, c)에 연산을 수행하는 방법 뿐입니다. 그렇지 않다면, 즉 0이 존재한다면 일단 걔네들부터 처리하고 봐야겠죠.
그래서 오른쪽 아래에서부터 쭉 탐색을 합니다. 0이 발견되면 그 위치로부터 오른쪽 아래의 영역에는 전부 1로 채워져 있으므로 그 칸에 대한 연산을 수행하면 됩니다.
Hard problem (900 pts.)
문제(legend12님 설명 인용)
2차원의 보드가 주어지고 각 점에는 1~9 의 숫자 또는 H 라는 문자가 적혀있다. 여기서 H 는 구멍(hole)을 뜻한다. 말은 위, 아래, 왼쪽, 오른쪽 네방향으로 현재 위치해있는 점에 적혀있는 숫자만큼 이동을 할 수 있으며, 말이 구멍에 위치하거나 보드 밖으로 나가게 되면 게임이 끝나게 된다. 좌측상단에 처음 말이 놓여있다고 할때 말을 최대한 많이 이동했을 때의 횟수를 구하여라. (단, 무한히 움직일 수 있다면 -1 로 표현한다.)
풀이
http://algospot.com/zbxe/openlecture/911 에 여러 풀이가 이미 제시되어 있지만, 저는 저런 풀이가 저어어언혀 생각나지 않았습니다-_-;;
제가 이 문제를 풀이한 방법은 Bellman-Ford인데요, Bellman-Ford가 음수 가중치를 가진 엣지들 사이에서도 아주 잘 작동한다는 데 착안한 방법입니다.
이동할 수 있는 모든 엣지를 -1의 가중치로 저장하고 최단경로를 구하면 됩니다. Bellman-Ford는 음수 사이클이 존재하는지 검출해주니 무한히 많이 움직일 수 있는 위치도 찾아낼 수 있겠죠.
System Test 데이터 중 제 코드로 가장 오래 걸리는 게 대략 140ms였고, 나머지는 70ms 이내였던 것으로 기억합니다. 다른 방법에 비해서는 느린 편이지요. 하지만 확실히 말릴 염려가 없다는 점에서 강력한 방법이라고 생각합니다.
후기
저희 방에 챌린지 당한 문제 수가 5개이고, 시스템 테스트 실패한 문제 수가 0개입니다.-_-;; 그 챌린지 5개는 전부 제가 한 거고, 전부 900점짜리 문제를 같은 데이터
"123456789H123456789H123456789H123456789H123456789H"
"23456789H123456789H123456789H123456789H123456789H1"
"3456789H123456789H123456789H123456789H123456789H12"
"456789H123456789H123456789H123456789H123456789H123"
..
로 공격했던 결과입니다. 위 데이터의 경우 Time-out도 위험하고, 특히 이 문제를 실패하신 많은 분들의 실수였던 DFS에서 방문 확인을 풀지 않음으로써 싸이클이 존재한다고 잘못 판정하는 경우도 걸러줍니다. (22스텝이던가로 유한합니다-_-;;)
그러니까 다시 말하면 "2214"와 같은 데이터를 DFS로 naive하게 풀 경우 1에서 두칸 뛰어 3으로, 3에서 1칸 뛰어 4로 가서 방문 확인을 하고 되돌아와서 1칸 왼쪽으로 뛰어 2로 갔다가 2칸 오른쪽으로 뛰면, 방문 확인을 풀지 않은 경우 싸이클이 존재한다고 판정하게 되는 것이죠.
-_-경악스러운 것은 이 hard 문제가 DIV1 easy였다는 점..
와, Bellman-Ford 풀이는 정말 참신하네요. Negative cycle detection 하는 데 쓰는 알고리즘이라도 가져다 쓸 수 있다는게 인상적입니다. Division win 축하해요~! ^^
덧) 글고 후기성이더라도 문제에 대한 해설이 있다면 open lecture 에 가는 것을 원칙으로 하도록 하겠습니다. ^^
Being
16년 전