Educational Codeforces Round 41

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

아직 시스템 테스트가 남긴 했지만 적당히 5문제 잘 풀었다. E번에서 코드 짜다가 갑자기 생각이 이상해져서 패널티를 많이 먹은게 아쉽다. 처음부터 좀 더 정확하게 생각했으면 패널티를 4~50은 덜 받았을텐데.. 그게 좀 아쉽. D번도 그렇고 E번도 그렇고 코드 짜다가 꼬이는 걸 어떻게 좀 해야할텐데 싶다.

A. Tetris

그냥 나온 숫자들 중에 제일 횟수 적은 거 출력해주면 된다.

	#include <stdio.h>
	#include <vector>
	#include <queue>
	#include <algorithm>
	#include <iostream>
	#include <string>
	#include <bitset>
	#include <map>
	#include <set>
	#include <tuple>
	#include <string.h>
	#include <math.h>
	#include <random>
	#include <functional>
	#include <assert.h>
	#include <math.h>
	using namespace std;
	using i64 = long long int;
	using ii = pair<int, int>;
	using ii64 = pair<i64, i64>;
	int main()
	{
	int n, m;
	scanf("%d %d", &n, &m);
	vector<int> counts(n + 1);
	for (int i = 0; i < m; i++)
	{
	int k;
	scanf("%d", &k);
	counts[k]++;
	}
	int ans = counts[1];
	for (int i = 2; i <= n; i++)
	ans = min(ans, counts[i]);
	printf("%d", ans);
	return 0;
	}

view raw A.cpp hosted with ❤ by GitHub

B. Lecture Sleep

t 값이 1인 건 다 답에 포함시켜놓고, 맨 앞부터 k개 구간을 유지하면서 그 k개 안쪽에 있는 0인 애들을 다 1로 바꿨을 때의 값을 순서대로 구해서 그 중 최댓값을 출력해주면 된다.

	#include <stdio.h>
	#include <vector>
	#include <queue>
	#include <algorithm>
	#include <iostream>
	#include <string>
	#include <bitset>
	#include <map>
	#include <set>
	#include <tuple>
	#include <string.h>
	#include <math.h>
	#include <random>
	#include <functional>
	#include <assert.h>
	#include <math.h>
	using namespace std;
	using i64 = long long int;
	using ii = pair<int, int>;
	using ii64 = pair<i64, i64>;
	int main()
	{
	int n, k;
	scanf("%d %d", &n, &k);
	vector<int> lectures(n);
	for (int i = 0; i < n; i++)
	scanf("%d", &lectures[i]);
	vector<int> t(n);
	int baseCount = 0;
	for (int i = 0; i < n; i++)
	{
	scanf("%d", &t[i]);
	if (t[i])
	baseCount += lectures[i];
	}
	for (int i = 0; i < k; i++)
	{
	if (t[i] == 0)
	baseCount += lectures[i];
	}
	int ans = baseCount;
	for (int right = k; right < n; right++)
	{
	//right번째 추가, right-k번째 제거
	if (t[right] == 0)
	{
	baseCount += lectures[right];
	}
	if (t[right - k] == 0)
	{
	baseCount -= lectures[right - k];
	}
	ans = max(ans, baseCount);
	}
	printf("%d", ans);
	return 0;
	}

view raw B.cpp hosted with ❤ by GitHub

C. Chessboard

완전 구현 문제. 4등분된 조각을 붙이고 / 색칠하는 모든 경우에 대해 최솟값 구해서 출력해주면 된다.

	#include <stdio.h>
	#include <vector>
	#include <queue>
	#include <algorithm>
	#include <iostream>
	#include <string>
	#include <bitset>
	#include <map>
	#include <set>
	#include <tuple>
	#include <string.h>
	#include <math.h>
	#include <random>
	#include <functional>
	#include <assert.h>
	#include <math.h>
	using namespace std;
	using i64 = long long int;
	using ii = pair<int, int>;
	using ii64 = pair<i64, i64>;
	vector<string> squares[4];
	vector<string> merge(const vector<int>& order)
	{
	vector<string> res;
	for (int i = 0; i < squares[order[0]].size();i++)
	res.push_back(squares[order[0]][i] + squares[order[1]][i]);
	for (int i = 0; i < squares[order[2]].size(); i++)
	res.push_back(squares[order[2]][i] + squares[order[3]][i]);
	return res;
	}
	int coloring(int k, const vector<string>& board)
	{
	int need = 0;
	for (int i = 0; i < board.size(); i++)
	{
	for (int j = 0; j < board.size(); j++)
	{
	int nowColor = (i + j + k) % 2;
	if (board[i][j] != nowColor + '0')
	need++;
	}
	}
	return need;
	}
	int main()
	{
	int n;
	scanf("%d", &n);
	for (int i = 0; i < 4; i++)
	{
	for (int j = 0; j < n; j++)
	{
	string s;
	cin >> s;
	squares[i].push_back(s);
	}
	}
	vector<int> order = { 0,1,2,3 };
	int minNeed = 4 * n * n;
	do
	{
	auto merged = merge(order);
	minNeed = min({ minNeed, coloring(0, merged), coloring(1, merged) });
	} while (next_permutation(order.begin(), order.end()));
	printf("%d", minNeed);
	return 0;
	}

view raw C.cpp hosted with ❤ by GitHub

D. Pair Of Lines

