Codeforces Round #677 (Div. 3)

티스토리 뷰

카테고리 없음

Codeforces Round #677 (Div. 3)

[gunwookim] 2020. 10. 21. 01:12

오랜만에 딥3가 나와서 한번 쳐봤다.

올솔이 1시간 컷이 나는거 보니 실력이 늘긴 늘었나 보다 (옛날엔 딥3 4~5솔..)

D 까지는 간단하게 설명해 주겠다. (사실 거의 다 간단간단해서 편하게 듣는게 좋을 것 같다)

A - Boring Apartments (1분)

그냥 시뮬레이션 문제다.

#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define all(v) v.begin(),v.end()
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast") 
#pragma gcc optimize("unroll-loops")
using namespace std;
const int INF = 1e9;
const long long llINF = 1e18;
long long mod;
typedef long long ll;
typedef long double ld;
typedef pair <int,int> pi;
typedef pair <ll,ll> pl;
typedef vector <int> vec;
typedef vector <pi> vecpi; 
typedef long long ll;
int n;
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	int T; cin >> T;
	//int T = 1;
	while(T--) {
		cin >> n;
		int d = 0,rn = n;
		while(n) {
			d++;
			n /= 10;
		}
		n = rn;
		cout << (n%10-1)*10+d*(d+1)/2 << '\n';
	}
}

B - Yet Another Bookshelf (6분)

가장 왼쪽에 나타나는 1 과 가장 오른쪽에 나타나는 1 사이에 있는 0의 개수가 최소 연산 횟수다.

증명을 알아서 해보길 바란다. (절대 귀찮아서 그러는게 아니다)

#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define all(v) v.begin(),v.end()
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast") 
#pragma gcc optimize("unroll-loops")
using namespace std;
const int INF = 1e9;
const long long llINF = 1e18;
long long mod;
typedef long long ll;
typedef long double ld;
typedef pair <int,int> pi;
typedef pair <ll,ll> pl;
typedef vector <int> vec;
typedef vector <pi> vecpi; 
typedef long long ll;
int n;
int a[55];
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	int T; cin >> T;
	//int T = 1;
	while(T--) {
		cin >> n;
		int st = 0,en = 0;
		for(int i = 1;i <= n;i++) {
			cin >> a[i];
			if(a[i]) {
				if(!st) st = i;
				en = i;
			}
		}
		int cnt = 0;
		for(int i = st;i <= en;i++) cnt += 1-a[i];
		cout << cnt << '\n';
	}
}

C - Dominant Piranha (11분)

가장 큰 피라냐에 인접한 피라냐 중 작은게 하나라도 있으면 무조건 가능하다.

가장 큰 피라냐가 그 피라냐 보다 작은 피라냐를 먹으면 수족관에서 유일한 가장 큰 피라냐가 되기 때문이다.

그러면 모든 피라냐를 먹어 치울 수 있다.

#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define all(v) v.begin(),v.end()
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast") 
#pragma gcc optimize("unroll-loops")
using namespace std;
const int INF = 1e9;
const long long llINF = 1e18;
long long mod;
typedef long long ll;
typedef long double ld;
typedef pair <int,int> pi;
typedef pair <ll,ll> pl;
typedef vector <int> vec;
typedef vector <pi> vecpi; 
typedef long long ll;
int n;
int a[300005];
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	int T; cin >> T;
	//int T = 1;
	while(T--) {
		cin >> n;
		int mx = 0,st = 0,en = 0;
		for(int i = 1;i <= n;i++) {
			cin >> a[i];
			mx = max(mx,a[i]);
		}
		a[0] = a[n+1] = INF;
		int ch = -1;
		for(int i = 1;i <= n;i++) {
			if(a[i] == mx) {
				if(a[i-1] < a[i]||a[i] > a[i+1]) ch = i;
			}
		}
		cout << ch << '\n';
	}
}

D - Districts Connection (15분)

일단 맨 처음 나온 갱을 기준으로 삼는다. (a[1])

a[1]과 다른 갱에 있는 모든 갱을 1과 연결한다.

a[1]과 같은 갱이랑 a[1]과 다른 갱중 아무 갱과 연결한다.

만약 a[1]과 같은 갱이 n개라면 불가능하다. 나머지 경우에는 모두 가능하다.

