2016년 3월 15일 화요일

JOI 2015/2016 qualifying round

JOI 2016 예선
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(N^{3}M)$
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 로 두고 다익스트라를 사용했다.
마지막 마을은 숙박비를 제외한다.


문제 #4 소스

#include <bits/stdc++.h>
using namespace std;

typedef long long lld;

int main(){
    lld a[100002], T;
    char sig[100002];
    int i, j, n, q;
    scanf("%d %lld %d", &n, &T, &q);
    for(i=1; i<=n; ++i){
        char c;
        scanf("%lld %c ", &a[i], &c);
        sig[i] = c=='1'?1:-1;
    }
    lld r[100002]={};
    bool freeze[100002]={};
    r[1] = a[1] + (sig[1]*T);
    for(i=2; i<=n; ++i){
        r[i] = a[i] + (sig[i]*T);
        if(r[i-1] > r[i]){
            lld cur = (r[i-1]+r[i])/2;
            r[i] = cur;
            freeze[i] = true;
            for(j=i-1; j>=0 && r[j] >= cur; --j){
                if(freeze[j]){
                    r[i] = r[j];
                    break;
                }
                r[j] = cur;
                freeze[j] = true;
            }
        }
    }
    
    while(q--){
        int k;
        scanf("%d", &k);
        printf("%lld\n", r[k]);
    }
    return 0;
}

문제 #5 소스

#include <bits/stdc++.h>
using namespace std;

#define INF 98765432109

#define VISITED 1
#define NOT_VISITED 0
#define HOST -1

typedef long long lld;
typedef pair<lld,lld> ii;

lld dijkstra(vector<ii> adj[], int n, int s, int e){
    vector<lld> cost(n, INF);
    priority_queue<ii> q;
    q.push({0, s});
    cost[s] = 0;
    while(!q.empty()){
        lld pos = q.top().second;
        lld dist = -q.top().first;
        q.pop();
        
        for(int i=0; i<adj[pos].size(); ++i){
            ii& next = adj[pos][i]; /* (next, weight) */
            if(dist + next.second >= cost[next.first]) continue;
            q.push({-(dist+next.second), next.first});
            cost[next.first] = dist+next.second;
        }
    }
    return cost[e];
}

int main(){
    int n, m, k, s;
    lld p, q;
    scanf("%d %d %d %d %lld %lld", &n, &m, &k, &s, &p, &q);
    vector<int> a[n];
    queue<int> infect;
    char infection[100001]={};
    while(k--){
        int v;
        scanf("%d", &v);
        infect.push(v-1);
        infection[v-1] = HOST;
    }
    while(m--){
        int s, e;
        scanf("%d %d", &s, &e);
        a[s-1].push_back(e-1);
        a[e-1].push_back(s-1);
    }
    for(int i=0; i<n; ++i) sort(a[i].begin(), a[i].end());
    
    int dist = 0;
    while(!infect.empty() && dist++ < s){
        int qs = infect.size();
        while(qs--){
            int cur = infect.front();
            infect.pop();
            for(int i=0; i<a[cur].size(); ++i){
                if(infection[a[cur][i]] == NOT_VISITED){
                    infection[a[cur][i]] = VISITED;
                    infect.push(a[cur][i]);
                }
            }
        }
    }

    vector<ii> adj[n];
    for(int i=0; i<n; ++i){
        for(int j=0; j<a[i].size(); ++j){
            if(infection[ a[i][j] ] == HOST){
                adj[i].push_back({a[i][j], INF});
            } else {
                adj[i].push_back({a[i][j], infection[ a[i][j] ]?q:p});
            }
        }
    }

    printf("%lld", dijkstra(adj, n, 0, n-1) - (infection[n-1]?q:p));
    
    return 0;
}
댓글 쓰기

게시글 목록