Atcoder Beginner Contest 280

 

https://atcoder.jp/contests/abc280

 

Denso Create Programming Contest 2022 Winter(AtCoder Beginner Contest 280) - AtCoder

 

 

A. Pawn on a Grid

 

 

요약

 

 

주어진 격자에서 '#'의 개수를 세어 반환한다.

---

#include <bits/stdc++.h>
using namespace std;
 
int H, W, cnt;
 
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> H >> W;
	for (int i = 0; i < H; i++) {
		string s;
		cin >> s;
		for (int j = 0; j < W; j++) if (s[j] == '#') cnt++;
	}
	cout << cnt;
	return 0;
}

 

 

 

B. Inverse Prefix Sum

 

 

요약

 

 

N과 수열 S가 주어질 때, 다음을 만족하는 수열 A를 구한다.
$A_{1} + A_{2} + ... + A_{k}  = S_{k}$

---

1. A[1] = S[1]로 고정된다.

 

2. A[k]는 필연적으로 S[k] - S[k-1]으로 고정됨을 알 수 있다.

#include <bits/stdc++.h>
using namespace std;
 
int N;
long long S[10];
 
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N;
	for (int i = 0; i < N; i++) cin >> S[i];
	cout << S[0] << " ";
	for (int i = 1; i < N; i++) cout << S[i] - S[i-1] << " ";	
	return 0;
}

 

 

 

C. Extra Character

 

 

요약

 

 

문자열 S와 T가 주어진다. T는 S에 하나의 알파벳 소문자를 추가하여 만든 문자열이다. 문자가 추가된 위치를 출력한다.

---

S와 T가 처음 달라지는 위치를 출력한다.

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

string S, T;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> S >> T;
	for (int i = 0; i < S.length(); i++) {
		if (S[i] != T[i]) {
			cout << i + 1;
			return 0;
		}
	}
	cout << T.length();
	return 0;
}

 

 

 

D. Factorial and Multiple

 

 

요약

 

 

정수 K가 주어졌을 때, $N!$이 K의 배수가 되도록 하는 가장 작은 N을 구한다.

---

1. $N!$이 K의 배수가 되기 위해서는 $N!$이 K의 모든 소인수를 포함하고 있어야 한다.

 

2. $\sqrt{K}$ 까지 반복문을 통해 K를 소인수분해하고, 동시에 K의 소인수의 개수를 포함하기 위한 N의 최대값을 구한다.
https://int-p.tistory.com/21

정수의 소인수분해 알고리즘

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

long long K, ans, cnt, x, temp;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> K;
	for (long long i = 2; i * i <= K; i++) {
		if (K % i == 0) {
			cnt = 0;
			while (1) {
				if (K % i != 0) break;
				K /= i;
				cnt++;
			}
			x = 0;
			while (cnt > 0) {
				x += i;
				temp = x;
				while (temp) {
					if (temp % i != 0) break;
					temp /= i;
					cnt--;
				}
			}
			ans = max(ans, x);
		}
	}
	ans = max(ans, K);
	cout << ans;
	return 0;
}

 

 

 

E. Critical Hit

 

 

요약

 

 

체력이 N인 몬스터가 있다. P%의 확률로 2의 타격을 줄 수 있고, (100-P)%의 확률로 1의 타격을 줄 수 있을 때, 몬스터의 체력을 0 이하로 깎기 위한 타격 횟수의 기댓값을 구한다.

---

1. DP의 관점으로 접근한다.

 

2. 체력을 i 깎는 경우는 체력을 i - 1 깎은 상태에서 $1 - P/100$의 확률로 체력을 1 깎는 경우와 체력을 i - 2 깎은 상태에서 $P/100$의 확률로 체력을 2 깎는 경우가 존재한다.

 

3. 체력을 i 깎기 위한 타격 횟수의 기댓값을 table[i]라고 하였을 때, 다음과 같은 점화식을 도출할 수 있다.
$table[i] = (table[i-1] + 1) \times (p/100) + (table[i - 2] + 1) \times (1 - p/100) $

 

4. table[0] = 0, table[1] = 1을 초기조건으로 세운 뒤, 페르마의 소정리를 이용하여 요구하는 값을 출력한다.

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

int N, P;
long long table[200001];

long long cal(long long A, long long B);

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> P;
	table[0] = 0; table[1] = 1;
	for (int i = 2; i <= N; i++) table[i] = (((table[i - 2] + 1) % mod * cal(P, 100)) % mod + ((table[i - 1] + 1) % mod * cal(100 - P, 100)) % mod) % mod;
	cout << table[N];
	return 0;
}