#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define all(v) v.begin(),v.end()
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast") 
#pragma gcc optimize("unroll-loops")
using namespace std;
const int INF = 1e9;
const long long llINF = 1e18;
long long mod;
typedef long long ll;
typedef long double ld;
typedef pair <int,int> pi;
typedef pair <ll,ll> pl;
typedef vector <int> vec;
typedef vector <pi> vecpi; 
typedef long long ll;
int n;
int a[5005];
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	int T; cin >> T;
	//int T = 1;
	while(T--) {
		cin >> n;
		int is = 0,wi = 0;
		for(int i = 1;i <= n;i++) {
			cin >> a[i];
			if(!is) is = a[i];
			else if(is != a[i]) is = -1;
		}
		if(is != -1) {
			cout << "NO\n";
			continue;
		}
		cout << "YES\n";
		for(int i = 1;i <= n;i++) {
			if(a[i] != a[1]) {
				cout << 1 << ' ' << i << '\n';
				wi = i; 
			}
		}
		for(int i = 2;i <= n;i++) {
			if(a[1] == a[i]) {
				cout << i << ' ' << wi << '\n';
			}
		}
	}
}

E - Two Round Dances (20분)

내가 싫어하는 수학이 나왔다.

딱히 어려운 수학은 아니라서 다행히 풀 수 있었다.

경우의 수를 세어보자.

반 반으로 찢어지는 경우 $nCn/2$

n/2개로 이루어진 서클에서 자리를 배치하는 경우의 수 (원순열) $(n/2-1)!$

첫번째 서클과 두번째 서클이 자리가 바뀌는 중복 처리 $1/2$

다 곱해보면 된다.

$nCn/2$ * $(n/2-1)^{2}$ * $1/2$

참 쉽죠?

#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define all(v) v.begin(),v.end()
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast") 
#pragma gcc optimize("unroll-loops")
using namespace std;
const int INF = 1e9;
const long long llINF = 1e18;
long long mod;
typedef long long ll;
typedef long double ld;
typedef pair <int,int> pi;
typedef pair <ll,ll> pl;
typedef vector <int> vec;
typedef vector <pi> vecpi; 
typedef long long ll;
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	//int T; cin >> T;
	int T = 1;
	while(T--) {
		ll n,d = 1; cin >> n;
		for(ll i = n/2+1;i <= n;i++) d *= i;
		for(ll i = 1;i <= n/2;i++) d /= i;
		ll f = 1;
		for(ll i = 1;i <= n/2-1;i++) f *= i;
		cout << d*f*f/2LL << '\n';
	}
}

F - Zero Remainder Sum (46분)

터졌습니다 ^^

~~너무 시간을 잡아먹은 문제다.~~

~~나만 $dp$식을 드럽게 짠건지는 잘 모르겠다.~~

~~$dp[i][j][k][l]$ : $i$번째 행 $j$번째 열까지 봤으며 $i$행에서 $k$개 골랐고 지금까지 합한 값을 $K$로 나눈 나머지가 $l$일때 가능한 최댓값~~

~~각 행에서 첫번째 열일때 따로 처리를 해줘야 한다. (그 전 행에서 넘어오는 작업)~~

~~너무 드럽쥬? 어쩔 수 없어유 이거밖에 안떠올랐어유 죄송해유~~

#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define all(v) v.begin(),v.end()
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast") 
#pragma gcc optimize("unroll-loops")
using namespace std;
const int INF = 1e9;
const long long llINF = 1e18;
long long mod;
typedef long long ll;
typedef long double ld;
typedef pair <int,int> pi;
typedef pair <ll,ll> pl;
typedef vector <int> vec;
typedef vector <pi> vecpi; 
typedef long long ll;
int d[71][71][40][71];
int n,m,K;
int a[75][75];
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	//int T; cin >> T;
	int T = 1;
	while(T--) {
		cin >> n >> m >> K;
		for(int i = 1;i <= n;i++) {
			for(int j = 1;j <= m;j++) cin >> a[i][j];
		}
		for(int i = 0;i <= n;i++) {
			for(int j = 0;j <= m;j++) {
				for(int k = 0;k <= (m+1)/2;k++) {
					for(int l = 0;l < K;l++) d[i][j][k][l] = -INF;
				}
			}
		}
		d[0][m][0][0] = 0;
		for(int i = 1;i <= n;i++) {
			for(int j = 1;j <= m;j++) {
				if(j == 1) {
					for(int k = 0;k <= (m)/2;k++) {
						for(int l = 0;l < K;l++) {
							d[i][1][0][l] = max(d[i][1][0][l],d[i-1][m][k][l]);
							d[i][1][1][(l+a[i][j])%K] = max(d[i][1][1][(l+a[i][j]%K)],d[i-1][m][k][l]+a[i][j]);
						}
					}
					continue;
				}
				for(int k = 0;k <= (m)/2;k++) {
					for(int l = 0;l < K;l++) {
						d[i][j][k][l] = max({d[i][j][k][l],d[i][j-1][k][l],(!k ? -INF : d[i][j-1][k-1][(l-a[i][j]+100*K)%K]+a[i][j])});
					}
				}
			}
		}
		int ans = 0;
		for(int k = 0;k <= (m)/2;k++) {
			ans = max(ans,d[n][m][k][0]);
		}
		cout << ans;
	}
}

