22.08.05. 풀었던 문제들 - Codeforces #811 Div. 3 4/7

Codeforces #811 Div. 3

https://codeforces.com/contest/1714

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

 

결과

많이 멀었군.

A, B, C, E번은 시간 내에 풀고 제출했다. 7문제 중 4문제를 맞췄다.

 

A번

 주어진 시간인 H, M에 대해 입력 시간이 더 느리다면 그대로 두고, 더 빠르다면 24*60을 더한 후 [입력 시간 - 주어진 시간]의 최솟값을 구하는 손풀기 문제

int timeToInt(int H, int M){
	return 60 * H + M;
}

pii intToTime(int t){
	return {(t/60)%24, t%60};
}

void solve(){
	int n, H, M; cin>>n>>H>>M;
	int startTime = timeToInt(H, M);
	int hi, mi;
	vector<int> minutes(n);
	for(int i = 0; i<n; i++){
		cin>>hi>>mi;
		minutes[i] = timeToInt(hi, mi);
		if(minutes[i] < startTime) minutes[i] += 1440;
	}
	sort(minutes.begin(), minutes.end());
	int result = *lower_bound(minutes.begin(), minutes.end(), timeToInt(H, M)) - startTime;
	pii answer = intToTime(result);
	cout<<answer.first<<' '<<answer.second<<'\n';
}

 

B번

 어떤 수열이 주어질 때, 앞에서부터 n개를 지워서 같은 숫자가 존재하지 않게 만드는 n의 최소값을 구하는 문제. 거꾸로 생각해서 뒤에서부터 세고 숫자가 2개 이상인 경우 거기서 stop해버리면 된다.

void solve(){
	int n; cin>>n;
	vector<int> arr(n);
	for(int i = n-1; i>=0; i--) cin>>arr[i];

	// sequence의 모든 숫자가 distinct

	// 모든 수의 개수가 1 이하로 맞춰질 때 까지 첫 자를 지움
	// 뒤에서부터 세서 개수가 2인 원소가 발견되는 즉시 멈추고 그 index부터 따짐
	map<int, int> m;

	int i;
	for(i = 0; i<n; i++){
		if(m.find(arr[i]) == m.end()){ // not exist in map
			m[arr[i]] = 1;
		}
		else{ // exist in map
			break;
		}
	}
	cout<<n-i<<'\n';
}

 

C번

 greedy 문제. 자리수들의 합 s가 주어졌을 때 만들 수 있는 제일 작은 수를 만드는 문제다. 제일 작은 수를 만들기 위해서는 숫자의 개수가 최소여야 하고, 그걸 위해서는 큰 수부터 s에서 빼야 한다. s에서 9를 빼고, 8을 빼고 ... 를 반복해야 한다는 뜻. 만약 뺄 수 없다면 빼는 수를 1 줄이고, 이렇게 만든 수를 오름차순 배열하면 된다.

void solve(){
	int s; cin>>s;
	vector<int> result;
	int num = 9;
	while(s != 0){
		if(s - num >= 0){
			s -= num;
			result.push_back(num);
		}
		num--;
	}

	for(int i = result.size()-1; i>=0; i--){
		cout<<result[i];
	}
	cout<<'\n';

	// digit들의 합인 s, 모든 digit은 distinct

	// 큰 수부터 뽑고 정렬하면 되겠군 - 이게 자리수를 제일 덜 먹음
	// 9를 뽑고(안되면 8을 뽑고, ... 안되면 1을 뽑는 식으로)
}

 

E번

 규칙 찾기 문제. 5는 다음 연산으로 0이 되고, 0은 평생 0이다. 1, 3, 5, 7, 9는 다음 연산으로 2, 4, 6, 8이 되며, 2, 4, 6, 8은 그 사이에서 규칙이 있다. 따라서 5는 0으로 만들고, 0는 냅두고, 나머지 모든 수는 첫 자리 수가 2가 될 때까지 돌린다.

 이렇게 돌린 이후, 0이 있는 경우 - 0 이외에 다른 수가 있다면 만들 수 없고, 그렇지 않다면 만들 수 있음. 0이 하나라도 없는 경우 - 십의 자리가 20의 배수로 차이나야 만들 수 있다. 그렇지 않으면 만들 수 없음.

