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;
}
댓글 없음:
댓글 쓰기