Round #707 (Div. 2)

A. Alexey and Train

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

Problem - A - Codeforces

 역을 떠나는 조건을 잘못 읽어서 4번의 WA를 받았다...

 

 문제에서 원하는대로 구현하면 된다. 

 주의할 점으로 떠나는 시간이 (현재 시간 + \(\left \lceil \frac{(b_i - a_i)}{2} \right \rceil\)) 이 \(b_i\)보다 작다면 출발을 못하기 때문에, 현재시간을 \(b_i\)로 설정해준다.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int INF = 2147483647;

vector<pair<int, int>> train(100001);
vector<int> extra(100001);

int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int T;
	cin >> T;
	while (T--) {
		int n;
		cin >> n;
		for (int i = 1; i <= n; i++) cin >> train[i].first >> train[i].second;
		for (int i = 1; i <= n; i++) cin >> extra[i];
        
		int time = 0; // 현재 시간
        
		for (int i = 1; i <= n; i++) {
			time += (train[i].first - train[i - 1].second + extra[i]); // 역에 도착하는 시간
            
			if (i != n) { // 마지막 역이 아니라면 떠나는 시간을 정해야함.
				time += (int)round(((double)train[i].second - (double)train[i].first) / 2);
				time = max(time, train[i].second);
			}
		}
		cout << time << '\n';

	}

	return 0;
}

---

B. Napoleon Cake

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

Problem - B - Codeforces

 stack을 이용하여 \(log n\)에 해결했다.

 \(a\)층\((1 <= a <= n)\)에서 \(b\)만큼의 레이어가 drench됐다면 \((a - b + 1)\)층까지 drench됐다는 의미이다.따라서 현재 \(a\)층이고, \(b\)만큼 drench됐다면 stack의 top이 \((a - b)\)보다 크다면 계속 pop해준다. ( == drench되는 층들을 stack에서 제거하는 과정)

 결국, stack에 남아있는 레이어 번호는 drench되지 않은 레이어이다.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int INF = 2147483647;
vector<bool> isNotDrenched;
int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	stack<int> stk;
	int T;
	cin >> T;
	while (T--) {
		int n;
		cin >> n;
		isNotDrenched.clear();
		isNotDrenched.resize(n + 1);
		for (int i = 1; i <= n; i++) {
			stk.push(i);
			int level;
			cin >> level;
			while (!stk.empty() && stk.top() > (i - level))
				stk.pop();
		}
		while (!stk.empty()) {
			isNotDrenched[stk.top()] = true;
			stk.pop();
		}
		for (int i = 1; i <= n; i++)
			if (isNotDrenched[i]) cout << 0 << ' ';
			else cout << 1 << ' ';
		cout << '\n';

	}
	
	return 0;
}

---

C. Going Home

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

Problem - C - Codeforces

 \(a[i] + a[j], ( i != j )\) 의 최댓값인 5백만이란 큰 숫자에 겁 먹지말자. (난 겁 먹었었다.)

 단순히 \(a[i] + a[j]\)를 index로 하는 벡터에 (i , j) 한 쌍을 push_back해주고 해당 인덱스에 여러 쌍이 존재한다면, \(x \neq  y \neq  z \neq  w\)를 만족하는 두 쌍을 찾으면 된다. 여기서 Time Limit이 뜨지 않을까라는 의구심이 든다.

 

 정답은 "Time Limit은 뜨지 않는다" 이다. 왜 그런지에 대해 araboja.

 

 \(a[i] + a[j]\)를 index로 하고 \( {i, j} \)를 저장하는 벡터를 sum이라고 해보자.

 모든 쌍 안에 두 index는 서로 다르다. 그렇다면 \(sum[a[i] + a[j]]\)에 두 쌍의 index에서 우리가 원하는 답이 안되는 경우는 \( (x, y_1), (x, y_2) , (x \neq  y_1 \neq  y_2)\)이다. 너무 슬픈 상황이다. 여기서 \(x\)를 갖는 한 쌍이 추가됐다고 생각해보자. 

\( (x, y_1), (x, y_2) , (x, y_3)\). 상황은 여전히 암울하다. 하나 더 추가해보자.

\( (x, y_1), (x, y_2) , (x, y_3), (x, y_4)\). 아직도 암울한가 ? 그렇지 않다. 저 네 쌍의 index로부터 우리가 알 수 있는건 \(a[y_1] = a[y_2] = a[y_3] = a[y_4]\) 이고 \(y_1 \neq  y_2 \neq  y_3 \neq  y_4\)이다. 찾았다. \((y_1, y_2), (y_3, y_4)\)이 답이 될 수 있다. 도출할 수 있는 결론은 "\(a[i] + a[j]\)가 같은 네 쌍 이상의 index가 있다면 우리는 무조건 답을 찾아낼 수 있다."

 

 정리해보자. sum의 한 index안에 네 개 이상의 원소를 갖고 있고, 이 원소들 중 두 개를 뽑아 비교했을 때 답이 안되는 경우는 \( (x, y_1), (x, y_2) , ... , (x, y_m) , ( m<=n)\) 이다. 이 외의 경우는 모두 상수 시간 안에 답을 찾아낼 수 있으므로, 시간 복잡도는 \(O(n^2)\)으로 봐도 무방하다.

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int INF = 2147483647;
const int MOD = 998244353;
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }

vector<vector<pair<int, int>>> sum(5000000);
int a[200001] = { 0, };
int main() {
	ios::ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> a[i];
		for (int j = 1; j < i; j++) {
			sum[a[j] + a[i]].push_back({ j, i });
			if (sum[a[j] + a[i]].size() > 1) {
				vector<pair<int, int>>& vec = sum[a[j] + a[i]];

				for (int p1 = 0; p1 < vec.size(); p1++) {
					int x = vec[p1].first, y = vec[p1].second;
					for (int p2 = p1 + 1; p2 < vec.size(); p2++) {
						int z = vec[p2].first, w = vec[p2].second;

						if (x == z || x == w || y == z || y == w) continue;

						cout << "YES\n" << x << ' ' << y << ' ' << z << ' ' << w;
						return 0;
					}
				}
			}
		}
	}

	cout << "NO\n";

	return 0;
}