[2017-09-25] Codeforces Round #436 (Div. 2)

링크 : http://codeforces.com/contest/864

문제도 쉬웠고 잘 풀려서 프리테스트까지는 14~5등 정도였는데 C번에서 진짜 멍청한 실수를 해가지고 시스템 테스트에서 나가는 바람에 153등으로 미끄러졌다 ㅠㅠ 바로 퍼플 다시 복귀할 좋은 찬스였는데 참 아쉽. 코드포스는 할 때마다 내가 참 주의성 부족하게 코드를 짠다는 걸 느끼게 된다. 좀 더 엄밀하게 코드 테스트하는 습관을 들여야하는데...

A. Fair Game

문제 설명에 충실하게 짜기만 하면 된다.

	#include <stdio.h>
	#include <vector>
	#include <queue>
	#include <algorithm>
	#include <iostream>
	#include <string>
	#include <bitset>
	#include <map>
	#include <set>
	#include <tuple>
	#include <string.h>
	using namespace std;
	using i64 = long long int;
	using ii = pair<int, int>;
	using ii64 = pair<i64, i64>;
	int main()
	{
	int n;
	scanf("%d", &n);
	map<int, int> m;
	for (int i = 0; i < n; i ++)
	{
	int k;
	scanf("%d", &k);
	m[k]++;
	}
	if (m.size() == 2 && (m.begin()->second) == (++m.begin())->second)
	{
	printf("YES\n");
	printf("%d %d", m.begin()->first, (++m.begin())->first);
	}
	else
	{
	printf("NO");
	}
	return 0;
	}

view raw A.cpp hosted with ❤ by GitHub

B. Polycarp and Letters

이 문제도 그냥 맨 앞에서부터 주어진 문자열 따라가면서 문제 조건에 따라 처리해주면 그리 어렵지 않게 해결할 수 있다. A번도 그렇고 B번도 그렇고 요런 문제들은 풀이를 어떻게 설명해야 할 지... 차라리 코드로 보는게 풀이 이해가 더 빠를 것 같다.

	#include <stdio.h>
	#include <vector>
	#include <queue>
	#include <algorithm>
	#include <iostream>
	#include <string>
	#include <bitset>
	#include <map>
	#include <set>
	#include <tuple>
	#include <string.h>
	using namespace std;
	using i64 = long long int;
	using ii = pair<int, int>;
	using ii64 = pair<i64, i64>;
	int main()
	{
	int n;
	scanf("%d", &n);
	set<char> s;
	string str;
	cin >> str;
	str.push_back('A');
	int ans = 0;
	for (auto& c : str)
	{
	if (c >= 'a' && c <= 'z')
	s.insert(c);
	else
	{
	ans = max<int>(ans, s.size());
	s.clear();
	}
	}
	printf("%d", ans);
	return 0;
	}

view raw B.cpp hosted with ❤ by GitHub

C. Bus

주유소를 최대한 적게 써서 주어진 횟수만큼 왕복 가능한 지를 물어보는 문제인데, 왕복 불가능할 만큼 기름이 적게 남을 데까지는 주유 안하다가 왕복 불가능할 만큼 기름이 적게 남게 되면 그 때 채워주는 걸 반복해주면 된다. 왔다갔다하는 거리에 비례해서 기름이 소모되고 주유소 위치가 정해져 있기 때문에 이 주유소 그냥 지나치면 다음에 다시 돌아올 수 있는지 판별하는 건 간단한 수식 계산으로 쉽게 알 수 있고, 전체 k번 순회를 해야하기 때문에 k번 반복문 돌면서 똑같은 계산 시뮬레이션 해주면 되는데, k상한이 10000 밖에 안 되기 때문에 시간 안에 답이 잘 나온다. 

