AtCoder ABC 246 풀이

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

Tasks - AtCoder Beginner Contest 246

 

 

 

A.

직사각형의 세 꼭짓점이 주어질 때 나머지 한 점을 출력해주는 문제입니다.

세 점이 주어지면 x,y좌표들의 최대, 최소는 모두 나왔으므로, 좌표를 저장한 뒤

방문하지 않은 좌표를 출력해주면 됩니다.  에디토리얼 풀이가 매우 훌륭합니다.

x, y좌표에 대한 XOR연산 1번으로 바로 답을 낼 수 있습니다. 같은 것끼리는 0이 되서,

주어진 세 점을 XOR한 결과는 한 번 등장한 점이 됩니다. 

#include<bits/stdc++.h>
using namespace std;
map<pair<int, int>, int>vis;
int x[3], y[3];

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	
	for (int i = 0; i < 3; i++) {
		cin >> x[i] >> y[i];
	}
	int X = x[0] ^ x[1] ^ x[2];
	int Y = y[0] ^ y[1] ^ y[2];
	cout << X << " " << Y << '\n';
}

 

 

 

 

B.

한 벡터의 단위벡터를 출력해주면 됩니다.

(a,b)의 단위벡터는 (a/d, b/d)이고, d=sqrt(a^2+b^2)이 됩니다.

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

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	double a, b;
	cin >> a >> b;
	double d = sqrt(a * a + b * b);
	cout << fixed << setprecision(8);
	cout << a / d << " " << b / d;
}

 

 

 

 

C.

그리디 문제입니다. 한 값을 최대한 작게 만드려면 쿠폰 a[i]/x개가 필요합니다.

우선 각 a[i]들이 음수가 되지 않을 때까지 쿠폰을 최대한 써줍니다.

왜 그래도 되냐면 a[i]가 음수가 되지 않는다면, 채우는 순서와 상관없이, 

a[i]들의 합 - k*x로 일정하기 때문입니다. 따라서 a[i]들이 음수가 되지 않을 때까지 각 값에다가

쿠폰을 써줍니다. 중간에 쿠폰을 다쓰면 답은 a[i]합-kx입니다.

이제 모든 시행 후 쿠폰이 남았다고 가정합니다. 이 때, a[i]/x개로 매번 x만큼 뺐으니까

각 a[i]들은 a[i]%x로 바뀝니다. 즉, 모든 a값들은 [0,x)에 있습니다. 이 때, 쿠폰을 쓰면, 

x가 빠지므로 0이 됩니다. 이 때부턴 큰 값부터 쿠폰을 써줘야 이득입니다. 

따라서 a%x들을 새로 정렬하고 큰 값부터 쿠폰을 써주면 그게 답입니다. 

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

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	int n, k, x;
	cin >> n >> k >> x;
	vector<int>a(n);
	for (int i = 0; i < n; i++) cin >> a[i];
	for (int i = 0; i < n; i++) {
		int cnt = min(a[i] / x, k);
		k -= cnt;
		a[i] -= cnt * x;
	}
	if (k > 0) {
		sort(a.rbegin(), a.rend());
		for (int i = 0; i < n; i++) {
			if (k <= 0) break;
			a[i] = 0;
			k--;
		}
	}
	cout << accumulate(a.begin(), a.end(), 0ll) << '\n';
}

 

 

 

 

D.

(a+b)(a^2+b^2)꼴 수중에 N이상의 가장 작은 값을 구하는 문제입니다.

우선 값이 1e18이하이므로 a와 b는 1e6이하입니다. 

a를 0부터 1e6까지 순회해봅시다. f(a,b)>=n이 되면서 최소가 되게 하려면

이 때 b는 계속 감소해야 합니다. 아래 그림을 참고하면 이해가 잘 될 것입니다. 

따라서 a를 순회하면서 b는 감소하면서 같이 순회할 수 있으므로, O(1e6)에 해줄 수 있습니다.

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

ll F(ll a, ll b) {
	return (a + b) * (a * a + b * b);
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	ll n; cin >> n;
	int j = (int)1e6;
	ll ans = 4e18;
	for (int i = 0; i <= (int)1e6; i++) {
		while (F(i, j) >= n && j >= 0) {
			j--;
		}
		ans = min(ans, F(i, j + 1));
	}
	cout << ans << '\n';
}

 

 

 

 

E.

비숍을 폰들을 피해 최단거리로 움직여주는 문제입니다.

다익스트라로 해주면 됩니다. 이 때, 4방향으로 가능하므로, dist변수에는

방향인자도 필요합니다. 즉, dist[x][y][dir]을 갱신해주면 됩니다.

이 때, 방향이 같으면 가중치가 0이고, 방향이 다르면 가중치는 1이 됩니다.