1-2 점이 같은 라인에 있는 경우, 1-3 점이 같은 라인에 있는 경우, 2-3 점이 같은 라인에 있는 경우 세 가지만 확인하면 된다.

1-2 점이 같은 라인에 있는 경우가 안 된다면 -> 1번 점과 2번 점은 반드시 서로 다른 라인 위에 존재해야 한다. 그러면 이제 이 경우, 또 다른 3번 점에 대해 이 점이 1번 점과 같은 라인 위거나 아니면 2번 점과 같은 라인 위거나 두 가지 경우밖에 남지 않는다(둘 중 한 라인에는 반드시 속해야 하기 때문). 따라서 모든 경우를 저 3가지로 커버 가능하므로, 3가지 경우에 대해 전체 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>
	#include <math.h>
	#include <random>
	#include <functional>
	#include <assert.h>
	#include <math.h>
	using namespace std;
	using i64 = long long int;
	using ii = pair<int, int>;
	using ii64 = pair<i64, i64>;
	bool solve(const vector<ii64>& points, int s1, int e1)
	{
	int s2 = 0;
	int e2 = -1;
	if (s1 == 0)
	s2 = 1;
	if (e1 == 1)
	s2 = -1;
	i64 dx1 = points[e1].first - points[s1].first;
	i64 dy1 = points[e1].second - points[s1].second;
	for (int i = e1 + 1; i < points.size(); i++)
	{
	i64 ndx1 = points[i].first - points[e1].first;
	i64 ndy1 = points[i].second - points[e1].second;
	//line1에 속함
	if (dx1 * ndy1 == ndx1 * dy1)
	continue;
	//line2 첫번째
	if (s2 == -1)
	{
	s2 = i;
	continue;
	}
	if (e2 == -1)
	{
	e2 = i;
	continue;
	}
	//line2에 속하는지 확인
	i64 dx2 = points[e2].first - points[s2].first;
	i64 dy2 = points[e2].second - points[s2].second;
	i64 ndx2 = points[i].first - points[e2].first;
	i64 ndy2 = points[i].second - points[e2].second;
	if (dx2 * ndy2 == ndx2 * dy2)
	continue;
	return false;
	}
	return true;
	}
	int main()
	{
	int n;
	scanf("%d", &n);
	vector<ii64> points(n);
	for (int i = 0; i < n; i++)
	scanf("%lld %lld", &points[i].first, &points[i].second);
	sort(points.begin(), points.end());
	//1-2 2-?
	//1-3 2-?
	//2-3 1-?
	//셋 중 하나만 돼도 가능 나머지는 x
	if (solve(points, 0, 1) || solve(points,0, 2) || solve(points, 1, 2))
	printf("YES");
	else
	printf("NO");
	return 0;
	}

view raw D.cpp hosted with ❤ by GitHub

E. Tufurama

i번째 시즌에 대해서, i+1~ai 시즌까지 중 에피소드가 i이상인 것들의 개수를 모두 구해 더해주면 답이 된다. 이걸 구하는 방법은 굉장히 여러 가지가 있을 수 있는데, 나는 펜윅으로 했다. i번째 시즌 루프에서 배열에 k번째 원소= k번째 시즌이 에피소드가 i이상이면 1, 아니면 0으로 정의하고 여기서 펜윅트리를 이용해 구간합을 빠르게 구한다. 저런 배열을 유지하는 건 간단한데, 에피소드가 동일한 시즌들을 모두 미리 묶어 놓은 후 시즌 i번째 루프를 지나갈 때 에피소드가 i이 모든 시즌들을 다 배열에서 제거해주면 배열에는 항상 에피소드가 i보다 큰 시즌들만 남아있게 된다.

	#include <stdio.h>
	#include <vector>
	#include <queue>
	#include <algorithm>
	#include <iostream>
	#include <string>
	#include <bitset>
	#include <map>
	#include <set>
	#include <tuple>
	#include <string.h>
	#include <math.h>
	#include <random>
	#include <functional>
	#include <assert.h>
	#include <math.h>
	using namespace std;
	using i64 = long long int;
	using ii = pair<int, int>;
	using ii64 = pair<i64, i64>;
	class FenwickTree
	{
	public:
	FenwickTree(int k)
	{
	data.resize(k);
	}
	i64 sum(int n)
	{
	i64 ans = 0;
	while (n > 0)
	{
	ans += data[n];
	n -= (n & -n);
	}
	return ans;
	}
	void add(int n, i64 num)
	{
	while (n < data.size())
	{
	data[n] += num;
	n += (n & -n);
	}
	}
	private:
	vector<i64> data;
	};
	vector<int> episodes[200001];
	int main()
	{
	int n;
	scanf("%d", &n);
	vector<int> a(n + 1);
	FenwickTree tree(n + 2);
	for (int i = 1; i <= n; i++)
	{
	scanf("%d", &a[i]);
	a[i] = min(a[i], n);
	tree.add(i, 1);
	episodes[a[i]].push_back(i);
	}
	i64 ans = 0;
	for (int i = 1; i <= n; i++)
	{
	if (a[i] > i)
	{
	//episode가 i이상인 애들만 남아 있음
	//이번 시즌 episode까지 범위에서 i이상인 애들 개수만 구할 수 있다
	ans += tree.sum(a[i]) - tree.sum(i);
	}
	//episode가 i이하인건 전부 제거
	for (auto& e : episodes[i])
	tree.add(e, -1);
	}
	printf("%lld", ans);
	return 0;
	}

view raw E.cpp hosted with ❤ by GitHub