[editorial] SRM 368 DIV 1 후기

  • legend12
    legend12

    10월 2일 20시에 있었던 SRM368 의 DIV 1 결과 입니다~ (상위10명 + 150등 이내 한국인 + Petr)
    standing.jpg
    Problem-setter 는 misof 였으며, Winner 의 점수가 1000점이 안될정도로 참가자들을 안드로메다로 보내버린 SRM 이었습니다;;
    오죽하면 Petr 의 등수가 저렇겠습니까 -0-

    Easy (250 pts.)

    • 문제설명 : 2차원의 보드가 주어지고 각 점에는 1~9 의 숫자 또는 H 라는 문자가 적혀있다. 여기서 H 는 구멍(hole)을 뜻한다. 말은 위, 아래, 왼쪽, 오른쪽 네방향으로 현재 위치해있는 점에 적혀있는 숫자만큼 이동을 할 수 있으며, 말이 구멍에 위치하거나 보드 밖으로 나가게 되면 게임이 끝나게 된다. 좌측상단에 처음 말이 놓여있다고 할때 말을 최대한 많이 이동했을 때의 횟수를 구하여라. (단, 무한히 움직일 수 있다면 -1 로 표현한다.)
      • 해결방법 : BFS 로 n( > 0) 번 이동했을 때 도달할 수 있는 위치를 저장하면서 더이상 진행하지 못할 때까지 루프를 돈다. 단 n >= row * col 일때는 비둘기집의 원리에 의하여 이미 한번 방문한 곳을 다시 방문할 수 밖에 없다. 따라서 n >= row * col 일 때는 -1 을 되돌려 주면 된다.

    Medium (500 pts.)

    • 문제설명 : 여러개의 선분들이 연속되어 연결되있는 것을 polyline 이라고 한다. 이 polyline 이 서로 교차하는 점이 있을 경우 하나의 이미지로 인식된다. 이 때, 주어진 polyline 들로 만들어지는 이미지의 갯수를 구하여라.
      • 해결방법 : polyline 들 간의 교차여부를 확인한 후에 union-find 를 통해서 그룹의 갯수를 세면 된다. 두 개의 polyline 의 교차는 각 polyline 에 속해있는 선분들 간의 교차를 확인하여 하나라도 교차하는 경우가 있으면, 두 개의 polyline 은 교차하는 것이다. 선분간의 교차는 CCW 함수와 예외 케이스 하나를 처리해주면 쉽게 해결된다. [code c++] int ccw(point pa, point pb, point pc) { return (pa.x - pb.x) * (pb.y - pc.y) - (pb.x - pc.x) * (pa.y - pb.y); } bool InLine(line l, point p) { if (min(l.pa.x, l.pb.x) <= p.x && p.x <= max(l.pa.x, l.pb.x) && min(l.pa.y, l.pb.y) <= p.y && p.y <= max(l.pa.y, l.pb.y)) return true; return false; } bool Intersect(line la, line lb) { int c1 = ccw(la.pa, la.pb, lb.pa), c2 = ccw(la.pa, la.pb, lb.pb); int c3 = ccw(lb.pa, lb.pb, la.pa), c4 = ccw(lb.pa, lb.pb, la.pb); if (c1 == 0 && c2 == 0 && c3 == 0 && c4 == 0) { if (InLine(la, lb.pa) || InLine(la, lb.pb) || InLine(lb, la.pa) || InLine(lb, la.pb))) return true; return false; } if (c1 * c2 <= 0 && c3 * c4 <= 0) return true; return false; } [/code]
        [이 글은 과거 홈페이지에서 이전된 글입니다. 원문보기]

    11년 전
6개의 댓글이 있습니다.
  • JongMan
    JongMan

    오오 스탱 오오~ 오오 스탱 오오~


    11년 전 link
  • astein
    astein

    Sys Fail 두개... ㅇ<-<


    11년 전 link
  • JongMan
    JongMan

    안드로 가도 온사이트 커트라인 48위로 안드로 가는 스탱님..


    11년 전 link
  • lazyboy
    lazyboy

    250 pt의 다른 해법은 DFS & memoization.
    D[i][j] = i열 j행에서 시작했을 때 최대 가능 move 수를 구합니다.
    만약 DFS 탐색 중 back edge가 생기면 D[i][j] = infinite.
    그렇지 않은 경우 D[i][j] = max({D[ni][nj] + 1 | (ni, nj) ∈ (i,j)에서 이동가능한 셀들})
    그리고나서 D[0][0] 이 infinite이면 -1을 출력합니다. :)
    젠장스럽게 back edge 체크를 위한 visited toggle을 실수해서 안드로로..


    11년 전 link
  • 정상인
    정상인

    저도 DFS & memoization 으로 했는데
    D[i][j] 랑 marked[i][j] 를 모두 둬서 D[i][j] 가 아직 채워넣지 않았는데 marked면 -1을 리턴 으로 ..
    주의할 점은 D[i][j]를 갱신하는 건 D[i][j]에서 갈 수 있는 곳을 모두 가 본 후에 해야 한다는 것?


    11년 전 link
  • legend12
    legend12

    사실.. 대회끝나고 연습방에서 푼건 DFS 로 풀었음 -0- 저건 astein 소스를 참조한...;;
    BFS 랑 DFS 둘다 시스테스트 돌려보니 DFS 가 훨씬 빨라서 ㅎㄷㄷ


    11년 전 link
  • 정회원 권한이 있어야 커멘트를 다실 수 있습니다. 정회원이 되시려면 온라인 저지에서 5문제 이상을 푸시고, 가입 후 7일 이상이 지나셔야 합니다. 현재 문제를 푸셨습니다.