long long cal(long long A, long long B) {
	long long ret = A, bit = 1, x = B;
	while (bit <= mod - 2) {
		if (bit & (mod - 2)) ret = (ret * x) % mod;
		x = (x * x) % mod;
		bit <<= 1;
	}
	return ret;
}

 

 

 

F. Pay or Receive

 

 

요약

 

 

N개의 정점과 M개의 간선을 가지는 가중치 그래프가 주어진다. 임의의 정점 X에서 Y로 향하는 비용을 구하는 Q개의 쿼리를 처리한다.

---

1. 그래프의 특수성을 파악한다. 두 정점간에 방향이 반대이고, 가중치가 서로 덧셈 항등원인 간선이 주어진다. 즉, A에서 B로 향하는 간선의 가중치가 C일 때, B에서 A로 향하는 가중치는 -C이다.

 

2. 임의의 정점 X와 Y는 다음 세 관계중 하나로 나타낼 수 있다.
- 서로 연결되지 않은 경우

- 서로 연결되어 있고, 사이클이 존재하지 않는 경우

- 서로 연결되어 있고, 사이클이 존재하는 경우

 

3. 첫 번째 경우는 간선을 받으며 두 정점을 유니온 연산하여 유니온 파인드(Union-Find) 기법으로 판별할 수 있다.

 

4. 그래프의 특수성에 의하여 사이클이 존재하지 않는 경로에서 한 노드에서 자신으로 되돌아오는 모든 경로의 비용의 합은 0이다.
X에서 Y로 향하는 비용을 $C(X,Y)$라고 할 때, $C(X,X) = 0$이 항상 성립한다. 그 이유는,  자신으로 되돌아오는 경로는 왔던 길을 돌아가는 방법밖에 존재하지 않는데, A->B와 B->A의 가중치는 항상 0이기 때문이다.
따라서, 임의의 정점 V를 잡았을 때, $C(V,V) = C(V,X) + C(X,V) = 0 = C(V,Y) + C(Y,V)$이고, 이를 응용하여 다음과 같은 관계식을 세울 수 있다.
$C(X,Y) = C(X,V) + C(V,Y) = C(V,Y) - C(V,X)$
따라서 유니온 연산을 통해 형성된 연결 그래프의 대표값을 V로 선정하고 DFS를 통해 비용을 구하여 임의의 정점 X와 Y간의 비용을 계산할 수 있다.

 

5. DFS 과정 중 사이클의 유무를 판별할 수 있다. DFS를 돌며 dist[node]에 가중치를 저장하는데, 이미 dist[node]에 값이 있음에도 다른 값을 넣고자 한다면, node로 향하는 경로가 유일하지 않다는 것을 의미하므로, 그 연결그래프에는 사이클이 존재한다.

 

6. 사이클이 존재하는 그래프에서는 가중치를 무한대로 늘릴 수 있기 때문에 inf를 출력한다. 

#include <bits/stdc++.h>
using namespace std;
const long long INF = 0x3f3f3f3f3f3f3f3fLL;

int N, M, Q;
int parent[100001];
int cycle[100001];
long long dist[100001];
vector <pair<int, long long>> graph[100001];

int Find(int node);
void Union(int A, int B);
void DFS(int node, long long cost);

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> N >> M >> Q;
	for (int i = 1; i <= N; i++) parent[i] = i;
	for (int i = 0; i < M; i++) {
		int A, B;
		long long C;
		cin >> A >> B >> C;
		graph[A].push_back({ B,C });
		graph[B].push_back({ A,-C });
		Union(A, B);
	}
	memset(dist, INF, sizeof(dist));
	for (int i = 1; i <= N; i++) if (Find(i) == i) DFS(i, 0);	
	for (int i = 0; i < Q; i++) {
		int A, B;
		cin >> A >> B;
		if (Find(A) != Find(B)) cout << "nan\n";
		else {
			if (cycle[Find(A)] == 1) cout << "inf\n";
			else cout << dist[B] - dist[A] << '\n';
		}
	}
	return 0;
}

int Find(int node) {
	if (parent[node] == node) return parent[node];
	else return parent[node] = Find(parent[node]);
}

void Union(int A, int B) {
	A = Find(A);
	B = Find(B);
	if (A == B) return;
	if (A > B) parent[A] = B;
	else parent[B] = A;
	return;
}

void DFS(int node, long long cost) {
	if (dist[node] != INF) {
		if (dist[node] != cost) cycle[Find(node)] = 1;
		return;
	}
	dist[node] = cost;
	for (int i = 0; i < graph[node].size(); i++) DFS(graph[node][i].first, cost + graph[node][i].second);
}