zeikar / atcoder Goto Github PK

View Code? Open in Web Editor NEW

5.0 5.0 0.0 1.64 MB

Solutions of AtCoder problems and brief explanations for study.

Home Page: https://zeikar.github.io/atcoder/

C++ 100.00%

algorithms atcoder atcoder-solutions issueage study

atcoder's Introduction

Hi 👋, I'm Zeikar 😝

A software engineer who loves developing and challenging.

🌱 I’m currently learning Flutter, Svelte, Golang
📝 I regulary write articles on https://zeikar.github.io/
📄 And also practice competitive programming. Leetcode / Codeforces / Atcoder
📫 How to reach me [email protected]

Connect with me:

Languages and Tools:

Support:

atcoder's People

Contributors

Stargazers

Watchers

atcoder's Issues

KYOCERA Programming Contest 2021（AtCoder Beginner Contest 200）

https://atcoder.jp/contests/abc200

ARC_084_A / ABC_077_C - Snuke Festival

Problem link

https://atcoder.jp/contests/arc084/tasks/arc084_a

Problem Summary

n개의 배열 a, b, c가 주어진다.
a[i] < b[j] < c[k] 를 만족시키는 모든 쌍의 개수를 구하는 문제.

Solution

순서 상관 없으니 정렬부터 해보면 뭔가 보인다.
b를 기준으로 살펴보자. b의 원소 중 하나를 정했다면

b보다 작은 a 배열 원소의 개수 X b보다 큰 c 배열 원소의 개수

가 해당 b 원소를 뽑았을 때 만들 수 있는 경우의 수가 된다.

모든 n에 대해 돌리면서 b의 원소를 기준으로 a, c 배열에 대해 이분 탐색을 사용하면 된다.

Code

#include <iostream>
#include <algorithm>
using namespace std;

int a[100000];
int b[100000];
int c[100000];

int main() {
	int n;
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}

	for (int i = 0; i < n; i++)
	{
		cin >> b[i];
	}

	for (int i = 0; i < n; i++)
	{
		cin >> c[i];
	}

	sort(a, a + n);
	sort(b, b + n);
	sort(c, c + n);

	long long ans = 0;

	for (int i = 0; i < n; i++)
	{
		int aIdx = lower_bound(a, a + n, b[i]) - a - 1;
		int cIdx = upper_bound(c, c + n, b[i]) - c;

		if (aIdx < 0 || cIdx >= n)
		{
			continue;
		}

		ans += (long long)(aIdx + 1) * (n - cIdx);
	}

	cout << ans << endl;
}

Problem link

https://atcoder.jp/contests/abc219/tasks/abc219_d

Problem Summary

도시락이 있고 최소 횟수로 x개 이상의 타코야키와 y개 이상의 타이야키를 고르는 문제

Solution

딱 보니 dp 냄새가 난다. 범위도 300으로 작으니 해볼만 하다고 생각.

dp[i][j][k] = i 인덱스까지 도시락 중에 j 개의 타코야키, k 개의 타이야키를 고르는 최소 가지 수

위처럼 dp를 정의하고 다 돌려주면 된다.

단, j, k 값이 계산 중에 300 범위를 넘어갈 수 있는데, 이는 x, j 중에 최솟값으로 처리하면 된다. x 값이 넘는 j의 경우 어차피 상관 없기 때문.

Source Code

#include <iostream>
#include <cstring>
using namespace std;

int n, x, y;
int a[300], b[300];
int dp[301][301][301];

int solve(int idx, int cx, int cy) {
	if (cx >= x && cy >= y)
	{
		return 0;
	}
	if (idx >= n)
	{
		return 987654321;
	}
	if (dp[idx][min(cx, x)][min(cy, y)] != -1)
	{
		return dp[idx][min(cx, x)][min(cy, y)];
	}

	int ret = 987654321;
	// pick
	ret = min(ret, solve(idx + 1, cx + a[idx], cy + b[idx]) + 1);

	// not pick
	ret = min(ret, solve(idx + 1, cx, cy));

	return dp[idx][min(cx, x)][min(cy, y)] = ret;
}

int main() {
	memset(dp, -1, sizeof(dp));

	cin >> n >> x >> y;

	for (int i = 0; i < n; i++)
	{
		cin >> a[i] >> b[i];
	}

	int ans = solve(0, 0, 0);

	if (ans == 987654321)
	{
		ans = -1;
	}
	cout << ans << endl;
}

CODEFESTIVAL_2016_QUALA_C - Next Letter

Problem link

https://atcoder.jp/contests/code-festival-2016-quala/tasks/codefestival_2016_qualA_c

Problem Summary

문자열과 k가 주어진다. k번 연산을 통해 만들 수 있는 사전 순으로 가장 작은 수를 구하는 문제.
연산: 다음 문자로 변경, 단 z는 a로 변함.

Solution

일단 그리디 적으로 생각해보면

사전 순으로 최소가 되려면 앞 문자를 최대한 a로 만들어야 한다.
a로 만들 수 없으면 아예 연산을 안 하는 것이 낫다.

위 두 규칙에 맞게 문자열을 돌면서 계산해주면 된다. 단, 연산 횟수가 남았을 경우 맨 마지막 문자를 수정하면 사전 순으로 최소가 되게 할 수 있다.

Source Code

#include <iostream>
#include <string>
using namespace std;

int main() {
	string s;
	int k;
	cin >> s >> k;

	for (int i = 0; i < s.size(); i++)
	{
		if (s[i] == 'a')
		{
			continue;
		}

		int diff = 26 - (s[i] - 'a');
		// possible to change to a
		if (k >= diff)
		{
			s[i] = 'a';
			k -= diff;
		}
	}

	// remains
	s[s.size() - 1] = ((s[s.size() - 1] - 'a') + k % 26) % 26 + 'a';

	cout << s << endl;
}

ACL Beginner Contest

https://atcoder.jp/contests/abl
2020-09-26 21:00

ABC_228 - TOYOTA SYSTEMS Programming Contest 2021(AtCoder Beginner Contest 228)

Contest Link

https://atcoder.jp/contests/abc228

Solved problems

A, B, C, D

Brief explanations

A, B 간단. 단, A는 처음에 이해가 안되서 1번 틀림...
C: 정렬을 한 후 자신보다 300점 높은 개수를 세고 K보다 작거나 같으면 Yes 출력. 개수를 셀 때 upper bound 이용.
D: 들어갈 수 있는 자리를 map으로 예약해두고 값이 업데이트 될 때마다 제거, 자리를 찾는 건 lower bound 이용. 단, n을 넘으면 다시 0부터 채워야 하므로 2 * n 만큼을 자리 예약을 해둠.