/*
0은 평생 0
5는 다음 연산으로 0이 됨
만약 5가 있다면 다음 연산을 해 주고,
 1) arr 중 0이 아닌 것이 하나라도 있거나
 2) 10의 자리가 다르다면
NO, 아닌 경우 YES

2, 4, 6, 8은 x2 - x4 - x8 - (x+1)6 - (x+2)2로 돌아감
1은 다음 연산으로 2가 되고
3은 다음 연산으로 6
5는 다음 연산으로 0
7은 다음 연산으로 4
9는 다음 연산으로 8이 됨

0, 5를 제외하고는 첫 자리가 2가 될 때 까지 다음 연산을 돌림
그리고 10의 자리가 20의 배수로 차이나지 않는 경우 - false

*/

void solve(){
	int n; cin>>n;
	vector<int> arr(n);
	for(int i = 0; i<n; i++){
		cin>>arr[i];
		if(getLastDigit(arr[i]) == 5) arr[i] = calculate(arr[i]);
		else if(getLastDigit(arr[i]) == 0) continue;
		else{
			while(getLastDigit(arr[i]) != 2){
				arr[i] = calculate(arr[i]);
			}
		}
	}

	string answer = Yes;
	// 0짜리가 하나라도 있으면 전부 동일해야 함
	bool isDigitZero = false;
	for(int elem : arr){
		if(getLastDigit(elem) == 0){
			isDigitZero = true;
			break;
		}
	}
	if(isDigitZero){
		for(int i = 1; i<arr.size(); i++){
			if(arr[i] != arr[0]){
				answer = No;
				break;
			}
		}
	}
	else{ // 0, 5짜리가 하나도 없는 경우에는 10자리수 차이가 모두 20이어야 함.
		for(int i = 1; i<arr.size(); i++){
			if((arr[i] - arr[0]) % 20 != 0){
				answer = No;
				break;
			}
		}
	}
	cout<<answer;
}

 

 

Upsolving

D번

 일단 풀긴 풀었는데.. 뭔가 이상하다. 아무튼 문제는 입력 string t와 string set sarr이 주어질 때, 최소의 sarr을 이용해서 t를 표현하는 방법이다.(조금 간략하게 바꾸어 설명했다.)

 처음에는 그냥 '최대로 채울 수 있는 걸 계속 채워'라고 생각했는데 이러면 시간초과가 난다. 그래서 '앞에서부터, 최대로 채울 수 있을 만큼 채워'라고 greedy하게 생각했다. 그리고 굳이 black을 red로 바꿨는지 검사할 필요 없이, [sarr을 사용했을 때 최대로 전진한 index]를 선택해버리면 된다.

 먼저 '지금 보고 있는, black인 index인 blackidx'와 '이전의 blackidx값인 prevbidx' 2개 값을 두고 생각해 보자. 우리의 목표는 최소의 sarr을 이용해 t를 채우는 것이기 때문에, 최대한 긴 sarr을 가져오면 될 것이다 (-> 이 생각이 틀렸다. 긴 sarr을 가져오더라도 갱신되지 않는 부분이 있기 때문.) 따라서 blackidx와 prevbidx 사이를 탐색하면서 black을 더 많이 red로 바꾸는 sarr을 택하고(이게 while문 내의 for loop이다) 이 sarr들을 결과 집합에 넣으면 된다. 생각보다 어렵지 않은 문제였는데 시간이 걸렸는데, 이유는...

void solve(){
	string t; cin>>t; // text
	int n; cin>>n; // number of strings in the set
	vector<string> sarr(n); // string in the set.
	
	for(int i = 0; i<n; i++){
		cin>>sarr[i];
	}

	vector<pii> answer;
	int blackidx = 0, prevbidx = -1; 
	// blackidx : 아직 black인 index 중 제일 왼쪽 것
	// prevbidx : 이전 blackidx
	while(blackidx < t.length()){
		int blackidx_temp = blackidx; // 갱신 될 수도 있기 때문에 이렇게 두고 쓴다.
		int prevbidx_temp = -1;
		int sarridx_temp = -1;
		for(int tidx = prevbidx + 1; tidx <= blackidx; tidx++){
			for(int i = 0; i<n; i++){
				if(t.substr(tidx, sarr[i].length()) == sarr[i]){
					if(blackidx_temp < (int)(tidx + sarr[i].length())){ // 최대한 뒤로 늘림 (greedy)
						prevbidx_temp = tidx;
						blackidx_temp = tidx + sarr[i].length();
						sarridx_temp = i;
					}
				}
			}
		}
		if(prevbidx_temp == -1){
			cout<<"-1\n";
			return;
		}
		blackidx = blackidx_temp;
		prevbidx = prevbidx_temp;
		answer.push_back({sarridx_temp+1, prevbidx_temp + 1});
	}
	cout<<answer.size()<<'\n';
	for(pii &p : answer){
		cout<<p.first<<' '<<p.second<<'\n';
	}
}

 

 위 코드에서는 prevbidx_temp = -1로 두고 이게 갱신되었는지 여부로 'sarr을 택할 수 있는지'여부를 선택했는데, 처음에는 이렇게 하지 않고 아래 사진의 코드처럼 boolean type의 isMatch 변수를 두고 풀었다. 이렇게 풀면 time limit이고 위 코드처럼 2-3줄만 바꿔주면 15ms로 accept이 나온다. 왜지...?

 그리고 못 푼 이유는 접근은 어떻게 했는데 잘못된 방식으로 푼 것이 문제였다. 분발하자!

 

