Codeforces Round #616 (Div. 2) 첫 코포

 

2020년 2월 3일 처음으로 코드 포스를 도전하게 되었다. 일단 너무 생소했다. 그래도 백준에서 문제를 조금 풀어보면서 조금 익숙해진 줄 알았는데 지금까지 풀었던 유형이랑 많이 달랐다. 또 평소 영어를 못하는데 영어가 나와서 해석하는 것만으로도 시간을 너무 많이 사용했다. 해석이 끝나도 멍했던 거 같다. 그래서 1시간 43분에 겨우 A번을 풀고 그렇게 첫 코포를 마치게 되었다.

 

A- Even But Not Even

소스코드

#include <iostream>
#include <vector>
#include <algorithm>
#define INF 1000000000
typedef long long ll;
using namespace std;

//sum이 2로 나눌수 있고 자체 넘버는 2로 안 나눠진다. ebne이다.
//앞에 0이 올 수 없고 숫자를 삭제할 수 도 있다. 순서는 변경 금지
//0~n-1의 수를 삭제가능
int n, m, t;

bool flag = false;
int sum(string num) {
	int s = 0;
	for (int i = 0; i < num.size(); i++) {
		if (num[i] == 0)
			break;
		s += num[i] - '0';
	}
	return s;
}

bool check(int num, int numend) {
	if (num % 2 == 0 && numend % 2 == 1)
		return true;
	return false;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> t;
	while (t--) {
		flag = false;
		string num;
		cin >> n;
		cin >> num;
		int totalsum;
		int circle = n;
		while (circle--) {
			totalsum = sum(num);
			if (check(totalsum, num[circle] - '0')) {
				for (int i = 0; i < n; i++) {
					if (num[i] == 0)
						break;
					cout << num[i];
				}
				cout << '\n';
				flag = true;
				break;
			}
			else {
				bool flag2 = false;
				for (int i = circle; i >= 0; i--) {
					int tmp = (totalsum - (num[i] - '0'));
					if (tmp % 2 == 0) {
						if (i == 0 && num[1] == '0')
							continue;
						for (int j = i; j < n; j++) {
							num[j] = num[j + 1];
						}
						totalsum -= tmp;
						flag2 = true;
						break;
					}
				}
				if (!flag2) {
					if ((num[circle] - '0') % 2 == 0) {
						totalsum -= num[circle] - '0';
						num[circle] = 0;

					}
					else {
						totalsum -= num[circle-1] - '0';
						num[circle-1] = num[circle];
						num[circle] = 0;
					}
				}
			}
		}
		if (!flag)
			cout << -1 << '\n';
	}
	return 0;
}

 

어떻게든 풀어서 맞은 코드이다. A는 홀수이면서 전체 합이 짝수인 숫자가 되도록 숫자를 마음대로 제거해서 결과값을 출력하는 문제였다. 제거하는 횟수가 최소나 최대가 될 필요가 없기에 그냥 홀수 두 개만 뽑아서 출력하면 된다. 그런데 이때는 그냥 구현으로 다해 보면서 했던 것 같다. 코드가 너무 더러워서 지금 다시 풀어봤다.

 

소스코드

#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define fu(i,a,j) for(int i=a;i<j;i++)
#define fd(i,a,j) for(int i=a;i>=j;i--)
#define SYNC ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define MOD 998244353
#define MOD2 1000000021
#define INF 1e9
#define N 100001
using namespace std;

typedef long long ll;
typedef long double ld;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a * b / gcd(a, b); };
int n, m, k, t;
int dr[] = { 0,0,1,-1, -1,1,1,-1 };
int dc[] = { -1,1,0,0, 1,1,-1,-1 };

int main() {
	SYNC;
	cin >> t;
	while (t--) {
		cin >> n;
		string s;
		cin >> s;
		string ans;
		int odd = 0;
		fu(i, 0, n) {
			if ((s[i] - '0') % 2 == 1) {
				odd++;
				ans += s[i];
			}
			if (odd == 2) break;
		}
		if (odd != 2) {
			cout << -1 << '\n';
			continue;
		}
		cout << ans << '\n';
	}
	return 0;
}

 

B. Array Sharpening

 

B문제는 이때는 풀지않았지만 끝나고 나중에 풀게 되었다. B에서는 strictly increasing or strictly decreasing array is sharpened 인 배열이 a= a-1 연산을 마음대로 사용해서 만들 수 있는지를 출력하는 문제였다.

증가하거나 감소하는 배열이 되기위해선 마이너스 연산을 할 수 있으므로 증가할 때는 값이 인덱스보다 크거나 같으면 되고 감소할 때는 값이 n-1-인덱스 보다 크거나 같으면 된다. 그래서 앞 뒤로 최대까지 가능한 인덱스를 구해 비교하여 출력하면 된다.

 

#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define fu(i,a,j) for(int i=a;i<j;i++)
#define fd(i,a,j) for(int i=a;i>=j;i--)
#define SYNC ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define MOD 998244353
#define MOD2 1000000021
#define INF 1e9
#define N 100001
using namespace std;

typedef long long ll;
typedef long double ld;
typedef double db;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pii> vpii;
typedef vector<pll> vpll;

ll gcd(ll a, ll b) { return b ? gcd(b, a % b) : a; }
ll lcm(ll a, ll b) { return a * b / gcd(a, b); };
int n, m, k, t;
int dr[] = { 0,0,1,-1, -1,1,1,-1 };
int dc[] = { -1,1,0,0, 1,1,-1,-1 };

int main() {
	SYNC;
	cin >> t;
	while (t--) {
		cin >> n;
		vi a(n);
		fu(i, 0, n)
			cin >> a[i];
		bool flg = 0;
		int pre = 0, suf = n - 1;
		while (pre < n && a[pre] >= pre) pre++;
		while (suf >= 0 && a[suf] >= n - suf - 1) suf--;
		if (suf + 1 <= pre - 1)
			cout << "Yes\n";
		else
			cout << "No\n";
	}
	return 0;
}