DIVERTA2019_D - DivRem Number

Problem link

https://atcoder.jp/contests/diverta2019/tasks/diverta2019_d

Problem Summary

주어진 N에 대해 나눈 몫과 나머지가 같도록 하는 m을 모두 구해 더하면 된다.

Solution

수식을 조금 이용하면 된다.
먼저 구하고자 하는 favorite number를 m으로 두면

x = N / m = N % m

이 성립해야 되고, 양쪽으로 식을 정리하면

N = m * x + x
m = (N - x) / x

이 된다.

단, 1부터 모든 n까지 탐색은 시간 초과가 되므로 sqrt(n) 까지만 돌려주면 된다.

Source Code

#include <iostream>
using namespace std;

int main() {
	long long n;
	cin >> n;

	long long ans = 0;

	for (long long x = 1; x * x <= n; x++)
	{
		long long m = (n - x) / x;

		if (m == 0)
		{
			continue;
		}

		if (n / m == n % m)
		{
			ans += m;
		}
	}

	cout << ans << endl;
}

ABC_140_D - Face Produces Unhappiness

Problem link

https://atcoder.jp/contests/abc140/tasks/abc140_d

Problem Summary

사람들이 L, R 방향을 바라보며 서 있고, 서로 같은 방향을 바라보면 happy이다.
이때 k 번의 횟수만큼 (l, r) 범위의 사람들의 방향을 뒤집을 수 있다.
최대로 happy 하게 만들 수 있는 사람의 수를 구하는 문제.

Solution

딱 보면 어려운데 포인트를 잘 알아채면 굉장히 쉬워지는 문제.

unhappy한 사람들을 뒤집게 되면 happy 하게 변하는 사람의 수는 2명이다.

위 사실을 알면 쉽게 풀린다.

먼저 간단한 증명은 LLL ... RRR ... LLL 이 있을 때 R 을 뒤집어서 L로 만든다고 해보자. 그렇게 되면 RRR...R 의 내부의 happy는 그대로 이고 LR ... RL 처럼 서로 경계에 있는 unhappy인 사람은 LL....LL로 뒤집어 지면서 총 2명의 happy 가 추가된다.
또한, 배열의 양쪽 끝부분을 뒤집으면 1명만 증가하지만 그리디 하게 2명 증가하는 부분만 뒤집는다고 생각하면 된다.

최대로 happy할 수 있는 사람의 수는 n-1 이므로 이를 넘지 않도록 출력해주면 된다.

Source Code

#include <iostream>
#include <string>
using namespace std;

int main() {
	int n, k;
	string s;

	cin >> n >> k >> s;

	int happy = 0;
	for (int i = 1; i < n; i++)
	{
		if (s[i] == s[i - 1])
		{
			happy++;
		}
	}

	cout << min(n - 1, happy + 2 * k) << endl;
}

ABC_223_D - Restricted Permutation

Problem link

https://atcoder.jp/contests/abc223/tasks/abc223_d

Problem Summary

1부터 N까지 순열 중에 Ai의 위치 < Bi의 위치를 만족시키는 사전 순으로 가장 작은 순열을 구하는 문제.

Solution

잘 보니 위상 정렬 문제이다.

사전 순으로 출력해야 하므로 우선순위 큐로 처리해주고 정답 사이즈가 n이 아니면 사이클이 존재하는 것이므로 -1을 출력하면 된다.

Source Code

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector<int> edges[200001];
int indegree[200001];

int main() {
	int n, m;

	cin >> n >> m;

	while (m--)
	{
		int a, b;
		cin >> a >> b;

		edges[a].push_back(b);
		++indegree[b];
	}

	priority_queue<int> que;
	queue<int> ans;
	for (int i = 1; i <= n; i++)
	{
		if (indegree[i] == 0)
		{
			que.push(-i);
		}
	}

	while (!que.empty())
	{
		int node = -que.top();
		que.pop();
		ans.push(node);

		for (int i = 0; i < edges[node].size(); i++)
		{
			int next = edges[node][i];

			indegree[next]--;

			if (indegree[next] == 0)
			{
				que.push(-next);
			}
		}
	}

	if (ans.size() != n)
	{
		cout << -1 << endl;
	}
	else
	{
		while (!ans.empty())
		{
			cout << ans.front() << ' ';
			ans.pop();
		}
		cout << endl;
	}
}

Study

대회가 아닌 스터디 용으로 푼 문제들 모음.

=> https://github.com/cp-study

ABC_216_E - Amusement Park

Problem link

https://atcoder.jp/contests/abc216/tasks/abc216_e

Problem Summary

n개의 a 배열이 주어지고 최대 k개를 골라서 최대가 되도록 고르는 문제.
단, 한번 고를 때마다 a 배열의 원소의 값은 1씩 감소한다.

Solution

뭔가 이분 탐색으로 가능할 것 같은데 생각보다 쉽지 않았다.

먼저 k개를 넘지 않는 최대 개수를 고르는 지점을 이분 탐색을 이용해서 구할 수 있다.
k 개에서 남은 개수만큼 더 고를 수 있는데 이건 따로 한 번 더 탐색해서 구하면 된다.

예제1로 보면 이분 탐색으로 k개를 넘지 않게 고를 수 있는 값인 100을 구함 (4개 선택 가능)
k 가 5이므로 1개를 더 추가로 고를 수 있는데 이건 아래쪽 for 문으로 cnt를 구해 k 에서 뺀 만큼 99 를 곱해서 더하도록 했다.

Source Code

#include <iostream>
using namespace std;

long long a[100000];

int main() {
	long long n, k;
	cin >> n >> k;

	long long high = 0;
	long long low = 0;
	long long ans = 0;

	for (int i = 0; i < n; i++)
	{
		cin >> a[i];

		high = max(high, a[i]);
	}

	while (low <= high)
	{
		long long mid = (high + low) / 2;
		long long cnt = 0;

		for (int i = 0; i < n; i++)
		{
			if (a[i] < mid)
			{
				continue;
			}

			long long n = a[i] - mid + 1;
			cnt += n;
		}

		if (cnt > k)
		{
			low = mid + 1;
		}
		else
		{
			high = mid - 1;
		}
	}

	long long cnt = 0;
	for (int i = 0; i < n; i++)
	{
		if (a[i] < low)
		{
			continue;
		}

		long long n = a[i] - low + 1;
		cnt += n;
		ans += n * (a[i] + low) / 2;
	}
	ans += max((k - cnt) * (low - 1), 0LL);

	cout << ans << endl;
}

ARC_061_A / ABC_045_C - Many Formulas

Problem link

https://atcoder.jp/contests/arc061/tasks/arc061_a

Problem Summary

