Codeforces Round #642 (Div. 3)

Codeforces Round #642 (Div. 3)를 쳤다아아

나도 이제 성장한것 같다. 딥3 올솔이라니!

원래는 4솔정도 였는데 실력이 늘었다!

 

올솔

 

A - Most Unstable Array

 

$n$개의 자리에 숫자들을 써넣을 건데 수들의 총합이 $m$이 되어야 한다.

이때 인접한 두 수 의 차이들의 합의 최댓값을 구하라는 문제다.

어떻게 분배하든 중간에 하나로 모으는게 최적이다. ($0$ $0$ $...$ $0$ $m$ $0$ $...$ $0$ $0$) 

$n = 1$ 인 경우와 $n = 2$ 인 경우만 따로 처리하면 된다.

 

#include <bits/stdc++.h>
using namespace std;
 
int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    int T;
    cin >> T;
    while(T--) {
    	int n,m;
    	cin >> n >> m;
    	if(n == 1) cout << 0;
    	else if(n == 2) cout << m;
    	else cout << m*2;
    	cout << '\n';
    }
}

 

B - Two Arrays And Swaps

 

그리디임이 자명하므로 $a$ 배열에서 가장 작은수와 $b$ 배열에서 가장 큰 수를 뽑아서 스왑했을때 합이 더 줄어든다면 그만한다. 또는 k번을 채운다.

 

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
int a[35],b[35],n,sum;
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	int T;
	cin >> T;
	while(T--) {
		int k;
		cin >> n >> k;
		sum = 0;
		for(int i = 1;i <= n;i++) cin >> a[i], sum += a[i];
		for(int i = 1;i <= n;i++) cin >> b[i];
		sort(a+1,a+n+1); sort(b+1,b+n+1); reverse(b+1,b+n+1);
		for(int i = 1;i <= k;i++) {
			if(b[i]-a[i] <= 0) break;
			sum += b[i]-a[i];
		}
		cout << sum << '\n';
	}
}

 

C - Board Moves

 

이 문제에서는 $n$이 홀수로 주어지는걸 잘 관찰해보면 무조건 중점이 있게된다.

이제 모든 셀들을 중점으로 이동시키면, 이 방법이 셀들이 움직이는 횟수가 최소가 됨이 자명하다.

계산을 알아서 하실 수 있죠?

 

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
ll n;
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	int T;
	cin >> T;
	while(T--) {
		cin >> n;
 
		ll ans = 0;
		for(ll i = 1;i <= n/2+1;i++) {
			ans += (i-1)*((i*2-1)*4-4);
		}
		cout << ans << '\n';
 
	}

 

D - Constructing the Array

 

그냥 말한데로 짜면 된다. $priority_queue$ 에 {길이,구간} 으로 넣으면 길이가 큰 것부터 튀어 나오는데, 구간을 넣을때 $left$는 작은 순부터 뽑아야 하기 때문에 -를 붙여서 넣어줘야 한다. (-를 붙이면 최소 힙 처럼 길이가 같을때 $left$가 작은것부터 나온다.)

 

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
int n;
int a[200005],g;
priority_queue <pair<int,pair<int,int>>> q;
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	int T;
	cin >> T;
	while(T--) {
		cin >> n;
		g = 0;
		q.push({n,{-1,n}});
		for(int i = 1;i <= n;i++) {
			auto x = q.top();
			q.pop();
			int l = -x.y.x;
			int r = x.y.y;
			int mid = (l + r) >> 1;
			a[mid] = ++g;
			if(mid-1-l+1 > 0) q.push({mid-1-l+1,{-l,mid-1}});
			if(r-mid > 0) q.push({r-mid,{-mid-1,r}});
		}
		for(int i = 1;i <= n;i++) cout << a[i] << ' ';
		cout << '\n';
	}
}

 

E - K-periodic Garland

 

우욱.., 재밋지도 않고 역겨운 문제다. (적어도 나는 그랬다)

위치 $mod$ $k$ 별로 묶어보면 1과 0으로 이루어진 k개의 이진 수열이 나오는데 우리는 각각의 이진 수열에 대해 구간을 하나 잡고 그 구간은 모두 1, 나머지는 모두 0 일때 최소 토글링 횟수 라고 표현이 가능하다.

이걸 잘 처리를 해주면 되는데 1인건 1, 0인건 -1로 원소를 재조정 했다. 이제 보면 연속 구간의 합의 최댓값을 찾는 문제로 변형이 가능하다. 이런 생각을 하다보면 백준의 연속합 문제가 떠오를 것이다.

 

그렇다. 이제 우리는 $k$개에 대해 다이나믹 점화식을 세운다음 돌려본다.