G - Reducing Delivery Cost (67분)

드디어 마지막 문제다.

먼저 모든 $x$ -> $y$ 로 가는 최소 거리를 구해 놓는다.

각 간선에 대해 모든 경우를 다 해보는데,

이 간선의 양 끝을 $x$, $y$ 라 두고 $i$번째 쿼리의 시작, 끝을 각각 $st$, $en$ 이라 한다.

이제 우린 $x$ -> $y$ 간선을 쓰거나 안쓰거나 둘 중 하나의 선택을 하여 최소 거리를 구할 수 있다.

안쓰는 경우는 그냥 $dist[st][en]$이고 쓰는 경우는 $min(dist[st][x]+dist[x][y](=0)+dist[y][en],dist[st][y]+dist[y][x](=0)+dist[x][en])$ 임을 알 수 있다!

저 두 값을 $min$ 해보면 각 쿼리의 최소 거리를 $O(1)$만에 구할 수 있다.

총 시간 복잡도는 $O(N^{2}logN)$ 이다.

#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define all(v) v.begin(),v.end()
#pragma gcc optimize("O3")
#pragma gcc optimize("Ofast") 
#pragma gcc optimize("unroll-loops")
using namespace std;
const int INF = 1e9;
const long long llINF = 1e18;
long long mod;
typedef long long ll;
typedef long double ld;
typedef pair <int,int> pi;
typedef pair <ll,ll> pl;
typedef vector <int> vec;
typedef vector <pi> vecpi; 
typedef long long ll;
int n,m,k,c[1005];
int d[1005][1005];
vecpi v[1005];
pi q[1005];
vector <pair<pi,int>> edge;
 
void dist(int st) {
	priority_queue <pi> q;
	q.push({0,st});
	memset(c,0,sizeof(c));
	while(!q.empty()) {
		auto x = q.top(); q.pop();
		if(c[x.y]) continue;
		c[x.y] = 1;
		d[st][x.y] = -x.x;
		for(pi i : v[x.y]) {
			q.push({x.x-i.y,i.x});
		}
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(0);
	//int T; cin >> T;
	int T = 1;
	while(T--) {
		cin >> n >> m >> k;
		for(int i = 1;i <= m;i++) {
			int x,y,z; cin >> x >> y >> z;
			edge.pb({{x,y},z});
			v[x].pb({y,z});
			v[y].pb({x,z});
		}
		for(int i = 1;i <= k;i++) {
			cin >> q[i].x >> q[i].y;
		}
		for(int i = 1;i <= n;i++) dist(i);
		int ans = INF*2,sum;
		for(auto i : edge) {
			sum = 0;
			int x = i.x.x, y = i.x.y, z = i.y;
			for(int j = 1;j <= k;j++) {
				sum += min({d[q[j].x][q[j].y],d[q[j].x][x]+d[y][q[j].y],d[q[j].x][y]+d[x][q[j].y]});
			}
			ans = min(ans,sum);
		}
		cout << ans;
	}
}

후 드디어 문제 풀이가 끝났다.

문제를 푸는 것 보다 풀이를 쓰는게 더 어려운거 같다 ㅋㅋ

아직 필력이 딸려서 잘 쓰지는 못하지만 좋게 봐주면 좋을 것 같다!

공지사항

최근에 올라온 글

최근에 달린 댓글

Total

Today

Yesterday

링크

TAG more

« 2024/05 »
일	월	화	수	목	금	토
			1	2	3	4
5	6	7	8	9	10	11
12	13	14	15	16	17	18
19	20	21	22	23	24	25
26	27	28	29	30	31

글 보관함

뉴비의 PS 낙서장

티스토리 뷰

Codeforces Round #677 (Div. 3)

티스토리툴바