따라서 O(N^2logN)에 풀 수 있습니다. 

cf) 가중치가 0,1이면 0-1 BFS로 O(V+E)로도 해결할 수 있습니다.

#include<bits/stdc++.h>
using namespace std;
int n, sx, sy, ex, ey;
char m[1505][1505];
int dist[1505][1505][4];
int dx[4] = { -1,-1,1,1 };
int dy[4] = { -1,1,-1,1 };
using tp = tuple<int, int, int, int>;

bool chk(int x, int y) {
	return (x && y && x <= n && y <= n);
}

void dijk() {
	priority_queue<tp, vector<tp>, greater<tp>>pq;
	fill(&dist[0][0][0], &dist[1501][1501][3], 1e9);
	for (int k = 0; k < 4; k++) {
		int nx = sx + dx[k];
		int ny = sy + dy[k];
		if (!chk(nx, ny))continue;
		if (m[nx][ny] == '#')continue;
		dist[nx][ny][k] = 1;
		pq.push({ 1, nx, ny, k });
	}
	while (pq.size()) {
		auto [d, x, y, dir] = pq.top(); pq.pop();
		if (dist[x][y][dir] != d) continue;
		for (int k = 0; k < 4; k++) {
			int nx = x + dx[k];
			int ny = y + dy[k];
			if (!chk(nx, ny))continue;
			if (m[nx][ny] == '#')continue;
			int cost = d + (k == dir ? 0 : 1);
			if (dist[nx][ny][k] > cost) {
				dist[nx][ny][k] = cost;
				pq.push({ cost , nx, ny, k });
			}
		}
	}
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	cin >> sx >> sy;
	cin >> ex >> ey;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> m[i][j];
		}
	}
	dijk();
	int ans = 1e9;
	for (int k = 0; k < 4; k++) {
		ans = min(ans, dist[ex][ey][k]);
	}
	if (ans == 1e9) ans = -1;
	cout << ans << '\n';
}

 

 

 

F.

문자열 N개를 적당히 써서 만들 수 있는 서로 다른 길이 L의 문자열의 개수를 구해야 합니다.

포함배제 원리에 의해, 1개로 만드는 개수 - 2개로 만드는 개수 + 3개로 만드는 개수..... 를 

연산해주면 될 것 같습니다. 이제 i개로 만드는 개수를 구해보겠습니다. 우선 i개를 어떻게 골랐는지

상태를 알아야 합니다.  N이 18로 작으니 비트마스크로 모든 상태를 순회할 수 있습니다.

i개로 만든 문자열은 i개 모두에서 등장하는 문자열로 만들어진 것입니다. 따라서 i개에서

모두 겹치는 문자열 개수를 x개라고 하면, 만들 수 있는 문자열은 L^x 개가 됩니다.

이제 x를 구해봅시다. 지금 시간복잡도만 해도 O(N*2^N)입니다.

만약 문자열 i개를 하나씩 비교한다면 그것만 최대 O(26*N)입니다. 더 줄여야 합니다. 

N이 작을 때 두 문자열에서 겹치는 비교를 O(1)에 하는 트릭은 잘 알려져 있습니다. 

알파벳 순번대로 다시 비트마스크하여 저장해놓는 것입니다.

예를 들어 abd면 013이므로 2^3, 2^1, 2^0 에 마스킹해줍니다.

이렇게 문자열들을 값으로 전처리 후 AND연산을 해주면 O(1)에 처리해줄 수 있습니다.

따라서 O(1)에 x를 구할 수 있습니다. 그리고 짝수개로 만들 때마다 음수를 곱해주면 됩니다.

총 시간복잡도는 O(N*2^N)입니다. 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll mod = 998244353;
string s[18];
ll x[18], n, L;

ll mul(ll a, ll b) {
	ll ret = 1;
	while (b) {
		if (b & 1) ret = ret * a % mod;
		a = a * a % mod;
		b >>= 1;
	}
	return ret;
}

ll solve(int mask) {
	int c1 = __builtin_popcount(mask) % 2 ? 1 : -1;
	ll state = (1 << 26) - 1;
	for (int i = 0; i < n; i++) {
		if (mask & (1 << i)) {
			state &= x[i];
		}
	}
	int c2 = __builtin_popcount(state);
	return (c1 * mul(1ll * c2, 1ll * L) + mod) % mod;
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n >> L;
	for (int i = 0; i < n; i++) {
		cin >> s[i];
		for (auto t : s[i]) {
			x[i] |= 1ll << (t - 'a');
		}
	}
	ll ans = 0;
	for (int mask = 1; mask < (1 << n); mask++) {
		ans = (ans + solve(mask)) % mod;
	}
	cout << ans << '\n';
}