문자열 s의 문자 사이에 + 를 넣어 만들 수 있는 수를 전부 더하는 문제.

Solution

그냥 말 그대로 +를 문자 사이에 다 한 번 씩 넣어서 만들 수 있는 수를 더하면 된다.
비트 연산으로 간단하게 가능.

Source Code

#include <iostream>
#include <string>
using namespace std;

int main() {
	string s;
	cin >> s;

	long long ans = 0;

	for (int i = 0; i < (1 << (s.length() - 1)); i++)
	{
		long long num = 0;

		for (int j = 0; j < s.length(); j++)
		{
			num *= 10;
			num += s[j] - '0';

			if ((1 << j) & i)
			{
				ans += num;
				num = 0;
			}
		}

		ans += num;
	}

	cout << ans << endl;
}

ABC_192_E - Train

Problem link

https://atcoder.jp/contests/abc192/tasks/abc192_e

Problem Summary

도시들이 있고 철도의 정보 (소요 시간, 출발하는 시각)이 주어질 때 x 에서 y로 가는 최소 시간을 구하는 문제.

Solution

전형적인 다익스트라 문제이다.
단, 기차가 ki 의 배수로만 출발하므로 이를 보정하기 위해 ki 배수 미만이면 ki 배수로 만들고 ti를 더하도록 하였다.

Source Code

#include <iostream>
#include <vector>
#include <queue>
#include <tuple>
#include <climits>
using namespace std;

class Edge
{
public:
	Edge(int dest, int t, int k) {
		this->dest = dest;
		this->t = t;
		this->k = k;
	}

	int dest;
	int t;
	int k;
};

vector<Edge> edges[100001];
long long distances[100001];

int main() {
	int n, m, x, y;
	cin >> n >> m >> x >> y;

	for (int i = 0; i <= n; i++)
	{
		distances[i] = LLONG_MAX;
	}

	while (m--)
	{
		int a, b, t, k;
		cin >> a >> b >> t >> k;

		edges[a].push_back(Edge(b, t, k));
		edges[b].push_back(Edge(a, t, k));
	}

	priority_queue<tuple<long long, int> > pq;
	pq.push(make_tuple(0, x));
	distances[x] = 0;

	while (!pq.empty())
	{
		auto current = pq.top();
		pq.pop();

		long long currentTime = -get<0>(current);
		int currentCity = get<1>(current);

		if (distances[currentCity] < currentTime)
		{
			continue;
		}

		for (int i = 0; i < edges[currentCity].size(); i++)
		{
			auto nextEdge = edges[currentCity][i];
			long long nextTime;

			if (currentTime % nextEdge.k == 0)
			{
				nextTime = currentTime + nextEdge.t;
			}
			else
			{
				nextTime = ((currentTime / nextEdge.k) + 1) * nextEdge.k + nextEdge.t;
			}

			if (distances[nextEdge.dest] <= nextTime)
			{
				continue;
			}
			distances[nextEdge.dest] = nextTime;

			pq.push(make_tuple(-nextTime, nextEdge.dest));
		}
	}

	if (distances[y] == LLONG_MAX)
	{
		cout << -1 << endl;
	}
	else
	{
		cout << distances[y] << endl;
	}
}

ABC_115_D - Christmas

Problem link

https://atcoder.jp/contests/abc115/tasks/abc115_d

Problem Summary

버거를 일정 규칙으로 쌓을 수 있다.
해당 레벨의 버거의 x층 까지 중에 패티가 몇 개인지 구하는 문제.

일정 규칙:

레벨 0의 버거는 패티 1개이다.
레벨 L의 버거는 번 + 레벨 L-1 버거 + 패티 + 레벨 L-1 버거 + 번이다.

Solution

분할 정복으로 레벨 L의 버거의 패티 수를 빨리 구할 수 있다.

번 + 레벨 L-1 버거 + 패티 + 레벨 L-1 버거 + 번

중간의 패티를 기점으로 반을 나눌 수 있고,
x가 레벨 L-1 버거의 층수 + 1 보다 작으면 레벨 L-1 버거의 패티의 개수를 구하는 식으로 재귀적으로 나눠나갈 수 있다.

대신 특정 레벨의 전체 버거 층 수 및 패티의 총 개수를 빨리 구하기 위해 먼저 전처리로 전부 구해놓았다.

Source Code

#include <iostream>
using namespace std;

long long totalLength[51];
long long pattyLength[51];

void getLength(int level) {
	if (level == 0)
	{
		totalLength[level] = 1;
		pattyLength[level] = 1;
		return;
	}

	getLength(level - 1);

	totalLength[level] = totalLength[level - 1] * 2 + 3;
	pattyLength[level] = pattyLength[level - 1] * 2 + 1;
}

long long solve(int level, long long x) {
	if (level == 0)
	{
		return 1;
	}

	if (x <= 1)
	{
		return 0;
	}
	else if (x <= 1 + totalLength[level - 1])
	{
		return solve(level - 1, x - 1);
	}
	else if (x == 1 + totalLength[level - 1] + 1)
	{
		return pattyLength[level - 1] + 1;
	}
	else if (x < totalLength[level])
	{
		return pattyLength[level - 1] + 1 + solve(level - 1, x - totalLength[level - 1] - 2);
	}
	else
	{
		return pattyLength[level];
	}
}

int main() {
	int n;
	long long x;

	cin >> n >> x;

	getLength(n);

	cout << solve(n, x) << endl;
}

대회들...

미리미리 올립시다 ㅋㅋㅋ

ABC_226 - AtCoder Beginner Contest 226

Contest Link

https://atcoder.jp/contests/abc226

Solved problems

A, B, C, D

Brief explanations

A, B: 간단
C: 그냥 dfs 탐색해주면 된다.
D: x, y 모든 쌍에 대해 좌표의 차이 (기울기)를 gcd로 나눠서 중복을 제거하면서 저장하면 된다.

ABC_191_C - Digital Graffiti

Problem link

https://atcoder.jp/contests/abc191/tasks/abc191_c

Problem Summary

그리드에 #, .으로 이루어진 문자열이 주어질 때 이 도형이 몇각형인지 구하는 문제.

Solution

문제 설명, 예제가 불친절한데... 오목 다각형도 존재할 수 있다.

