[CF] Round #657 (Div. 2) _ 200905

(2020년 9월 6일에 작성한 글입니다.)

 

Dashboard - Codeforces Round #657 (Div. 2) - Codeforces

학회 코드포스 스터디 Road to Expert에서 풀었다.

​

A.

아니 이 문제가 어떻게 A번일 수 있는가..

싶을 정도로 A번 같지 않은 문제였다.

abacaba가 하나만 존재해야 하기 때문에

물음표를 채우고 나서, 전체 문자열에서 abacaba가 하나밖에 없다는 걸 확인해야 하는데

여기서 나는 abacaba가 시작하는 지점을 indx라고 하면

indx + 4부터 시작하는 abacaba가 있는지만을 확인하면 되는 줄 알았다.

근데 아니었어.

abacaba 앞에 abac가 있을수도 있고, 맨 마지막 a에 bacaba가 붙어서 생겼을수도 있고.

여러 경우가 있다.

그래서 끝나고 원빈이가 다른 분들이 제출한 코드 보고 이야기해줬는데

물음표를 적절히 채울 때 마다

문자열을 처음부터 끝까지 돌면서

abacaba가 몇 개인지를 체크하도록 한 사람이 있었고

문자열 자체가 별로 길지 않고 테스트케이스도 적기 때문에 시간초과가 나지 않는다....

그래서 처음부터 다시 짜서 맞았다.

string s;
string aba = "abacaba";
int N;

int chk()
{
	int i, j;
	int cnt = 0;
	bool flag;

	for (i = 0; i + 6 < N && cnt <= 1; i++) {
		flag = true;
		for (j = 0; j < 7; j++) {
			if (s[i + j] != aba[j]) {
				flag = false;
				break;
			}
		}

		if (flag) {
			cnt++;
		}
	}

	return cnt;
}

void print()
{
	int i;

	cout << "Yes" << '\n';
	for (i = 0; i < N; i++) {
		if (s[i] == '?') {
			cout << 'd';
		}
		else {
			cout << s[i];
		}
	}
	cout << '\n';

	return;
}

int main()
{
	//freopen("input.txt", "r", stdin);
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int T;
	int i, j;

	cin >> T;
	while (T--) {
		cin >> N;
		cin >> s;

		int check = chk();
		if (check == 2) {
			cout << "No" << '\n';
			continue;
		}
		else if (check == 1) {
			print();
			continue;
		}

		//s[i]에 abacaba 없음
		bool flag;
		for (i = 0; i + 6 < N; i++) { //처음부터 쭉 가는 중
			vector<int> indexs;
			flag = true;
			for (j = 0; j < 7; j++) {
				if (s[i + j] == '?') {
					s[i + j] = aba[j];
					indexs.push_back(i + j);
				}
				else if (s[i + j] != aba[j]) {
					flag = false;
					break;
				}
			}

			if (flag) {
				if(chk() != 1) {
					flag = false;
				}
			}

			if (flag) {
				break;
			}
			else {
				for (int indx : indexs) {
					s[indx] = '?';
				}
			}			
		}

		//결과
		if (flag) {
			print();
		}
		else {
			cout << "No" << '\n';
		}		
	}
	return 0;
}

​

B.

이것도 진짜 어려웠는데

내가 포인트를 잘못 잡았던 게

abs(b - c) <= (r - l)이어야 하는거고...

다 맞는데

나는 a가 항상 l(엘, 범위의 최솟값)일 줄 알았는데

생각해보니까 그렇지 않은 경우가 있을 수도 있었고,

그래서 for(a = l; a <= r; a++)를 돌면서

abs(b - c) <= (r - l) 및 여러 조건을 만족하는 경우가 존재하는지를 확인해줬고

존재하면 break;

이렇게 했다.....ㅎ

int main()
{
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	int T;
	ll l, r, m;
	ll a, b, c, n;
	ll diff, sub;
	ll i;

	cin >> T;
	while (T--) {
		cin >> l >> r >> m;
		diff = r - l;

		for (i = l; i <= r; i++) {
			a = i;

			n = (m + a - 1) / a; //n * a는 m 이상, b < c
			sub = abs(n*a - m);
			if (sub <= diff) {
				a = i;
				b = l;
				c = b + sub;
				break;
			}

			n--;
			sub = abs(n*a - m);
			if (sub <= diff) { // b > c
				a = i;
				b = r;
				c = b - sub;
				break;
			}
		}

		cout << a << ' ' << b << ' ' << c << '\n';
	}
	return 0;
}