JOI 2015/2016 qualifying round

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

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)$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 로 두고 다익스트라를 사용했다.
마지막 마을은 숙박비를 제외한다.

	#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;
	}

view raw 4. JOI国のお散歩事情.cpp hosted with ❤ by GitHub

	#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;
	}

view raw 5. ゾンビ島.cpp hosted with ❤ by GitHub