22.06.24. 풀었던 문제들 - Codeforce #799 Div. 4 6/8

 오늘은 코드포스 #799 Div 4를 풀었다.

https://codeforces.com/contest/1692

Dashboard - Codeforces Round #799 (Div. 4) - Codeforces

시간 다되니까 쫄깃쫄깃 하다.

 

결과

 8문제 중 6문제 풀었다.

 

A번, B번, C번, D번

 단순히 풀면 되는 구현 문제

 

E번

  부분합과 two-pointer로 풀어야 하는 문제.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <map>
#include <set>

using namespace std;

void solve(){
	int n, s; cin>>n>>s;
	vector<int> v(n); cin>>v[0];
	for(int i = 1; i<n; i++){
		cin>>v[i];
		v[i] += v[i-1];
	}

	if(v[n-1] < s){
		cout<<"-1\n";
		return;
	}

	int start = 0, end;
	for(int i = n-1; i>=0; i--){
		if(v[i] == s){
			end = i;
			break;
		}
	}
	int max_len = end - start + 1;


	while(end < n){
		while(end + 1 < n && v[end + 1] == v[end]){ // end는 최대한 오른쪽 끝까지 당김
			end++;
		}

		int ssum = v[end] - (start - 1 < 0 ? 0 : v[start - 1]);
		if(ssum == s){
			max_len = max(max_len, end - start + 1);
			start++;
		}
		else if(ssum < s){ // end를 수가 바뀔 때까지 당기자
			while(end + 1 < n && v[end + 1] == v[end]){
				end++;
			}
			end++;
		} else{ // start를 수가 바뀔 때까지 당기자
			while(start + 1 <= end && v[start] == v[start + 1]){
				start++;
			}
			start++;
		}

		if(start > end){
			end = start;
		}
	}
	
	cout<<n - max_len<<'\n';
}

int main(void) {
	cin.tie(0);
	std::ios_base::sync_with_stdio(0);
	
	int t; cin>>t;
	while(t--){
		solve();
	}

	return 0;
}

// v에는 0과 1만 들어있고, total sum이 s와 같아지는 operation의 최솟값.
// 불가하다면 -1 출력

// psum : s[i] : s[0]부터 s[i]까지 합
// s[i] - s[j-1] : j to i까지 합
// tp 문제인 것 같은데
// s, e 두고

 

 다른 방식으로도 풀 수 있다. 이건 풀이보면서 놀랐다.

 prefix_sum은 항상 오름차순 정렬되어 있으니까, start point 기준으로 합이 s가 되는 upper bound -1의 위치를 찾을 수 있다. -> nlogn이다.

 

F번

 i, j, k를 전체 배열로 풀면 시간 초과가 나지만 이 문제가 묻는 것은 '1의 자리의 합이 3이 되는 i, j, k를 고를 수 있는지 여부'이다. 따라서 1의 자리만 저장하고, 같은 수가 나오면 그 1의 자리 수의 개수를 1 더한다.

 다음으로 그 숫자 개수만큼 vector에 넣고(만약 3보다 크거나 같다면 3개만 넣는다 - i, j, k 모두 그 수를 고르면 되기 때문), 그러면 그 vector size는 최대 30이다. 그러면 3중포문 돌려도 시간 내에 돌릴 수 있다.

 

G번

 어찌어찌 접근은 한 것 같은데 시간초과 난 문제. 그리고 복기하는 과정에서 이 접근이 틀렸음을 깨달았다! 나는 nk로 풀고 있었던 것... 이 문제는 sliding window로 푸는 문제다. 

 먼저 모든 i에 대해 $a_{i} < 2 * a_{i+1}$인지 여부를 체크하고 vector에 넣는다. true면 1, 아니면 0. 혹시 int 범위를 초과할 수 있으니 나누기나 long long을 사용해야 할 것이다. 그리고 1이 k개 연속된다면 k+1개의 수열이 위 조건을 만족하게 된다. --- 여기까진 풀었다.

 이후 1이 k개 연속되는지를 찾으면 되는 문젠데, 나는 2중포문을 써버려서(시간이 촉박했다) nk로 풀고 만 것이었다.

 그러나 sliding window를 이용한다면, 0~k-1, 1~k, ... , n-k+1~k를 모두 확인하는 데 O(n-k)의 시간이 걸리고, 한번 progress하는 데 O(1)의 시간이 걸리기 때문에 시간 내에 풀 수 있다.

 방금 보니 주석에 'sliding window인 듯!' 적어놨네 ㅋㅋㅋㅋㅋ

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <queue>
#include <map>
#include <set>

using namespace std;

void solve(){
	int n, k; cin>>n>>k;
	vector<int> arr(n);
	for(int i = 0;i <n; i++){
		cin>>arr[i];
	}

	vector<int> v(n); v[0] = 0;
	int flag;
	for(int i = 1; i<n; i++){
		flag = 0;
		if(arr[i] > arr[i-1] / 2) flag = 1;
		v[i] = flag;
	}
	
	int answer = 0, cur_point = 0;
	for(int i = 0; i<k; i++){
		cur_point += v[i];
	}
	if(cur_point == k) answer++;

	for(int i = k; i<n; i++){
		cur_point += v[i] - v[i-k];
		if(cur_point == k) answer++;
	}
	cout<<answer<<'\n';
}

int main(void) {
	cin.tie(0);
	cout.tie(0);
	std::ios_base::sync_with_stdio(0);
	
	int t; cin>>t;
	while(t--){
		solve();
	}

	return 0;
}

/*
arr[i] < 2 * arr[i+1]이 가능하다면 'true - 해당 array는 포함될 수 있음' 표시
20 22 19 84
1 1 1 1

sliding window인 듯!

*/

 

H번

 음... 어렵군. 내일 마저 풀어봐야겠다.