어쨌든 다각형이 몇각형인지 구하려면 꼭지점의 개수를 구해야 한다.
이건 에디토리얼을 참고했는데 상하좌우 2칸씩 개수를 세서 검은색 블록 (#)이 1개 또는 3개이면 꼭지점이다.

예시를 보면 좀 이해가 가긴 하는데

.....
.###.
.###.
.###.
.....

이건 4각형이고

.....
.#.#.
.###.
.###.
.....

이건 8각형이 된다

Source Code

#include <iostream>
#include <string>
using namespace std;

int main() {
	int h, w;
	cin >> h >> w;

	string grid[10];

	for (int i = 0; i < h; i++)
	{
		cin >> grid[i];
	}

	int ans = 0;

	for (int i = 0; i < h - 1; i++)
	{
		for (int j = 0; j < w - 1; j++)
		{
			int cnt = 0;

			for (int a = 0; a < 2; a++)
			{
				for (int b = 0; b < 2; b++)
				{
					cnt += (grid[i + a][j + b] == '#');
				}
			}

			if (cnt == 1 || cnt == 3)
			{
				ans++;
			}
		}
	}

	cout << ans << endl;
}

ARC_097_A / ABC_097_C - K-th Substring

Problem link

https://atcoder.jp/contests/arc097/tasks/arc097_a

Problem Summary

문자열 s 의 모든 부분 문자열 중에서 k 번째로 작은 문자열을 구하는 문제.

Solution

일단 힌트는 k가 아주 작다는 것이다. (최대 5)

s 의 길이가 최대 5000이므로 s의 모든 부분 문자열을 구하는 것은 n^2이 되고 이론상 시간 안에 들어올 수 있다.
중복을 제거하기 위해 맵을 사용하고, 구한 모든 부분 문자열을 맵에 넣으면 쉽게 풀 수 있다.

처음 제출한 답은 그냥 단순히 모든 부분 문자열 중 k 번째를 구했는데 당연히 시간초과. 약간의 최적화를 해서 맵의 크기를 최대 k개 까지만 유지했더니 1초정도로 통과.

여기서 더 최적화를 할 수 있는데 k 번째의 부분 문자열의 길이는 최대 k여야만 한다는 것을 이용하면 된다.
길이가 k가 넘으면 그보다 작은 부분 문자열(prefix)보다 크게 되기 때문이다. (aaaaaa > aaaaa) 이다.

Source Code

#include <iostream>
#include <string>
#include <algorithm>
#include <map>
using namespace std;

int main() {
	string s;
	int k;

	cin >> s >> k;

	map<string, bool> substrs;
	for (int i = 0; i < s.length(); i++)
	{
		for (int j = i + 1; j <= min(i + k, (int)s.length()); j++)
		{
			substrs[s.substr(i, j - i)] = true;

			if (substrs.size() > k)
			{
				substrs.erase(--substrs.end());
			}
		}
	}

	for (auto const& str : substrs)
	{
		k--;

		if (k == 0)
		{
			cout << str.first << endl;
			break;
		}
	}
}

AtCoder Beginner Contest 180

https://atcoder.jp/contests/abc180

ABC_099_C - Strange Bank

Problem link

https://atcoder.jp/contests/abc099/tasks/abc099_c

Problem Summary

한 번에 인출할 수 있는 액수가 정해져 있고, 주어진 돈을 최소 몇 번만에 인출할 수 있는지 구하는 문제.

Solution

전형적인 DP 문제.
간단하게

dp[n] = n을 인출할 수 있는 최소 횟수.

로 정의하고 돌려주면 된다.

에디토리얼 보니 그리디로도 풀 수 있다.

Source Code

#include <iostream>
#include <cstring>
using namespace std;

int dp[100001];

int main() {
	int N;
	cin >> N;

	for (int i = 1; i <= N; i++)
	{
		dp[i] = 987654321;

		for (int j = 6; j <= i; j *= 6)
		{
			dp[i] = min(dp[i], dp[i - j] + 1);
		}
		for (int j = 9; j <= i; j *= 9)
		{
			dp[i] = min(dp[i], dp[i - j] + 1);
		}

		dp[i] = min(dp[i], dp[i - 1] + 1);
	}

	cout << dp[N] << endl;
}

ZONe Energy Programming Contest

https://atcoder.jp/contests/zone2021

ABC_166_E - This Message Will Self-Destruct in 5s

Problem link

https://atcoder.jp/contests/abc166/tasks/abc166_e

Problem Summary

배열에서 두 원소를 선택할 때 값의 합이 인덱스의 차이의 절댓값이 되는 경우의 수를 구하는 문제.

Solution

뭔가 수학적인 것이 보일 듯 해서 정리를 해봤다.

Ai + Aj == | j - i |

j > i로 고정하고 절댓값을 풀면 j - Aj = i + Ai 가 되는데 i + Ai가 몇개인지 계속 더해주면서 j에 대해 j - Aj 개수를 더해주면 된다.

참고: https://codeforces.com/blog/entry/76833?#comment-614685

Source Code

#include <iostream>
#include <map>
using namespace std;

int a[200000];
map<int, int> diff;

int main() {
	int n;
	cin >> n;

	long long res = 0;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];

		res += diff[i - a[i]];
		diff[a[i] + i]++;
	}


	cout << res << endl;
}

ABC_222 - Exawizards Programming Contest 2021（AtCoder Beginner Contest 222）

Contest Link

https://atcoder.jp/contests/abc222

Solved problems

A, B, C, D

Brief explanation

A, B, C: 쉬움
D: DP + prefix sum.
일반적인 DP로 하면 시간 초과가 되므로 prefix sum도 섞어서 계산해주면 된다.

ABC_231 - Panasonic Programming Contest 2021(AtCoder Beginner Contest 231)

Contest Link

https://atcoder.jp/contests/abc231

Solved problems

A, B, C, D

Brief explanations

A, B, C: 간단
D: 결론만 말하면 연결된 곳이 3개 이상이거나 사이클이 있을 경우 No가 출력되어야 한다.
불친절한 예제로 직접 예외 케이스를 찾아야 한다.
엄청난 삽질.. 끝에 dsu로 풀긴 풀었다.

ARC_110_C - Exoswap

Problem link

https://atcoder.jp/contests/arc110/tasks/arc110_c

Problem Summary

배열이 주어지고, 임의의 순열 P의 순서대로 swap을 했을 때 오름차순이 되는지 확인하는 문제.

Solution

그리디하게 접근해보자.
가장 큰 수는 가장 오른쪽으로 이동해야 되므로 가장 큰 수부터 탐색을 진행한다.
오른쪽으로 swap이 가능하면 swap을 해주고 자기 위치까지 계속 swap을 한다. 일종의 버블 정렬 느낌.

이때 P가 순열이므로 visited를 넣어 한번 나온 수는 더 나오지 않게 처리한다.

Source Code

#include <iostream>
#include <algorithm>
#include <utility>
#include <vector>
using namespace std;

int a[200001];
pair<int, int> map[200001];
bool visited[200001];

