AtCoder ABC 253 풀이

https://atcoder.jp/contests/abc253/tasks

Tasks - NOMURA Programming Contest 2022（AtCoder Beginner Contest 253）

 

 

A. 

항상 a<c가 되게 하고 a<=b and b<=c를 확인해주면 됩니다. 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int a, b, c;
	cin >> a >> b >> c;
	if (a > c) swap(a, c);
	if (a <= b && b <= c) {
		cout << "Yes\n";
	}
	else cout << "No\n";
}

 

 

 

B. 

두 "O" 사이의 맨해튼 거리를 출력해주면 됩니다.

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int h, w; cin >> h >> w;
	vector<pair<int, int>>v;
	for (int i = 0; i < h; i++) {
		for (int j = 0; j < w; j++) {
			char s; cin >> s;
			if (s == 'o') {
				v.push_back({ i,j });
			}
		}
	}
	cout << abs(v[0].first - v[1].first) + abs(v[0].second - v[1].second);
}

 

 

 

C. 

std::multiset 사용법 문제입니다. 에디토리얼에 자세한 기본 문법이 있습니다.

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
multiset<int> ms;

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int q; cin >> q;
	while (q--) {
		int op, x, c;
		cin >> op;
		if (op == 1) {
			cin >> x;
			ms.insert(x);
		}
		else if (op == 2) {
			cin >> x >> c;
			while (c-- && ms.find(x) != ms.end()) {
				ms.erase(ms.find(x));
			}
		}
		else {
			cout << *ms.rbegin() - *ms.begin() << '\n';
		}
	}
}

 

 

 

D. 

1~N중 a 또는 b의 배수가 아닌 것의 합을 찾는 문제입니다. 포함배제 원리에 의해

전체 합에서 (a의 배수 합 + b의 배수 합 - a, b의 배수 합)을 빼주면 됩니다. 

a의 배수를 a, 2a, ,,..., ka 라고 할 때 (k=n/a) 합은 a*k*(k+1)/2로 O(1)에 구해주면 됩니다.

#include<bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	ll n, a, b;
	cin >> n >> a >> b;
	ll ans = n * (n + 1) / 2;
	ans -= a * (n/a * (n/a + 1) / 2);
	ans -= b * (n/b * (n/b + 1) / 2);
	ll k = lcm(a, b);
	ll c = n / k;
	ans += k * c * (c + 1) / 2;
	cout << ans;
}

 

 

 

E. 

dp[i][j]를 i번째까지 채웠고 마지막 수 A[i]가 j일 때 조건을 만족하는 경우의 수라고 정의합니다. 

a[i]=j이므로 a[i-1]은 1~j-k , j+k~n까지 가능합니다. 

따라서 dp[i][j]=(dp[i-1][1]+....+dp[i-1][j-k])+(dp[i-1][j+k]+....+dp[i-1][n]) 이 됩니다.

이걸 naive 하게 채우면 O(NM*M)이므로 최적화가 필요합니다.

관찰 1. 우선 i와 i-1만을 참조하고 두번째 인자에 영향을 안주므로 첫번째 인자는 삭제해도 됩니다. 

즉, dp table이 채워진 상태에서 다시 새롭게 dp[j]를 채워주면 잘 갱신됩니다.  

 

관찰 2. dp[1]+...+dp[j-k]과 dp[j+k]+....+dp[n]은 누적합으로 O(1)에 처리할 수 있습니다.

dp table이 채워진 상태에서 누적합을 만들어두는데 O(M)이 걸립니다. 그러면 dp갱신은 O(1)에 됩니다.

따라서 시간복잡도 O(NM)에 해결할 수 있습니다. 

k=0인 예외상황만 주의해줍시다. 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 998244353;

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int n, m, k;
	cin >> n >> m >> k;
	vector<ll>dp(m + 1, 1);
	for (int i = 1; i < n; i++) {
		vector<ll>psum(m + 1);
		for (int j = 1; j <= m; j++) {
			psum[j] = (psum[j - 1] + dp[j]) % mod;
		}
		for (int j = 1; j <= m; j++) {
			int l = max(0, j - k);
			int r = min(m, j + k - 1);
			if (!k) {
				dp[j] = psum[m];
			}
			else {
				dp[j] = (psum[m] - psum[r] + psum[l] + mod) % mod;
			}
		}
	}
	ll ans = 0;
	for (int i = 1; i <= m; i++) {
		ans = (ans + dp[i]) % mod;
	}
	cout << ans << '\n';
}