Codeforces Round #575 (Div. 3)

A - Three Piles of Candies

그냥 반띵

 

소스코드:

int n;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	while (n--) {
		long long q, w, e;
		cin >> q >> w >> e;
		cout << (q + w + e) / 2 << '\n';
	}
	return 0;
}

 

 

 

B - Odd Sum Segments

입력으로 홀수가 들어오면 홀수의 위치(index)를 벡터에 push  (짝수는 무시)

홀수의 개수가 홀수가 일 때 k도 홀수가 이여야 하고, 짝수개 이면 k도 짝수 개이여야 한다.

 

소스코드:

int n;
vector<int> v;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> n;
	while (n--) {
		int q, w;
		cin >> q >> w;
		v.clear();
		for (int i = 0; i < q; i++) {
			int a;
			cin >> a;
			if(a%2) v.push_back(i+1);
		}
		int sz = v.size();
		if (sz < w||(sz % 2 == 0 && w % 2)||(sz % 2&& w % 2==0)) cout << "NO\n";
		else {
			cout << "YES\n";
			for (int i = 1; i < w; i++) {
				cout << v[i] - 1 << " ";
			}
			cout << q << '\n';
		}

	}
	return 0;
}

 

 

 

C - Robot Breakout

1. 위로 못간다 -> 현재 위치를 최대 x값으로 갱신

2. 오른쪽으로 못간다 -> 현재 위치를 최대 y 값으로 갱신

3. 아래로 못간다 -> 현재 위치를 최소 x값으로 갱신

4. 왼쪽으로 못간다 -> 현재 위치를 최소 y 값으로 갱신

최소값이 최대값을 넘어서면 해당 정점 존재 안함

 

* 주의: 가능한 정점이 여러개일 때, 최소 값으로 출력하기

 

소스코드:

int tc,n;
int dx[4] = { -1,0,1,0 };
int dy[4] = { 0,1,0,-1 };

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> tc;
	while (tc--) {
		cin >> n;
		int lx=inf,sx=-inf, ly= inf,sy=-inf;
		bool chk = true;
		for (int i = 0; i < n; i++) {
			int x, y, q, w, e, r;
			cin >> x >> y >> q >> w >> e >> r;
			if (!q) sx = max(sx, x);
			if (!w) ly = min(ly, y);
			if (!e) lx = min(lx, x);
			if (!r) sy = max(sy, y);
			if (sy > ly) chk = false;
			if (sx > lx) chk = false;

		}
		if (!chk) cout << "0\n";
		else {
			cout << "1 "<<sx << " " << sy << '\n';
		}
	}
	return 0;
}

 

 

 

D1(easy) - RGB Substring (easy version)

그냥 대충 O($n^{2}$)으로 풀어도 맞음 

 

D2(hard) - RGB Substring (hard version)

입력받은 문자열을 3번 비교할건데,

RGBRGBRGB.... 로 1번 비교

GBRGBRGBR.... 로 1번 비교

BRGBRGBRG.... 로 1번 비교하면서

int dp[3][200001]에 구간합으로 저장해줌 -> 현재 값 틀리면 (지금까지 틀린 개수+1)

이렇게 구간 합 저장하면서 비교하는 문자의 위치가 K 이상일 때, 구간 합을 결과로 갱신해줌

 

* 쓸데없이 memset으로 dp 변수 초기화 해주다가 시간초과 남 ㅎㅎ

  초기화할 필요 없이 dp[i][0]은 0으로 항상 두고 (이전 값+1) 해주면 됨

 

소스코드:

int tc, n, k;
int dp[3][200001];
char c[3] = { 'R','G','B' };
string s;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> tc;
	while (tc--) {
		cin >> n >> k;
		cin >> s;
		int len = s.size();
		int res = len;
		for (int z = 0; z < 3; z++) {
			int p =z;
			for (int i = 0; i <len; i++) {
				if (s[i] != c[p]) dp[z][i + 1] = dp[z][i]+1;
				else dp[z][i + 1] = dp[z][i];
				p = (p + 1) % 3;
				if (i >= k-1) res = min(res, dp[z][i + 1] - dp[z][i+1- k]);
			}
		}
		cout << res << '\n';
	}
	return 0;
}

 

 

 

E - Connected Component on a Chessboard

문제를 이해 못 하겠당...

뭔 소리징... ㅠㅅㅠ

 

 

F - K-th Path

그냥 모르겠다