int main() {
	int n;
	cin >> n;


	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
		map[i].first = a[i];
		map[i].second = i;
	}

	sort(map, map + n);

	vector<int> ans;

	for (int i = n - 1; i > 0; i--)
	{
		int val = map[i].first;
		int pos = map[i].second;

		// move
		if (pos < val - 1 && !visited[pos])
		{
			// swap
			int target = a[pos + 1];

			map[i].second = map[i - (val - target)].second;
			map[i - (val - target)].second = pos;

			a[pos] = target;
			a[pos + 1] = val;

			ans.push_back(pos);
			visited[pos] = true;
			i++;
		}
		else if (pos == val - 1)
		{
			continue;
		}
		else
		{
			ans.clear();
			break;
		}
	}

	if (ans.size() != n - 1)
	{
		cout << -1 << endl;
	}
	else
	{
		for (int i = 0; i < ans.size(); i++)
		{
			cout << ans[i] + 1 << endl;
		}
	}
}

AtCoder Regular Contest 106

https://atcoder.jp/contests/arc106

AGC_034_B - ABC

Problem link

https://atcoder.jp/contests/agc034/tasks/agc034_b

Problem Summary

주어진 문자열에서 ABC를 BCA로 최대 몇 번 바꿀 수 있는지 출력하는 문제.

Solution

생각보다 쉽지 않은데 몇 가지 특징을 써보자.

A, BC는 덩어리로 움직이고 나머지 문자열은 무시할 수 있다.
=> 나머지 문자열이 나오면 더 이상 변환이 불가능하다.
A, BC들이 적절히 만났을 때 모든 변환이 끝나면 A는 맨 뒤로 이동한다. (AABCBCBC => BCBCBCAA)
=> BC가 나오면 그 전의 A 개수만큼 변환 가능하다.

A 개수를 누적으로 카운트 해주면서 BC를 만나면 A 개수를 정답에 계속 더해나가면 된다.

Source Code

#include <iostream>
#include <string>
using namespace std;

int main() {
	string s;
	cin >> s;

	// dummy
	s += "F";

	long long ans = 0;
	long long aCount = 0;

	for (int i = 0; i < s.length(); i++)
	{
		if (s[i] == 'A')
		{
			aCount++;
		}
		else if (s.substr(i, 2) == "BC")
		{
			ans += aCount;
			i++;
		}
		else
		{
			aCount = 0;
		}
	}

	cout << ans << endl;
}

AISing Programming Contest 2021（AtCoder Beginner Contest 202）

https://atcoder.jp/contests/abc202

ARC_100_A / ABC_102_C - Linear Approximation

Problem link

https://atcoder.jp/contests/arc100/tasks/arc100_a

Problem Summary

N 개의 a 배열에서 적당한 b 값을 구해서 아래 식을 최소로 만드는 b 값을 찾는 문제.

Solution

먼저 자기 인덱스 + 1만큼 빼고 시작하자.
그러면 | a[i] - b | 의 최솟값을 찾는 문제가 되는데..
이건 중앙값을 쓰면 된다.

자세한 증명은 https://drken1215.hatenablog.com/entry/2019/06/15/114700 참고.

a[i]를 정렬한 다음 중앙값으로 b를 설정하고 정답을 구하면 된다.
위 중앙값을 골라야 한다는 사실을 모르면 쉽지 않은 문제.

Source Code

#include <iostream>
#include <algorithm>
using namespace std;

int a[200000];

int main() {
	int n;
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> a[i];

		a[i] -= (i + 1);
	}

	sort(a, a + n);

	int median = a[(n - 1) / 2];

	long long ans = 0;
	for (int i = 0; i < n; i++)
	{
		ans += abs(a[i] - median);
	}

	cout << ans << endl;
}

AtCoder Beginner Contest 199

https://atcoder.jp/contests/abc199

AtCoder Beginner Contest 205

https://atcoder.jp/contests/abc205

TENKA1_2018_C - Align

Problem link

https://atcoder.jp/contests/tenka1-2018-beginner/tasks/tenka1_2018_c

Problem Summary

적당히 N개의 배열을 정렬해서 양 옆 원소의 차이의 절대값의 합의 최댓값을 구하는 문제.

Solution

먼저 어떻게 하면 최대가 될지 대충 생각해보면 큰 값, 작은 값이 번갈아가면서 나와야 한다.

아래부턴 에디토리얼을 참고함.

예시로 홀수 번째 인덱스가 큰 값들, 짝수 번째 인덱스가 작은 값들이라고 놓으면, 절대값을 한 결과는 (큰 값 - 작은 값)이 된다.

n = 5일 때,

(p1 − p2) + (p3 − p2) + (p3 − p4) + (p5 − p4) = (+1) ∗ p1 + (−2) ∗ p2 + (+2) ∗ p3 + (−2) ∗ p4 + (+1) ∗ p5.

이런 식이 되고, 계수가 큰 순서대로 큰 수를 넣어주면 최댓값을 얻을 수 있다.

반대로 짝수 번째 인덱스가 큰 값일 때는

(p2 − p1) + (p2 − p3) + (p4 − p3) + (p4 − p5) = (-1) ∗ p1 + (+2) ∗ p2 + (-2) ∗ p3 + (+2) ∗ p4 + (-1) ∗ p5.

이것도 마찬가지로 큰 계수부터 큰 수를 넣어주면 된다.
정답은 위 두 가지 중 큰 값을 출력하면 된다.

위 예시는 n이 홀수일 경우고 짝수인 경우는 한번만 해주면 된다.

Source Code

#include <iostream>
#include <algorithm>
using namespace std;

long long a[100000];

int main() {
	int n;
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}

	sort(a, a + n);

	long long ans = 0;

	if (n % 2 == 0)
	{
		for (int i = 0; i < n / 2; i++)
		{
			ans -= 2 * a[i];
		}
		for (int i = n / 2; i < n; i++)
		{
			ans += 2 * a[i];
		}
		ans -= a[n / 2];
		ans += a[n / 2 - 1];
	}
	else
	{
		long long oddBig = 0, evenBig = 0;

		for (int i = 0; i < n / 2; i++)
		{
			oddBig -= 2 * a[i];
		}
		for (int i = n / 2; i < n; i++)
		{
			oddBig += 2 * a[i];
		}
		oddBig -= a[n / 2];
		oddBig -= a[n / 2 + 1];


		for (int i = 0; i <= n / 2; i++)
		{
			evenBig -= 2 * a[i];
		}
		for (int i = n / 2 + 1; i < n; i++)
		{
			evenBig += 2 * a[i];
		}
		evenBig += a[n / 2];
		evenBig += a[n / 2 - 1];

		ans = max(oddBig, evenBig);
	}


	cout << ans << endl;
}

ABC_230_D - Destroyer Takahashi

