AtCoder ABC 269 풀이

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

Tasks - UNICORN Programming Contest 2022(AtCoder Beginner Contest 269)

 

 

A.

(a+b)*(c-d)와 문자열 하나를 출력해주면 됩니다. 

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

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int a, b, c, d;
	cin >> a >> b >> c >> d;
	cout << (a + b) * (c - d) << '\n';
	cout << "Takahashi\n";
}

 

 

 

B.

사각형의 왼쪽윗점과 오른쪽아랫점을 출력해주면 됩니다. 

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

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int a = 11, b = 0, c = 11, d = 0;
	for (int i = 1; i <= 10; i++) {
		for (int j = 1; j <= 10; j++) {
			char s; cin >> s;
			if (s == '#') {
				a = min(a, i);
				b = max(b, i);
				c = min(c, j);
				d = max(d, j);
			}
		}
	}
	cout << a << " " << b << '\n';
	cout << c << " " << d << '\n';
}

 

 

 

C.

비트의 부분집합을 순회하는 문제입니다. 비트전체집합을 순회하는 테크닉은

전체집합을 M이라 할 때, s=(s-1)&M을 사용하면 됩니다. 

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

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	ll n; cin >> n;
	vector<ll>ans;
	for (ll s = n; s; s = (s - 1) & n) {
		ans.push_back(s);
	}
	ans.push_back(0);
	reverse(ans.begin(), ans.end());
	for (ll x : ans) {
		cout << x << '\n';
	}
}

 

 

 

D.

육각구조에서 컴포넌트의 개수를 묻는 문제입니다. O(N^2)에 모든 쌍을 유니온하여 컴포넌트를 

만들 수 있고 그 개수는 부모가 -1인 것들의 개수가 됩니다. (-1로 초기화할 시)

#include<bits/stdc++.h>
using namespace std;
int dx[] = { -1, -1, 0, 0, 1, 1 };
int dy[] = { -1, 0, -1, 1, 0, 1 };
int n, x[1001], y[1001], par[1001];

int find(int x) {
	return par[x] == -1 ? x : par[x] = find(par[x]);
}

void uni(int x, int y) {
	x = find(x), y = find(y);
	if (x != y) par[y] = x;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	memset(par, -1, sizeof(par));
	for (int i = 0; i < n; i++) {
		cin >> x[i] >> y[i];
	}
	for (int i = 0; i < n; i++) {
		for (int j = i + 1; j < n; j++) {
			for (int k = 0; k < 6; k++) {
				if (x[j] == x[i] + dx[k] && y[j] == y[i] + dy[k]) {
					uni(i, j);
				}
			}
		}
	}
	int ans = 0;
	for (int i = 0; i < n; i++) {
		ans += (par[i] == -1);
	}
	cout << ans << '\n';
}

 

 

E. 

pass

 

 

F. 

직사각형 집합이 주어질 때 그 안의 합을 구해주는 문제입니다.

2차원 누적합을 이용하면 누적합을 O(1)에 처리해줄 수 있습니다.

그렇다면 이제 (1,1)부터 (r,c)까지 합을 O(1)에 구해주면 됩니다. 

홀수열과 짝수열을 나누고 첫항들을 구합니다. 홀수열의 첫항은 1열의 합이고, 

짝수열의 첫항은 2열의 합입니다. 3열부터는 첫 항에 공차가 2MC인 등차수열이 됩니다. 

짝수열과 홀수열을 나눠서 등차수열 합을 열심히 구현해주면 됩니다. 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 998244353;
ll n, m, q, a, b, c, d;

ll go(ll r, ll c) {
    if (r < 1 || c < 1) return 0;
    ll ret = 0;
    ll cnt = (c + 1) / 2;
    ll temp = cnt * cnt;
    temp %= mod;
    ll nr = (r + 1) / 2;
    temp *= nr; temp %= mod;
    nr = (nr * (nr - 1)) / 2; nr %= mod;
    ll s1 = (2 * m * cnt) % mod;
    temp += nr * s1; temp %= mod;
    ret += temp; ret %= mod;
    if (r >= 2) {
        ll cnt = (c / 2);
        ll temp = cnt * (cnt + 1) + m * cnt;
        temp %= mod;
        ll nr = r / 2;
        temp *= nr; temp %= mod;
        nr = (nr * (nr - 1)) / 2; nr %= mod;
        ll s2 = (2 * m * cnt) % mod;
        temp += nr * s2; temp %= mod;
        ret += temp; ret %= mod;
    }
    return ret;
}

ll solve(ll r1, ll r2, ll c1, ll c2) {
    ll ret = go(r2, c2) - go(r1 - 1, c2) - go(r2, c1 - 1) + go(r1 - 1, c1 - 1);
    ret = (ret + 4 * mod) % mod;
    return ret;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m >> q;
	while (q--) {
		cin >> a >> b >> c >> d;
        cout << solve(a, b, c, d) << "\n";
	}
}