Joonas' Note

Joonas' Note

JOI 2015/2016 qualifying round 본문

알고리즘/문제 풀이

JOI 2015/2016 qualifying round

2017. 10. 29. 16:13 joonas

    [이전 블로그로부터 글 옮김]


    Online Judge: https://www.acmicpc.net/contest/view/152

    크롬에서 한국어 번역 기능을 써서 문제를 읽었다. 문장이 이상하면 영어로 번역했다.

    문제 #1. 科目選択

    (물리, 화학, 생물, 지구과학) 중 상위 점수 3개 + (역사, 지리) 중 상위 점수 1개
    두 묶음을 나눈 뒤 정렬하고 더함.

    문제 #2. ゼッケンの交換

    문제에서 설명한대로 구현하면 정답.
    a[j] mod k > a[j+1] mod k 이면 자리를 바꾼다. k를 2부터 m까지 진행한 후 배열 a의 상태를 출력한다.

    문제 #3. ロシアの旗

    주어진 국기를 러시아 국기의 형태로 바꿔야하는 데, 최소 몇 개의 칸의 색깔을 바꿔야 하는 지 출력하는 문제이다.

    위에서부터 (흰색, 파란색, 빨간색) 의 형태이여야한다. 나올 수 있는 모든 경우를 만들어보고 최소값을 갱신했다. O(N3M)
    N이 작아서 괜찮다.

    나올 수 있는 모든 경우는 [0, i) 이 흰색 / [i, j) 이 파란색 / [j, n) 이 빨간색 구간인 것이다.
    매 경우마다 N*M만큼 돌면서 색이 다른 칸의 수를 셈.

    문제 #4. JOI国のお散歩事情

    개미 문제처럼 사람들의 위치와 진행 방향이 주어지면 T 초 후 Q 사람들의 위치는 어디인가 묻는 문제이다. (사람들은 위치가 겹치면 그 자리에서 멈춘다.)

    i번째 사람에게서 진행 방향에 따라 -T 혹은 +T 를 한 것이 그 사람의 T초 후의 위치일 것이다. i번째 사람의 나중 위치가 i-1번째 사람보다 앞서있다면 둘은 충돌한다는 것이다. 그럼 두 사람이 멈추는 위치는 (a[i]+a[i-1])/2. 그리고 이 위치로부터 더 이전 (i-1번째보다 더 이전) 에 있던 사람들도 이 위치에서 멈춰야하므로 모두 다시 갱신한다.

    문제 #5. ゾンビ島

    N개의 마을 중 K개 마을은 좀비에게 지배되었고 K개의 마을로부터 S개 이하의 도로만큼은 숙박 요금이 다르게 적용된다. - 정확히는 요금 Q를 적용, 그 외에는 요금 P를 적용 - (단, 좀비에게 지배된 K개의 마을은 지날 수 없다), 그리고 마을을 지날때마다 숙박 요금(P 또는 Q)를 낸다.
    1번 마을로부터 N번 마을까지 가는 최소의 숙박 비용을 구하는 문제이다.

    BFS로 K개 마을로부터 S개 이하의 도로(주변 거리라고 생각하면 됨)로 갈 수 있는 마을은 요금 Q를 적용한다.

    노드마다 가중치를 두고 최단경로 알고리즘을 사용하면 된다.
    노드에 가중치를 둘 줄 몰라서(!) 안전한 마을->위험한 마을 = Q, 위험한 마을>안전한 마을 = P 로 두고 다익스트라를 사용했다.
    마지막 마을은 숙박비를 제외한다.



    Comments