[CF] Round #555 (Div. 3) _ 210118

(2021년 1월 20일에 작성한 글입니다.)

 

Dashboard - Codeforces Round #555 (Div. 3) - Codeforces

 

A.

그냥 구현

input의 일의 자리가 0일 수 있다는 점을 체크해야 하고

수가 줄어들어서 일의자리 수가 되면 그냥 +9를 하고 끝내면 된다는 점을

유의해주면 된다

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	ll N;
	ll ans = 0;

	cin >> N;
	if (N % 10 == 0) {
		ans++;
		N++;
	}
	while (1) { //다시
		if (N / 10 == 0) {
			ans += 9;
			break;
		}
		do {
			ans++;
			N++;
		} while (N % 10 != 0);
		while (N % 10 == 0) {
			N /= 10;
		}
	}
	cout << ans << ENDL;

	return 0;
}

​

B.

앞에서부터 확인하면서

현재 값과 바뀌는 값이 같으면 continue

만약 바뀌는 값이 크면 바꿔주고

만약 그렇지 않은데, 바꾸는 과정이 시작된 상태라면 break

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int N;
	string s;
	vector<int> arr(10);
	bool started = false;
	int i;

	cin >> N;
	cin >> s;
	for (i = 1; i <= 9; i++) {
		cin >> arr[i];
	}
	
	for (i = 0; i < s.length(); i++) {
		int temp = s[i] - '0';
		if (temp == arr[temp]) {
			continue;
		}
		else if (temp < arr[temp]) {
			if (!started) {
				started = true;
			}
			s[i] = arr[temp] + '0';
		}
		else {
			if (started) {
				break;
			}
		}
	}

	cout << s << ENDL;

	return 0;
}

​

C1.

왼쪽 오른쪽 비교하면서

일단 좌우 둘 다 이전 수보다 작으면 break

만약 좌<우이고 좌>before이면 왼쪽,

반대 경우라면 오른쪽,

좌>우지만 좌 > before이면 왼쪽

반대 경우라면 오른쪽

이렇게 해주면 된다. 이걸 else if문으로 처리하면서​

deque<int> deq;
vector<char> ans;
int before = 0;

void left()
{
	before = deq.front();
	ans.push_back('L');
	deq.pop_front();
}

void right()
{
	before = deq.back();
	ans.push_back('R');
	deq.pop_back();
}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int N;
	int i;

	cin >> N;
	for (i = 0; i < N; i++) {
		int temp; cin >> temp;
		deq.push_back(temp);
	}

	while (!deq.empty()) {
		int l = deq.front(), r = deq.back();
		if (l < before && r < before) {
			break;
		}
		
		if (l<r && l>before) {
			left();
		}
		else if (r < l && r > before) {
			right();
		}
		else if (l > before) {
			left();
		}
		else {
			right();
		}
	}

	cout << ans.size() << ENDL;
	for (char n : ans) {
		cout << n;
	}

	return 0;
}

​

C2.

결국 못 풀었다가 효규한테 물어봄

dp같은 prefix sum이라고 했는데 딱 적절한 설명인 거 같다

각 수들에 대해 만약 그 수를 선택하면 최대 몇 개를 더 뽑을 수 있는지를

좌, 우에 대해 정보 다 저장해놓고

만약 좌, 우에 같은 수가 있다면 미리 저장해놓은 정보를 바탕으로

더 많이 뽑을 수 있는 쪽을 뽑는다.

만약 다른 수가 있다면 C1에서처럼 처리하면 되고.

​

dart님 풀이는 왼쪽, 오른쪽에 대해서

그걸 쭉 뽑았을 때의 최대 개수를 구하시고 더 큰 쪽으로 가신거 같은데

나도 그렇게 하려고 했는데 왜 잘 안 된건지 모르겠다...

dart님은 그냥 temporary한 deque 만드셔서 다 빼보셨는데

나는 그렇게 안 하고 어떻게 잘 구현하려고 하다가

잘 안 된거 같다....

vector<char> ans;
vector<int> arr;
int before = 0;
int idx1, idx2;

void left()
{
	before = arr[idx1];
	idx1++;
	ans.push_back('L');
}

void right()
{
	before = arr[idx2];
	idx2--;
	ans.push_back('R');
}

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int N;
	int i;

	cin >> N;
	arr.resize(N + 5);
	vector<int> A(N + 5, 1), B(N + 5, 1);
	for (i = 1; i <= N; i++) {
		cin >> arr[i];
	}
	for (i = N - 1; i >= 1; i--) {
		if (arr[i] < arr[i + 1]) {
			A[i] = A[i + 1] + 1;
		}
	}
	for (i = 2; i <= N; i++) {
		if (arr[i - 1] > arr[i]) {
			B[i] = B[i - 1] + 1;
		}
	}

	idx1 = 1;
	idx2 = N;
	while (idx1 <= idx2) {
		if (arr[idx1] <= before && arr[idx2] <= before) {
			break;
		}

		if (arr[idx1] < arr[idx2] && arr[idx1] > before) {
			left();
		}
		else if (arr[idx1] > arr[idx2] && arr[idx2] > before) {
			right();
		}
		else if (arr[idx1] > arr[idx2]) {
			left();
		}
		else if (arr[idx1] < arr[idx2]) {
			right();
		}
		else {
			if (A[idx1] > B[idx2]) {
				left();
			}
			else {
				right();
			}
		}
	}

	cout << ans.size() << ENDL;
	for (char c : ans) {
		cout << c;
	}

	return 0;
}

​

E.

앞에서부터 그리디하게

mod를 작게 만들려고 노력하면 된다.

남아있는 수를 빠르게 확인하기 위해 map을 사용했다

​

효규는 유파로 풀었구나

정말 신기하도다

​

만약 x를 사용할 수 있다면 par[x] = -1

그렇지 않다면 par[x] = (x + 1) % n

이 방식으로 처음 초기화 + 값 사용한 후 업데이트 한다

​

신기가 방기다

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int N;
	cin >> N;
	vector<int> A(N + 5);
	map<int, int> B;
	int i;

	for (i = 0; i < N; i++) {
		cin >> A[i];
	}
	for (i = 0; i < N; i++) {
		int temp; cin >> temp;
		B[temp]++;
	}

	for (i = 0; i < N; i++) {
		int start = (N - A[i]) % N;
		auto iter = B.lower_bound(start);
		if (iter == B.end())iter = B.begin();
		auto start_iter = iter;

		if (iter->second > 0) {
			cout << (A[i] + iter->first) % N << ' ';
			iter->second--;
			if (iter->second == 0) {
				B.erase(iter->first);
			}
			continue;
		}

		iter++;
		if (iter == B.end()) {
			iter = B.begin();
		}
		for (; iter != start_iter; ) {
			if (iter->second) {
				cout << (A[i] + iter->first) % N << ' ';
				iter->second--;
				if (iter->second == 0) {
					B.erase(iter->first);
				}
				break;
			}
			
			iter++;
			if (iter == B.end()) {
				iter = B.begin();
			}
		}
	}

	return 0;
}