Grakn Forces 2020

2솔했다. 원래는 b pretest까진 맞췄었는데 모든게 같은 수로 이루어져 있는 데이터 셋이 부족했는데 그걸 완벽하게 처리하지 못했다  ㅠㅠ 2100등정도 찍히는거 보고 잤는데 일어나보니 3500등정도로 떨어진거 같다. 다음엔 다시 블루 복귀 하자.

 

 

A.

For each ii, ai≠bi, ai≠ci, bi≠ci 라는 조건만 읽으면 잘 해결해낼 수 있다.

우선 처음 숫자를 저장해놓는다.(마지막이랑 비교해야 함) 그리고 계속 수를A에서 가져온다.

그러다 이전에 가져온 수와 동일하면 b와 가져온다.(b는 a랑 다르니까 무조건 먹을 수 있다.)

그리고 마지막에선, 그전에 가져온 수와 a가 동일하고 처음 가져온 수 와 b가 동일하면 c를 먹어준다.

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<cmath>
#include<string>
#include<functional>
#include<queue>
 
using namespace std;
using ll = long long;
const int inf = 1234567891, n_ = 300000 + 100;
ll a, b, c, y, t, n, m, x, ans = 0, sum = 0, A[n_], B[n_], C[n_];
ll arr[n_];
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> t;
	while (t--) {
		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];
		b = A[0];
		a = A[0];
		cout << A[0] << ' ';
		for (int i = 1; i < n-1; i++) {
			if (A[i] != a) {
				cout << A[i] << ' ';
				a = A[i];
			}
			else {
				if (B[i] != a)
					a = B[i];
				else a = C[i];
				cout << a << ' ';
			}
		}
		if (A[n - 1] != b && A[n - 1] != a) c = A[n - 1];
		if (B[n - 1] != b && B[n - 1] != a) c = B[n - 1];
		if (C[n - 1] != b && C[n - 1] != a) c = C[n - 1];
		cout << c << ' ';
		cout << '\n';
	}
}

 

B.

1~200등 스코어 보드 보니까 ㅋㅋ 나처럼 pretest 맞았다가 틀린사람 수두룩 한 거 같다. 

우선 숫자를 몇번 변하는지를  살펴본다.  예제처럼 0 1 2 2 3 3 3 4 4 4 4 가 주어지면 0->1,1->2,2->3,3->4 4번 변화한 것이다. 이제 주어진 k의 의미를 생각해봐야 하는데 잘 떠올려 보면 한번의 수열에 숫자를 변화시킬 수 있는 횟수 +1 임이 자명하다. 

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<cmath>
#include<string>
#include<functional>
#include<queue>
 
using namespace std;
using ll = long long;
const int inf = 1234567891, n_ = 300000 + 100;
ll a, b, c, y, t, n, m, x, ans = 0, sum = 0, A[n_], B[n_], C[n_], k;
double xx, yy;
ll arr[n_];
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> t;
	while (t--) {
		cin >> n >> k;
		c = 0;
		for (int i = 1; i <= n; i++) {
			cin >> arr[i];
			if (arr[i] != arr[i - 1] && i != 1)
				c++;
		}
		if (c && k == 1)ans = -1;
		else {
			if (!c || k == 1)ans = 1;
			else
				ans = (c - 1) / (k - 1) + 1;
		}
		cout << ans;
		cout << '\n';
	}
}

그럼이제 ans= (c-1)/(k-1)+1이 되는데 항상 c가 0이 될때, k가 1이 될때를 생각해줘야 한다. 이걸 안하면 틀릴확률이 다분하다.

 

 

C.

덱에 들어온 숫자들을 모두 집어넣는다. 그리고 변수를 만들어, 자동차들의 위치와 속력을 저장해 놓는다. 그리고 매 경우에 대해 front와 back중에 누가 더 먼저 도달하는지를 계산하고 더 먼저 도달하는 쪽을 pop한다.

#include<iostream>
#include<algorithm>
#include<vector>
#include<cstring>
#include<cmath>
#include<string>
#include<functional>
#include<queue>
#include<deque>
using namespace std;
using ll = long long;
const int inf = 1234567891, n_ = 300000 + 100;
ll a, b, c, y, t, n, m, x, sum = 0, A[n_][2], B[n_][2], C[n_][2], k, d;
double xx, yy;
ll arr[n_];
 
int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cout << fixed;
	cout.precision(12);
	cin >> t;
	while (t--) {
		deque<int> dq;
		cin >> n >> m;
		for (int i = 0; i < n; i++) {
			cin >> a;
			dq.push_back(a);
		}
		double sum = 0;
		double a, b, c, d;
		a = 1, b = 1, c = 0, d = m;
		while (dq.size()) {
			int cur1 = dq.front(), cur2 = dq.back();
		/*	if (cur1 == cur2) {
				sum += (d - c) / (a + b);
				break;
			}*/
			 if ((cur1 - c)/a < (d - cur2)/b) {
				dq.pop_front();
				sum += (cur1 - c) / a;
				//sum += (cur1 - c) / b;
				d -= b * ((cur1 - c) / a);
				a++;
				c = cur1;
			}
			else {
				dq.pop_back();
				sum += (d- cur2) / b;
				//sum += (d cur2) / a;
				c += a * ((d - cur2) / b);
				b++;
				d = cur2;
			}
 
		}
		sum += (d - c) / (a + b);
		cout << sum << '\n';
	}
}

D는 tourist님 코드 보고 이해했다.

우선 x좌표를 기준으로 모든 것을 바라봐야 한다. 즉 아무리 커봐야 100만번에 안해 해결되므로 x가 a필요할때 y의 움직임의 최솟값을 arr[a]에 저장해 두는 관점에서 해결한다. 뭔가 이문제는 웰논인거 같다... 다들 풀이가 비슷비슷 하다.

/**
 *    author:  tourist
 *    created: 30.09.2020 17:48:42       
**/
#include <bits/stdc++.h>
 
using namespace std;
 
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<int> a(n), b(n);
  for (int i = 0; i < n; i++) {
    cin >> a[i] >> b[i];
  }
  vector<int> c(m), d(m);
  for (int i = 0; i < m; i++) {
    cin >> c[i] >> d[i];
  }
  const int MAX = 1000010;
  vector<int> v(MAX);
  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      if (a[i] <= c[j]) {
        v[c[j] - a[i]] = max(v[c[j] - a[i]], d[j] - b[i] + 1);
      }
    }
  }
  int ans = 2 * MAX;
  int mx = 0;
  for (int dx = MAX - 1; dx >= 0; dx--) {
    mx = max(mx, v[dx]);
    ans = min(ans, dx + mx);
  }
  cout << ans << '\n';
  return 0;
}

투어리스트 코드임.