Problem link

https://atcoder.jp/contests/abc230/tasks/abc230_d

Problem Summary

모든 벽을 부수기 위해 최소 몇 번 펀치를 해야 하는지 구하는 문제.

Solution

모든 벽을 부숴야 하므로 정렬 후 왼쪽부터 쭉 나가면 될 것 같다.
근데 이게 생각보다 안돼서... 대회 중에 결국 못 풀었다

에디토리얼을 참고해서 재작성.

일단 정렬은 맞는데 오른쪽 좌표를 기준으로 정렬해야 한다. 해당 벽을 제거할 때 최대한 오른쪽을 제거해야 다른 벽도 같이 제거할 수 있기 때문이다.
제거하는 벽은 왼쪽 좌표가 제거할 좌표 + d - 1 이내이면 가능하다.
이 좌표를 넘어가면 한번에 부술 수 없으므로 다시 오른쪽 좌표에서 펀치를 날려야 한다.

Source Code

#include <iostream>
#include <algorithm>
#include <utility>
#include <queue>
#include <vector>
using namespace std;

int main() {
	int n, d;
	cin >> n >> d;

	vector< pair<int, int> > walls;

	for (int i = 1; i <= n; i++)
	{
		int l, r;
		cin >> l >> r;

		walls.push_back(make_pair(r, l));
	}

	sort(walls.begin(), walls.end());

	int ans = 0, x = -1987654321;
	for (int i = 0; i < walls.size(); i++)
	{
		int l = walls[i].second;
		int r = walls[i].first;

		if (l > x + d - 1)
		{
			ans++;

			x = r;
		}
	}

	cout << ans << endl;
}

ABC_129_D - Lamp

Problem link

https://atcoder.jp/contests/abc129/tasks/abc129_d

Problem Summary

H * W 크기의 그리드가 있고 빈 칸에 램프를 놓을 수 있다.
램프는 장애물을 넘을 수 없고, 상하좌우를 밝힐 수 있다.
램프가 밝힐 수 있는 칸의 최대 수를 구하는 문제.

Solution

아주 간단하게 완전 탐색하면 시간 초과다. (모든 점에 램프를 넣어보고 칸 수를 계산)
빛이 비출 수 있는 칸 수를 계산할 때 시간을 줄일 수 있는데, 칸 별로 연속한 칸 수를 저장해두면 된다.
상하로 연속한 칸의 개수, 좌우로 연속한 칸의 개수를 미리 계산해서 넣어둔 후 마지막엔 두 합이 최대가 되는 것이 정답이다.

Source Code

#include <iostream>
#include <string>
using namespace std;

string grid[2000];
int consecutiveX[2000][2000];
int consecutiveY[2000][2000];

int main() {
	int H, W;

	cin >> H >> W;

	for (int i = 0; i < H; i++)
	{
		cin >> grid[i];
	}

	int ans = 0;
	int cnt = 0;

	for (int i = 0; i < H; i++)
	{
		int startX = i, startY = 0;

		for (int j = 0; j < W; j++)
		{
			if (grid[i][j] == '.')
			{
				++cnt;
			}
			else
			{
				for (int k = startY; k < j; k++)
				{
					consecutiveX[startX][k] = cnt;
				}

				startY = j + 1;
				cnt = 0;
			}
		}

		for (int k = startY; k < W; k++)
		{
			consecutiveX[startX][k] = cnt;
		}

		cnt = 0;
	}

	for (int j = 0; j < W; j++)
	{
		int startX = 0, startY = j;

		for (int i = 0; i < H; i++)
		{
			if (grid[i][j] == '.')
			{
				++cnt;
			}
			else
			{
				for (int k = startX; k < i; k++)
				{
					consecutiveY[k][startY] = cnt;
				}

				startX = i + 1;
				cnt = 0;
			}
		}

		for (int k = startX; k < H; k++)
		{
			consecutiveY[k][startY] = cnt;
		}

		cnt = 0;
	}

	for (int i = 0; i < H; i++)
	{
		for (int j = 0; j < W; j++)
		{
			ans = max(ans, consecutiveX[i][j] + consecutiveY[i][j] - 1);
		}
	}

	cout << ans << endl;
}

ABC_194_D - Journey

Problem link

https://atcoder.jp/contests/abc194/tasks/abc194_d

Problem Summary

n개의 정점으로 이루어진 그래프가 있다.
현재는 그래프의 1번에 있는데 1/n 확률로 다른 정점을 선택할 수 있다. 이때 모든 정점을 선택하게 되는 시도 횟수의 기댓값을 구하는 문제.

Solution

https://blog.hamayanhamayan.com/entry/2021/03/07/000733
위 블로그를 참고함.

일단, 성공 확률을 p 라고 할 때, 성공할 때까지 수행 할 때의 시도 횟수는 확률의 역수(1/p)가 된다. 라는 사실을 알아야 풀 수 있는 문제.

증명은 에디토리얼을 참고하면 되고 직관적으로 보자면 확률 1/3 짜리가 있다고 할 때 성공의 기댓값은 역수인 3회가 된다.

이를 이용해보자면 처음은 1개를 골랐으므로 나머지는 n-1개이다. n개 전부를 고르려면 나머지 중에 하나를 골라야 되고 고르는 확률은 n-1 / n 이다. 이에 따른 기댓값은 역수인 n / n-1 이다.
이제 또 다른 나머지에서 골라야 하므로 기댓값은 n / n-2 이 되고 이를 계속해서 더해나가면 된다.

Source Code

#include <iostream>
#include <iomanip>
using namespace std;

int main() {
	int n;
	cin >> n;

	long double ans = 0;
	for (int i = 1; i < n; i++)
	{
		ans += (long double)n / (n - i);
	}

	cout << fixed << setprecision(12) << ans << endl;
}

ABC_194_E - Mex Min

Problem link

https://atcoder.jp/contests/abc194/tasks/abc194_e

Problem Summary

0≤i≤N−M 범위에서 mex의 최솟값을 구하는 문제.

Mex(x1...xk): x1...xk 에 속하지 않는 가장 작은 0이상의 정수.

Solution

아주 간단하게 생각해보면 쉽게 풀린다.

Ai의 최대 범위가 N이므로 0부터 N까지의 수를 맵에 넣어 두고 범위 안에서 Ai의 값이 나오면 맵에서 제거, Ai값이 없어지면 맵에 추가하는 방식으로 할 수 있다.

즉, 속하지 않는 가장 작은 0이상의 정수 (Mex)를 맵 형태로 계속 유지하는 것.

Source Code

#include <iostream>
#include <map>
using namespace std;

int a[1500000];
int cnt[1500001];