점화식은 $dp[i]$ $:$ $i$번째 숫자를 포함한다고 할때 가장 최대인 연속합 이라고 하면 $dp[i] = min(dp[i-1]+a[i],a[i])$ 가 나온다.

어떤 구간을 잡으면 구간을 제외한 모든 곳은 모두 0이 되어야 하므로 그것도 세줄려면 누적합을 사용하자.

그리고 다이나믹 테이블을 채우면서 어떤 구간이 이 답이 나오는지도 저장 하면서 가야 한다.

이 뒤는... 너무 드러우니 생략한다.( + 구간이 $l~r$ 이고 그 구간의 원소들의 합이 $x$라 하면 그 구간안에 있는 0의 수는 $(r-l+1)/2-x$개다)

 

코드가 매우 드러우니 양해 바란다..

 

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
int n,k;
int d[1000005],sum[1000005],allsum;
char in[1000005];
vector <int> a[1000005];
vector <int> s[1000005];
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	int T;
	cin >> T;
	while(T--) {
		cin >> n >> k;
		cin >> in;
		for(int i = 0;i < n;i++) sum[i] = 0, s[i].clear(), a[i].clear();
		allsum = 0;
		for(int i = 0;i < n;i++) {
			if(in[i] == '1') allsum++, sum[i%k]++, a[i%k].push_back(1);
			else a[i%k].push_back(-1);
			s[i%k].push_back((s[i%k].empty()?0:s[i%k].back())+(a[i%k].back()==1));
		}
		int ans = allsum,tans,l,r;
		for(int i = 0;i < k;i++) {
			tans = n;
			l = 0;
			for(int j = 0;j < a[i].size();j++) {
				if(!j) d[j] = a[i][j];
				else {
					if(d[j-1]+a[i][j] > a[i][j]) d[j] = d[j-1]+a[i][j];
					else {
						d[j] = a[i][j];
						l = j;
					}
				}
				tans = min(tans,allsum-sum[i]+(l==0?0:s[i][l-1])+((j-l+1)-d[j])/2+s[i].back()-s[i][j]);
			}
			ans = min(ans,tans);
		}
		cout << ans << '\n';
	}
}

 

F - Decreasing Heights

 

우리는 적당한 관찰을 통해서 배열에 있는 $n*m$ 개의 숫자중 하나는 고정하면 최선의 답이 나옴을 알 수 있다.

그래서 우린 $n*m$개의 원소에 대해 시작 숫자를 지정하고 다이나믹 테이블을 돌려 나가면 된다.

+ 그리고 갈 수 없는 경우도 체크해줘야 한다.

 

시간 복잡도는 $O(n^{2}m^{2})$이다.

 

#include <bits/stdc++.h>
#define x first
#define y second
using namespace std;
typedef long long ll;
ll d[105][105],a[105][105],c[105][105];
ll n,m;
 
ll cost(ll x,ll y) {
	if(x < y) return -1;
	return abs(x-y);
}
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	int T;
	cin >> T;
	while(T--) {
		cin >> n >> m;
		for(int i = 1;i <= n;i++) {
			for(int j = 1;j <= m;j++) cin >> a[i][j];
		}
		ll ans = 2e18;
		for(int x = 1;x <= n;x++) {
			for(int y = 1;y <= m;y++) {
				ll st = a[x][y]-x-y+2;
				memset(c,0,sizeof(c));
				for(int i = 1;i <= n;i++) {
					for(int j = 1;j <= m;j++) {
						if(cost(a[i][j],st+i+j-2) == -1) {
							c[i][j] = 1;
							continue;
						}
						if(i+j == 2) d[i][j] = cost(a[i][j],st);
						else if(i == 1) {
							if(c[i][j-1]) {
								c[i][j] = 1;
								continue;
							}
							d[i][j] = d[i][j-1]+cost(a[i][j],st+i+j-2);
						}
						else if(j == 1) {
							if(c[i-1][j]) {
								c[i][j] = 1;
								continue;
							}
							d[i][j] = d[i-1][j]+cost(a[i][j],st+i+j-2);
						}
						else {
							if(c[i-1][j]&&c[i][j-1]) {
								c[i][j] = 1;
								continue;
							}
							if(c[i-1][j]||c[i][j-1]) {
								if(!c[i-1][j]) d[i][j] = d[i-1][j]+cost(a[i][j],st+i+j-2);
								else d[i][j] = d[i][j-1]+cost(a[i][j],st+i+j-2);
							}
							else d[i][j] = min(d[i][j-1],d[i-1][j])+cost(a[i][j],st+i+j-2);
						}
					}
				}
				if(c[n][m]) continue;
				ans = min(ans,d[n][m]);
			}
		}
		cout << ans << '\n';
	}
}