처음에 분명히 생각했던 예외 케이스였음에도 불구하고 풀면서 빼먹어가지고 시스템 테스트에서 틀렸다. ㅠㅠ 남들 코드 핵한다고 나서기 전에 내 코드부터 핵하고 락걸자 라는 생각이 들었다. 시스템 테스트에서 나간 거 보자마자 코드 다시 보니 바로 어디서 틀린 건지 알 수 있었기 때문에..

	#include <stdio.h>
	#include <vector>
	#include <queue>
	#include <algorithm>
	#include <iostream>
	#include <string>
	#include <bitset>
	#include <map>
	#include <set>
	#include <tuple>
	#include <string.h>
	using namespace std;
	using i64 = long long int;
	using ii = pair<int, int>;
	using ii64 = pair<i64, i64>;
	int main()
	{
	int a, b, f, k;
	scanf("%d %d %d %d", &a, &b, &f, &k);
	int tf = a - f;
	int gas = b - f;
	if (gas < 0)
	{
	printf("-1");
	return 0;
	}
	int count = 0;
	for (int i = 0; i < k; i++)
	{
	if (i % 2 == 0)
	{
	if (i == k - 1)
	{
	if (gas < tf)
	{
	gas = b;
	count++;
	}
	}
	else
	{
	if (gas < tf * 2)
	{
	gas = b;
	count++;
	}
	}
	if (i == k - 1)
	{
	gas -= tf;
	}
	else
	{
	gas -= tf * 2;
	}
	if (gas < 0)
	{
	printf("-1");
	return 0;
	}
	}
	else
	{
	if (i == k - 1)
	{
	if (gas < f)
	{
	gas = b;
	count++;
	}
	}
	else
	{
	if (gas < f * 2)
	{
	gas = b;
	count++;
	}
	}
	if (i == k - 1)
	{
	gas -= f;
	}
	else
	{
	gas -= f * 2;
	}
	if (gas < 0)
	{
	printf("-1");
	return 0;
	}
	}
	}
	printf("%d", count);
	return 0;
	}

view raw C.cpp hosted with ❤ by GitHub

D. Make a Permutation!

주어진 수열에서 최소한의 개수의 숫자만 바꿔서 수열을 순열(1~n까지 숫자가 한 번씩만 나타나는 수열)로 바꾸고 싶은데 이 때 숫자 바꾸는 최소 횟수를 구하는 문제다. 일단 순열로 만들되, 가능한 순열이 여러 개가 있다면 사전순으로 가장 앞서게 만들어야 한다.

 나는 간단한 전처리를 한다음 맨 앞에서부터 현재 숫자를 바꿔야 할지 아닐지 확인하는 식으로 풀었는데, 만약에 기존 수열에서 하나밖에 안 남은 숫자라면 그 숫자는 바꾸면 안 된다(1~n사이 숫자가 한 번씩은 나와야되는데, 여기서 바꾸면 나중에 또 바꿔야 하기 때문에 바꾸는 횟수에서 손해봄). 또, 사전순으로 가장 앞서게 만들어야하므로 1~n숫자들 중 등장하지 않는 가장 작은 수부터 순서대로 나타나게 만들어줘야 하는데, 이 때 바꿀 수가 기존 수보다 더 크다면, 그리고 해당 바꿀려는 숫자가 기존 수열에서 2번 이상 등장한다면 현재 수를 놔두고 나중에 해당 수가 또 나울 때 거기서 바꾸는게 사전 순으로 더 앞이기 때문에 그렇게 해주고, 아니면 그냥 바로 바꿔주면 된다. 이 규칙 그대로 지키면서 전체 수열 처음부터 쭉 계산해주면 O(N)에 답을 구할 수 있다. 

	#include <stdio.h>
	#include <vector>
	#include <queue>
	#include <algorithm>
	#include <iostream>
	#include <string>
	#include <bitset>
	#include <map>
	#include <set>
	#include <tuple>
	#include <string.h>
	using namespace std;
	using i64 = long long int;
	using ii = pair<int, int>;
	using ii64 = pair<i64, i64>;
	vector<int> exists[200001];
	int eidx[200001];
	int counts[200001];
	int main()
	{
	int n;
	scanf("%d", &n);
	vector<int> res(n);
	for (int i = 0; i < n; i++)
	{
	int k;
	scanf("%d", &k);
	res[i] = k;
	counts[k]++;
	exists[k].push_back(i);
	}
	int idx = 0;
	int count = 0;
	for (int i = 1; i <= n;)
	{
	if (counts[i] > 0)
	{
	i++;
	continue;
	}
	//하나 밖에 존재하지 않는 원소 - 못 건드림
	while (counts[res[idx]] <= 1) idx++;
	if (res[idx] > i)
	{
	counts[res[idx]]--;
	eidx[res[idx]]++;
	res[idx] = i;
	i++;
	count++;
	}
	else
	{
	if (idx == exists[res[idx]][eidx[res[idx]]])
	{
	idx++;
	}
	else
	{
	counts[res[idx]]--;
	eidx[res[idx]]++;
	res[idx] = i;
	i++;
	count++;
	}
	}
	}
	printf("%d\n", count);
	for (auto& r : res)
	printf("%d ", r);
	return 0;
	}

