Round #731 (Div. 3)

A. Shortest Path with Obstacle

https://codeforces.com/contest/1547/problem/A

Problem - A - Codeforces

 A, B, F의 위치가 주어졌을 때 A->B로 가는 최단 거리를 구하는 문제이다.

 F가 거슬리는 경우를 생각해보자.

 A, B, F가 한 줄 위에 같이 존재하면서 F가 A, B사이에 있는 경우에만 A->B로 가는 경로에서 F를 우회하기 위해 2번의 움직임이 더 필요하다.

 그 외에 경우는  A->B 최단거리인 \(|Ax - Bx| + |Ay - By|\)가 답이 된다.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int INF = 2147483647;
const int MAX_N = 1e+5 + 1;
const int MOD = 1e5;

ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }

void solve() {
	int Ax, Ay, Bx, By, Fx, Fy;
	
	cin >> Ax >> Ay >> Bx >> By >> Fx >> Fy;

	if (
    		((Ax == Bx && Bx == Fx) && ((Ay <= Fy && Fy <= By) || (By <= Fy && Fy <= Ay)))
		|| 
        	((Ay == By && By == Fy) && ((Ax <= Fx && Fx <= Bx) || (Bx <= Fx && Fx <= Ax)))
            ) {
		cout << abs(Ax - Bx) + abs(Ay - By) + 2 << '\n';
	}
	else {
		cout << abs(Ax - Bx) + abs(Ay - By) << '\n';
	}

	return;
}

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int T;
	cin >> T;
	while (T--) {
		solve();	
	}
	return 0;
}

---

B. Alphabetical Strings

https://codeforces.com/contest/1547/problem/B

Problem - B - Codeforces

 a만 들어있는 string을 str이라고 하자. alphabetical이란, b부터 z까지 알파벳의 순서대로 str의 앞 or 뒤에 삽입했을 때 나오는 string을 일컫는다. 입력받은 string이 alphabetical인지 판별하는 게 목표인 문제이다.

 

 입력받은 string안에 들어있는 알파벳들의 위치를 기억하자. 

 이 위치를 기반으로 어떤 알파벳을 삽입하는 상황일 때 이전 알파벳의 위치를 보고 앞으로 삽입할지, 뒤로 삽입할지 판단할 수 있다. 따라서 a만 들어있는 string을 만들고 b부터 순서대로 삽입할 때 이전 알파벳의 위치가 삽입해야되는 알파벳의 위치보다 앞에 있으면 뒤에 삽입, 그렇지 않으면 앞에 삽입해준다.

 마지막으로 위 과정을 거쳐 나온 string이 입력받은 string과 같은지 확인해주면 된다.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int INF = 2147483647;
const int MAX_N = 1e+5 + 1;
const int MOD = 1e5;

ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }

int alp[26] = { 0, };
void solve() {
	memset(alp, -1, sizeof(alp)); //-1로 초기화
	string str;
	cin >> str;

	for (int i = 0; i < str.size(); ++i) {
		if (alp[str[i] - 'a'] == -1) { // 알파벳이 처음 등장
			alp[str[i] - 'a'] = i;
		}
		else if (alp[str[i] - 'a'] >= 0) { // 같은 알파벳이 두번 이상 등장
			cout << "NO\n";
			return;
		}
	}
	string ans = "a";
	for (int i = 1; i < 26; ++i) {
		if (alp[i] == -1) break; // 입력받은 string에 없는 알파벳이 나오면 break

		int prev = alp[i - 1];
		int cur = alp[i];
        
		if (prev > cur) ans = (char)('a' + i) + ans; 
		else ans += (char) ('a' + i);
	}

	if (ans == str) cout << "YES\n";
	else cout << "NO\n";

	return;
}

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int T;
	cin >> T;
	while (T--) {
		solve();
	}

	return 0;
}

---

C. Pair Programming

https://codeforces.com/contest/1547/problem/C

Problem - C - Codeforces

 문제를 처음에 잘못 읽어 여러번의 WA를 받은 문제이다. 문제의 조건과 내용은 항상 정확하게 읽어야한다는 것을 다시 한번 상기시키는 문제였다.

 

 Monocarp와 Polycarp 중 한명이 매초마다 (file 마지막에 한줄을 더 추가) or (이미 있는 라인 하나를 수정)을 한다.

 현재 파일에 적혀있는 라인의 개수와, Monocarp와 Polycarp가 각각 하는 Action들의 순서와 내용이 주어졌을 때, 가능한 Action의 순서를 출력해주어야 한다.

 

 Monocarp와 Polycarp 중 한명이라도 다음에 하는 Action이 라인을 추가하는 것이라면 greedy하게 라인을 추가해주자. 만약, 둘 다 라인을 바꿔주는 Action이라면 바꿔야하는 라인이 현재 쓰여있는 라인인지 확인해주면 된다. 마지막으로 한명이 먼저 Action을 다 끝냈을 때도 고려해주자.

 

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const int INF = 2147483647;
const int MAX_N = 1e+5 + 1;
const int MOD = 1e5;

ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }

int a[101] = { 0, };
int b[101] = { 0, };

void solve() {
	int k, n, m;
	cin >> k >> n >> m;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	for (int i = 1; i <= m; ++i) cin >> b[i];

	vector<int> ans;
	int ai = 1, bi = 1;

	for (int i = 1; i <= n + m; ++i) {
		if (ai <= n && bi <= m) { // 두명 다 할 일이 남아있을 때
			if (a[ai] == 0) { // 라인 추가
				ans.push_back(0);
				k++;
				ai++;
			}
			else if (b[bi] == 0) { // 라인 추가
				ans.push_back(0);
				k++;
				bi++;
			}
			else {
				if (a[ai] <= k) { 
					ans.push_back(a[ai++]);
				}
				else if (b[bi] <= k) {
					ans.push_back(b[bi++]);
				}
				else { // 둘 다 바꿀 수 있는 라인이 없는 경우
					cout << -1 << '\n';
					return;
				}
			}
		}
		else if(ai <= n){ // b의 Action이 끝난 경우
			if (a[ai] == 0) {
				ans.push_back(0);
				k++;
				ai++;
			}
			else if (a[ai] <= k) {
				ans.push_back(a[ai++]);
			}
			else {
				cout << -1 << '\n';
				return;
			}
		}
		else if (bi <= m) { // a의 Action이 끝난 경우
			if (b[bi] == 0) {
				ans.push_back(0);
				k++;
				bi++;
			}
			else if (b[bi] <= k) {
				ans.push_back(b[bi++]);
			}
			else {
				cout << -1 << '\n';
				return;
			}
		}
		
	}

	for (int num : ans) cout << num << ' ';
	cout << '\n';
	return;
}

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int T;
	cin >> T;
	while (T--) {
		solve();
	}
	return 0;
}

---

D. Co-growing Sequence

추가 예정

---

E. Air Conditioners

추가 예정