F번

 뭐지? 음.. constructive algorithm이라고는 하고, 음.... 어렵다. 이건 먼 미래에 깨부하면 그때 풀 수 있을 것 같다. 스킵.

 

G번

 상당히 흥미로운 문제였다. 최근에 이진 탐색을 계속 건들여서 그런가? 풀이가 딱 생각났다.

 먼저 문제는 [root to i] path에서 aj의 sum = Ai일 때, ri = sum of bj가 Ai보다 작거나 같은 maximum prefix이다. 

 root부터 leaf까지 [누적 aj, [bj의 psum]] 이렇게 DFS로 내려가게 하고 bj의 psum list에서 에서 '누적 aj'의 upper bound를 찾으면 된다. 그러면 DFS는 O(V + E), 각 탐색에서 log(depth)번 탐색한다 - O(log(max_depth)(V+E))이고, 그러면 nlogn이다.

 오타?로는 signed integer overflow가 나서... 솔직히 integer overflow가 날 거라곤 생각 못했다. 숫자 범위는 $10^{9}$, 10억임에도 불구하고. 아직 미숙하다!으으으윽 문제 못 푼 이유는 솔직히 문제도 안읽히고 시간부족으로 못 푼 문제 같다. D번에서 멘탈 와장창 하기도 했고.

ll n = 200000;
vector<vector<ll>> childs(n+1); // childs[i] : vertex i의 child list
vector<ll> a(n+1), b(n+1); // a[i] : aj value from p[i] to i

vector<ll> b_psum; // bj의 psum
vector<ll> answer;

void DFS(ll parent, ll ajsum){
	for(ll child : childs[parent]){
		ajsum += a[child];
		b_psum.push_back((b_psum.empty() ? 0LL : b_psum[b_psum.size()-1])+ b[child]);

		answer[child] = upper_bound(b_psum.begin(), b_psum.end(), ajsum) - b_psum.begin();
		DFS(child, ajsum);

		ajsum -= a[child];
		b_psum.pop_back();
	}
}

void solve(){
	cin>>n; // n : # of vertices
	ll pj, aj, bj;
	
	for(ll i = 0; i<=n; i++){ // reset
		childs[i].resize(0);
	}
	for(ll i = 2; i<=n; i++){
		cin>>pj>>aj>>bj; // pj : vertex j의 parent, [pj - j]의 edge
		childs[pj].push_back(i);
		a[i] = aj;
		b[i] = bj;
	}

	b_psum.resize(0);
	answer.resize(n+1);

	DFS(1, 0);
	for(ll i = 2; i<=n; i++) cout<<answer[i]<<' ';
	cout<<'\n';

	/*
		[root to i] path에서 aj의 sum = Ai
		ri = sum of bj가 Ai보다 작거나 같은 maximum prefix

		6 : ajsum = 2, bj 누적합 = [1], ajsum의 upper bound : 2 -> 1
		8 : ajsum = 6, bj 누적합 = [1, 4], ajsum의 upper bound : 3 -> 2
		9 : ajsum = 7, bj 누적합 = [1, 4, 7], ajsum의 upper bound : 4 -> 3

		2 : ajsum : 5, bj누적합 = [6], ajsum의 uppber bound : 1 -> 0
		4 : ajsum : 14, bj누적합 = [6, 16], ajsum의 upper bound : 2 -> 1
		3 : ajsum = 19, bj누적합 = [6, 16, 17], ajsum의 upper bound : 4 -> 3

		root부터 leaf까지 [누적 aj, [bj의 psum]] 이렇게 내려가게 하고 bj의 psum에서 aj의 ub 찾으면 된다.
	*/
}