int main() {
	int n, m;
	cin >> n >> m;

	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}

	map<int, bool> notOccurred;
	for (int i = 0; i <= n; i++)
	{
		notOccurred[i] = true;
	}

	for (int i = 0; i < m; i++)
	{
		if (cnt[a[i]] == 0)
		{
			notOccurred.erase(a[i]);
		}

		cnt[a[i]]++;
	}

	int ans = notOccurred.begin()->first;
	for (int i = m; i < n; i++)
	{
		if (cnt[a[i]] == 0)
		{
			notOccurred.erase(a[i]);
		}

		cnt[a[i]]++;	
		cnt[a[i - m]]--;

		if (cnt[a[i - m]] == 0)
		{
			notOccurred[a[i - m]] = true;
		}

		ans = min(ans, notOccurred.begin()->first);
	}

	cout << ans << endl;
}

CADDI_2018_B / CADDI_2018B_D - Harlequin

Problem link

https://atcoder.jp/contests/caddi2018/tasks/caddi2018_b

Problem Summary

플레이어와 Lunlun이 번갈아 가며 게임을 한다.
한 턴에 다른 색의 사과만을 먹을 수 있다.
마지막 사과를 먹은 사람이 승자일 때 승자를 구하는 문제.

Solution

이런 게임류 문제가 생각보다 까다롭다.

일단, 예제 1번에서 얻을 수 있는 정보는 사과가 한 종류만 남았을 경우 짝수개이면 무조건 진다는 것이다. (하나씩밖에 못 가져가므로)
사과가 두 종류일 때를 시뮬레이션 해보자.
2, 2인 경우 첫 번째 플레이어가 한 종류만 먹는다고 하면 1,2 이고 두 번째 플레이어가 1개 남은 사과를 먹게 되면 두 번째가 승리한다.
만약 첫 번째 플레이어가 두 종류 다 먹는다면 1,1이 되고 이렇게 해도 두 번째 플레이어가 둘 다 먹게 되어 두 번째가 승리한다.

짝수개로 일반화도 가능한데, 2n, 2n개인 경우 첫 번째 플레이어가 둘 다 먹든 하나만 먹든 다른 플레이어가 남은 사과의 수를 짝수로 만들어 버릴 수 있으므로 이길 수 없다.

에디토리얼을 참고하면 모든 사과가 짝수인 상태를 E, 하나라도 홀수가 있다면 O 로 정의한다. 마지막 승리 상태도 E로 볼 수 있다.
처음 시작이 E인 상태일 때 첫 번째 플레이어가 뭘 하든 O 상태로 변화되고 두 번째 플레이어는 다시 E로 전환시킬 수 있다.
처음 시작이 O인 상태일 때는 첫 번째 플레이어가 E로 변환시킬 수 있다.

즉, 처음 시작이 E인 경우 두 번째 플레이어가 이기고 처음 시작이 O인 경우는 첫 번째 플레이어가 이기게 된다.

Source Code

#include <iostream>
#include <string>
using namespace std;

int a[100000];

int main() {
	int n;
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		cin >> a[i];
	}

	string ans = "second";
	for (int i = 0; i < n; i++)
	{
		if (a[i] % 2 != 0)
		{
			ans = "first";
			break;
		}
	}

	cout << ans << endl;
}

ABC_178_E - Dist Max

Problem link

https://atcoder.jp/contests/abc178/tasks/abc178_e

Problem Summary

x, y 좌표가 주어질 때 가장 먼 맨해튼 거리를 구하는 문제.

Solution

일단 유명한 문제라고 하는데... 처음 대회에서는 풀지 못했다...

다시 천천히 해보면 어렵지 않은 문제이긴 하다

먼저 조건을 잘 써보면,| xi - xj | + | yi - yj |의 최댓값을 찾는 문제인데 절댓값을 벗겨준 후 정리해줄 수 있다.

xi > xj, yi > yj

(xi - xj) + (yi - yj)
(xi + yi) - (xj + yj)

xi < xj, yi > yj

-(xi - xj) + (yi - yj)
-(xi - yi) + (xj - yj)

xi > xj, yi < yj

(xi - xj) - (yi - yj)
(xi - yi) - (xj - yj)

xi < xj, yi < yj

-(xi - xj) - (yi - yj)
-(xi + yi) + (xj + yj)

잘 보면 양쪽이 (xj + yj) 또는 (xj - yj) 형식으로 정리가 되는데 x, y값의 합 또는 x, y의 값의 차를 전부 구하고 그중에 최대가 되도록 해주면 된다.

따라서 정답은 max( max(xi + yi) - min(xi + yi), max(xi - yi) - min(xi - yi) )

Source Code

#include <iostream>
#include <climits>
using namespace std;

int main() {
	int n;
	cin >> n;

	int maxPlus = -INT_MAX;
	int minPlus = INT_MAX;
	int maxMinus = -INT_MAX;
	int minMinus = INT_MAX;
	for (int i = 0; i < n; i++)
	{
		int x, y;
		cin >> x >> y;

		int plus = x + y;
		int minus = x - y;

		maxPlus = max(maxPlus, plus);
		minPlus = min(minPlus, plus);
		maxMinus = max(maxMinus, minus);
		minMinus = min(minMinus, minus);
	}

	cout << max(maxPlus - minPlus, maxMinus - minMinus) << endl;
}

ARC_091_B / ABC_090_D - Remainder Reminder

Problem link

https://atcoder.jp/contests/arc091/tasks/arc091_b

Problem Summary

N을 넘지 않는 a, b 쌍 중에서 a % b가 K 보다 크거나 같은 개수를 구하는 문제.

Solution

예제 1에 힌트가 있는데, b에 대해 K + 1부터 N까지 다 돌려가면서 나머지가 K 이상이 되는 a의 개수를 구해주면 된다.

N % b를 r로 두면, a가 r 이하인 경우엔 N / b + 1번 가능하고 r보다 큰 경우는 N / b번만 가능하다.

K == 0일 땐, a == 0인 경우를 처리하기 위해 결과에서 N을 빼주면 된다. (문제에서 positive integers 라고 했으므로)

Source Code

#include <iostream>
using namespace std;

int main() {
	int n, k;

	cin >> n >> k;

	long long res = 0;
	for (int b = k + 1; b <= n; b++)
	{
		// k to b-1
		int cnt = b - k;
		res += cnt * (n / b);

		res += max(0, n % b - k + 1);
	}

	if (k == 0)
	{
		res -= n;
	}

	cout << res << endl;
}

ARC_068_B / ABC_053_D - Card Eater

Problem link

https://atcoder.jp/contests/arc068/tasks/arc068_b

Problem Summary