view raw D.cpp hosted with ❤ by GitHub

E. Fire

n개의 물건이 있고 물건은 각각 ti, di, pi라는 세 가지 수치를 갖고 있다. 해당 물건을 지키기 위해 걸리는 시간이 ti, 그 물건이 타서 없어져버리는 데 걸리는 시간이 di, 물건의 가치를 pi라고 했을 때, 물건들 가치 합이 최대가 되게 구할려면 어떤 물건들을 구해야하는 지를 찾는게 문제다. 좀 까라도워 보이지만 타서 없어지는데 걸리는 시간 di를 기준으로 정렬하면 DP로 쉽게 구할 수 있다. 

 만약에 어떤 물건 집합 S를 선택하려고 했을 때, a,b라는 두 개의 물건에 대해 da < db라면 a를 먼저 구하는게 항상 이득이기 때문이다. b를 먼저 구할 경우 a가 타서 없어질 수 있지만 a를 먼저 구했는데 b가 타서 없어질 수는 없기 때문(a,b둘 다 선택이 가능하다고 했을 때). 즉 어떤 물건들에 대해서 di순으로 정렬해두면 항상 di가 더 작은 값부터 집합에 포함시킬 지 말지 고려하게 되므로 모든 경우를 다 테스트해볼 수 있다. di순으로 정렬한 다음에는 평범한 냅색 dp처럼 구현하면 된다. 시간 복잡도는 O(N(logN + D)). N이 100이고 D가 2000이므로 시간 제한안에 충분히 답이 나온다.

	#include <stdio.h>
	#include <vector>
	#include <queue>
	#include <algorithm>
	#include <iostream>
	#include <string>
	#include <bitset>
	#include <map>
	#include <set>
	#include <tuple>
	#include <string.h>
	using namespace std;
	using i64 = long long int;
	using ii = pair<int, int>;
	using ii64 = pair<i64, i64>;
	struct Item
	{
	int t, d, p, idx;
	};
	vector<Item> items;
	int table[101][2001];
	ii nextArr[101][2001];
	int solve(int idx, int offset)
	{
	if (idx == items.size())
	return 0;
	int& res = table[idx][offset];
	if (res != -1)
	return res;
	res = solve(idx + 1, offset);
	nextArr[idx][offset] = ii(idx + 1, offset);
	if (offset + items[idx].t < items[idx].d)
	{
	if (res < items[idx].p + solve(idx + 1, offset + items[idx].t))
	{
	res = items[idx].p + solve(idx + 1, offset + items[idx].t);
	nextArr[idx][offset] = ii(idx + 1, offset + items[idx].t);
	}
	}
	return res;
	}
	int main()
	{
	memset(table, -1, sizeof(table));
	int n;
	scanf("%d", &n);
	items.resize(n);
	for (int i = 0; i < n; i++)
	{
	scanf("%d %d %d", &items[i].t, &items[i].d, &items[i].p);
	items[i].idx = i + 1;
	}
	sort(items.begin(), items.end(), [](const Item& l, const Item& r)
	{
	return l.d < r.d;
	});
	printf("%d\n", solve(0, 0));
	vector<int> select;
	int idx = 0;
	int offset = 0;
	while (idx < items.size())
	{
	int nidx, noffset;
	tie(nidx, noffset) = nextArr[idx][offset];
	if (noffset != offset)
	{
	select.push_back(items[idx].idx);
	}
	idx = nidx;
	offset = noffset;
	}
	printf("%d\n", select.size());
	for (auto& s : select)
	printf("%d ", s);
	return 0;
	}

view raw E.cpp hosted with ❤ by GitHub