수가 적혀진 N개의 카드들이 있다.
카드 중에 3개를 고른 후 가장 작은 수와 가장 큰 수를 빼고 남은 수는 다시 덱에 넣는다.
다른 수의 카드의 개수의 최댓값을 출력하는 문제.

Solution

먼저 3개를 고르고 하나를 다시 집어넣는 연산을 잘 살펴보자.

그냥 아무 두 개의 카드를 제거하는 것과 같다는 것을 알 수 있다.
일단, 각 카드가 한 장밖에 없는 경우는 연산을 하면 안되고, 두 장 이상 있다면 그 두 장을 다 뽑게 되면 나머지 하나는 다시 덱으로 돌아가기 때문이다.

각 카드의 수를 전부 센 다음 제거해야 할 개수를 더한 다음 홀수면 카드의 종류의 수 -1, 짝수면 카드의 종류의 수를 출력하면 된다.

Source Code

#include <iostream>
#include <map>
using namespace std;

int main() {
	int n;
	cin >> n;

	map<int, int> cnt;

	for (int i = 0; i < n; i++)
	{
		int a;
		cin >> a;
		cnt[a]++;
	}

	int toRemove = 0;
	for (auto& i : cnt)
	{
		if (i.second > 1)
		{
			toRemove += i.second - 1;
		}
	}

	if (toRemove % 2 == 0)
	{
		cout << cnt.size() << endl;
	}
	else
	{
		cout << cnt.size() - 1 << endl;
	}
}

ABC_080_C - Shopping Street

Problem link

https://atcoder.jp/contests/abc080/tasks/abc080_c

Problem Summary

상점을 오픈하는데, 특정 시간에 다른 상점이 열린 개수에 따라 최대로 만들 수 있는 이익을 구하는 문제.
Fij : i 상점이 j 시간에 열려 있는지 여부.
Pij : i 상점이 j 시간만큼 열린 시간이 겹쳤을 때 얻을 수 있는 이익.

Solution

처음에 문제 자체를 이해하기 좀 어려웠는데 계속 보니까 대략 머리에 들어왔다.

일단, Joisino가 상점을 열지 말지 두 가지 방법이 있고 시간이 총 10개 있으므로 단순 2^10 탐색을 해주면 된다.

상점을 열었을 경우 그 시점에 다른 상점이 열려있는 개수를 카운트 하고 더해주면 되는 간단한 문제.

Source Code

#include <iostream>
using namespace std;

int f[100][10];
int p[100][11];

int main() {
	int n;
	cin >> n;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < 10; j++)
		{
			cin >> f[i][j];
		}
	}

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < 11; j++)
		{
			cin >> p[i][j];
		}
	}

	int ans = -1987654321;
	for (int i = 1; i < (1 << 10); i++)
	{
		int profit = 0;

		for (int j = 0; j < n; j++)
		{
			int cnt = 0;

			for (int k = 0; k < 10; k++)
			{
				// open
				if (i & (1 << k) && f[j][k] == 1)
				{
					cnt++;
				}
			}

			profit += p[j][cnt];
		}

		ans = max(ans, profit);
	}

	cout << ans << endl;
}

ABC_230 - AtCoder Beginner Contest 230

Contest Link

https://atcoder.jp/contests/abc230

Solved problems

A, B, C

Brief explanations

A, B: 간단
C: 칠해지는 좌표의 규칙을 알면 된다. i-j, i+j 값을 이용하면 칠해지는 위치인지 판별 가능하다.

ABC_182_E - Akari

Problem link

https://atcoder.jp/contests/abc182/tasks/abc182_e

Problem Summary

n개의 전구가 4방향으로 빛을 쏘고, m개의 블럭은 빛을 차단한다.
전체 그리드 (H*W)에서 총 몇 칸이 빛이 도달하는지 확인.

Solution

간단한 시뮬레이션 문제.
모든 전구에서 상 하 좌 우로 빛을 쏴주면서 카운트를 해주면 된다.

Source Code

#include <iostream>
#include <vector>
#include <cstring>
#include <utility>
using namespace std;

vector<pair<int, int> > bulbs;
int grid[1502][1502];
int h, w, n, m;

const int direction[][2] = { 1, 0, -1, 0, 0, 1, 0, -1 };

int main() {
	cin >> h >> w >> n >> m;

	// set border to -1
	for (int i = 0; i <= h; i++)
	{
		grid[i][0] = -1;
		grid[i][w + 1] = -1;
	}
	for (int i = 0; i <= w; i++)
	{
		grid[0][i] = -1;
		grid[h + 1][i] = -1;
	}

	for (int i = 0; i < n; i++)
	{
		int a, b;
		cin >> a >> b;

		grid[a][b] = 1;
		bulbs.push_back(make_pair(a, b));
	}

	for (int i = 0; i < m; i++)
	{
		int c, d;
		cin >> c >> d;

		grid[c][d] = -1;
	}

	int ans = n;

	for (int i = 0; i < n; i++)
	{
		int a = bulbs[i].first;
		int b = bulbs[i].second;

		for (int d = 0; d < 4; d++)
		{
			int x = a, y = b;
			int cnt = 1;

			while (true)
			{
				int nx = x + direction[d][0] * cnt;
				int ny = y + direction[d][1] * cnt;

				if (grid[nx][ny] == -1 || grid[nx][ny] == 1)
				{
					break;
				}

				if (grid[nx][ny] == 0)
				{
					ans++;
				}
				grid[nx][ny] = 2;
				cnt++;
			}
		}
	}

	cout << ans << endl;
}

PANASONIC_2020_D - String Equivalence

Problem link

https://atcoder.jp/contests/panasonic2020/tasks/panasonic2020_d

Problem Summary

n 길이의 isomorphic 한 normal form를 전부 구하는 문제

Solution

예시에 2밖에 없어서 뭔가 애매한데 4 예시를 직접 만들어보자.

aaaa
aaab
aaba
aabb
aabc
abaa
abab
abac
abba
abbb
abbc
abca
abcb
abcc
abcd

총 15개가 나오고 규칙을 찾을 수 있다.

s[i] 뒤에는 s[0 ... i] + 1 이하의 알파벳이 와야 한다.

좀더 formal하게는

이건 재귀적으로 간단하게 짤 수 있다.

Source Code

#include <iostream>
#include <string>
using namespace std;

int n;

void solve(string s, int prevMax) {
	if (s.length() == n)
	{
		cout << s << endl;
		return;
	}

	for (int i = 0; i <= prevMax + 1; i++)
	{
		solve(s + (char)('a' + i), max(prevMax, i));
	}
}

int main() {
	cin >> n;

	solve("", -1);
}

AtCoder Beginner Contest 204

https://atcoder.jp/contests/abc204