Google Codejam Kickstart 2020 Round B 후기

올해 킥스타트 B라운드는 주말 아침8시에 시작을 해서, 어째저째 술먹고 새벽에 퍼질러 자다가 비몽사몽한상태에서 용캐 일어나서 한번 풀어보았다.

 

코드잼 1Round에서 엄청 발렸던 기분을 Kickstart를 풀면서 조금 달래주려 했는데, 확실히 Kickstart는 Codejam에 비해서는 난이도가 낮은 듯 한 느낌을 많이 받았다.

 

총 4문제가 나왔고, 예전에는 Large set은 Full feedback을 안주고 Hidden verdict형식이었는데, 이번에는 다 Visible verdict로 진행이 되었다.

 

Bike Tour

봉우리 갯수를 새는 문제이다. for loop로 순회하면서 좌우 값을 봐서 그 보다크면 봉우리로 갯수를 카운트 하면 되는 간단한 문제이다.

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

typedef long long ll;
typedef pair<int, int> pii;
#define endl '\n'

int arr[105];
void solve() {
	int n;
	int ans = 0;
	cin >> n;
	for (int i = 0; i < n; i++) cin >> arr[i];
	for (int i = 1; i < n - 1; i++) {
		if (arr[i] > arr[i - 1] && arr[i] > arr[i + 1]) ans++;
	}
	cout << ans << endl;
}
int main() {
	int tc; cin >> tc;
	for (int t = 1; t <= tc; t++) {
		printf("Case #%d: ", t);
		solve();
	}
}

Bus Routes

버스가 오는 시간 주기를 알때, 마지막 버스를 탈 수 있는 가장 늦은 시간을 구하는 문제이다. 배수개념으로 접근하면 될 것 같은데, 파라메트릭 서치를 이용하면 간단하게 풀 수 있다. 쿼리를 바이너리 서치로 확인하는건데, 쿼리 확인시에는 floor(v/x) * x를 해서 가장 가까운 배수를 찾아내면 된다.

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

typedef long long ll;
typedef pair<int, int> pii;
#define endl '\n'

ll a[1005];
int n;
ll d;
bool q(ll v) {
	
	for (int i = 0; i < n; i++) {
		ll x = a[i];
		v = max(v, (v + x - 1) / x * x);
		if (v > d)
			return false;
	}
	return true;
}
void solve() {
	ll l, r;
	l = 1;
	//r = (ll)1e12;
	cin >> n >> d;
	r = d;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
	}
	while (l < r) {
		ll m = (l + r + 1) / 2;
		//printf("%lld %lld %lld\n", l, r, m);
		if (q(m)) {
			l = m;
		}
		else {
			r = m - 1;
		}
	}
	cout << l << endl;
}
int main() {
	int tc; cin >> tc;
	for (int t = 1; t <= tc; t++) {
		printf("Case #%d: ", t);
		solve();
	}
}

Robot Path Decoding

문제 내용 자체보다는, Operation code 파싱이 더 어렵다. (를 만나면 같은 depth의 )의 인댁스를 찾아서 재귀로 짜보려다가 //(O(N^2)//)인데 TLE안나려나 궁금했다가 그냥 스택으로 짜는게 더 나을거 같아서 머리를 쥐어 짜면서 스택으로 파서를 만들어 보았다. 생각보다 파서가 간단하게 만들어 졌던 것 같다. 좌표계가 wrap-around되므로 그 부분을 처리해주는 함수를 따로 만들어서 썼다.

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

typedef long long ll;
typedef pair<int, int> pii;
#define endl '\n'
const ll MOD = 1e9;
ll nor(ll v) {
	if (v < 0)
		v += MOD;
	if (v >= MOD)
		v %= MOD;
	return v;
}
struct Data {
	int op;
	ll x, y;
	void add(struct Data& rhs) {
		x += rhs.x;
		y += rhs.y;
		x = nor(x);
		y = nor(y);
	}
	void mult(int v) {
		x *= v;
		y *= v;
		x = nor(x);
		y = nor(y);
	}
};
Data calc(char c) {
	if (c == 'N') {
		return { 0, -1, 0 };
		//return make_pair(-1, 0);
	}
	else if (c == 'S') {
		return { 0, 1, 0 };
		//return make_pair(+1, 0);
	}
	else if (c == 'W') {
		return { 0, 0, -1 };
		//return make_pair(0, -1);
	}
	else if (c == 'E') {
		return { 0, 0, 1 };
		//return make_pair(0, +1);
	}
	else {
		assert(false);
	}
}

void solve() {
	string s;
	cin >> s;
	//ll x, y;
	//x = y = 0;
	stack<Data> ss;
	ss.push({ 0, 0, 0 });
	for (int i = 0; i < s.length(); i++) {
		char c = s[i];
		if (c >= '0' && c <= '9') {
			ss.push({ c - '0', 0, 0 });
			ss.push({ 0, 0, 0 });
		}
		else if (c == ')') {
			Data operand = ss.top(); ss.pop();
			Data mult = ss.top(); ss.pop();
			Data prev = ss.top(); ss.pop();
			operand.mult(mult.op);
			prev.add(operand);
			ss.push(prev);
		}
		else if (c >= 'A' && c <= 'Z') {
			Data cur = ss.top(); ss.pop();
			Data delta = calc(c);
			cur.add(delta);
			ss.push(cur);
		}
	}
	ll y = (ss.top().y + 1);
	ll x = (ss.top().x + 1);
	cout << y << ' ' << x << endl;
	while (ss.size()) ss.pop();
	//x++; y++;
	//cout << y << ' ' << x << endl;

}
int main() {
	int tc; cin >> tc;
	for (int t = 1; t <= tc; t++) {
		printf("Case #%d: ", t);
		solve();
	}
}

Wandering Robot

kickstart때는 못풀어서 나중에 Analysis랑 남의 코드들을 보고 업솔빙을 좀 했다. 아이디어 자체는 대충 냈었는데, 어차피 디테일부분을 못따라가서 구현법 팁을 알았어도 당시에는 못 풀었을 듯 하다.

1등한 사람의 코드도 좀 참고를 하고 이해안가는 부분을 동기형한테는 물어보고 해서 도움을 꽤 받았다.(사실 아직도 100%는 이해 안 된 것 같기도하고...)

 

이항계수를 구하는 부분에서 Precision Error가 많이 날 것 같았는데 결국 요구하는 정확도가 //(10^{-5}//)정도로 낮은 수준이기도 하고, log로 축소시켜서 계산한 뒤 다시 역로그(exp함수)로 되돌려서 계산하는 부분들이 신박했다.

 

근데 여기서 좀 쟁점이 되는 부분은 대각선이 딱 맞아떨어지지 않는 경우가 쟁점인데, 아래 그림을 보자.

참고로 아래 문단에서 구한다고 하는 것은 시작점을 //((0,0)//)라고 가정하고 도착지점 좌표를 //((x,y)//)라고 가정하면

//(\frac{1}{2}^{x+y}*\binom{x+y}{x}//)를 의미한다. 이를 //(f(x,y)//)라고 하자.

파란색들은 독립적으로 되기 때문에 각자 구해서 더하면 되는데, 파란색 위쪽에 비어있는 칸으로 가는 경우는 쟁점이 된다.

오른쪽 끝에 다다른 경우 무조건 아래로만 가기 때문에 해당 부분에 대한 내용들도 더해줘야 하는데, 이는 빨간색 박스에 도달하는 경우(실제로는 벽을 뚫을 순 없지만 뚫을 수 있다고 가정할 시)를 더해주면 된다. 어차피 벽을 뚫는경우 아래로 내려가는걸로 취급하면 되므로 그러하다.

 

근데 1등 코드를 확인해보면 노란색으로 가는 확률(f(노랑칸))에 1/2를 곱해서 더해버리는 식이다. 사실 노랑색 바로 아래 파란색(C) 입장에서는 바로 위 노란색(B)에서 아래로 1/2확률로 내려오는 것만 포함되어 있는데, 바로 위 노란색(B)에서 오른쪽으로 가는 경우의 확률도 더해져야 하므로 노란색으로 도달하는 확률에 1/2를 곱해서 더한다.

그리고 마찬가지로 가장 아래 노란색(B)으로 가는 확률은 바로 위 노란색(A)에서 1/2확률로 내려온경우는 포함되지만, 맨 위 노란색에서 오른쪽으로 가서 내려오는 경우확률이 빠져있으므로 이도 더해주는 식이라고 한다.(thanks for jrj) 각 부분의 정의를 명확하게 해줘야지 안햇갈린다고 한다.

 

설명하면서도 내가 약간 햇갈려서 첨언을 하자면, 대각선으로 구역을 나누는 경우 서로 겹치는 경우가 없으므로(독립이므로) 확률을 구해서 더해버리면 되는데, 노란색(B)의 경우와 아래 파란색(C)의 경우는 겹치는 경우가 있다. 그러므로 겹치지 않는 경우 중에 세어지지 않은 부분만 추가적으로 더해주는 것이다. 노란색(A, B)의 경우에서는 오른쪽으로 갈 확률이 0%이므로 이 부분만 따로 추가로 더해주는 것이고, 아래로 가는 확률이 100%, 오른쪽이 0%인데 이것이 50% 50%으로 더해져 있으므로, 부족한 아래로 가는 50%를 더해주는 것이다.

내가 착각을 했던 것이, A,B의 경우가 무조건 C까지 가야만 한다고 생각을 했는데, 어차피 C에는 A,B 경우의 수 중 절반은 더해져 있는 상황이고, 이 남은 절반만 더해주면 된다는 것이다. 이 남은 절반의 확률은 맨 오른쪽에서는 아래로만 내려가는 선택지만 생긴다는 특수한 상황때문에 생기는 것이기도 하다.

 

그리고 역으로 전체에서 중간 구멍으로 빠질 확률을 빼줘도 되는데, f(초록칸)을 죄다 구한 뒤 1/2를 곱해서 더하면 된다고 한다. 그리고 1에서 그 값을 빼줘도 될 것 같은데 아직 구현은 안해봤다.

 

아래 코드는 빨간칸을 구해서 다 더하는 방식의 코드이다.

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef long long ll;
typedef pair<int, int> pii;
#define MAXN 200005
double lnfact[MAXN];
double bicof(int a, int b) {
	return lnfact[a] - lnfact[a - b] - lnfact[b];
}
void solve() {
	int W, H, L, U, R, D;
	cin >> W >> H >> L >> U >> R >> D;

	int dist = L + D - 2;
	double ans = 0;
	if (D < H) {
		for (int i = 1; L - i > 0; i++) {
			int x = L - i;
			int y = D + i;
			double logval = bicof(dist, x - 1);
			logval -= dist;
			ans += pow(2, logval);
		}
	}
	dist = R + U - 2;
	if (R < W) {
		for (int i = 1; U - i > 0; i++) {
			int x = R + i;
			int y = U - i;
			double logval = bicof(dist, x - 1);
			logval -= dist;
			ans += pow(2, logval);
		}
	}
	cout << fixed << setprecision(8);
	cout << ans << endl;
}
int main() {
	for (int i = 2; i < MAXN; i++) {
		lnfact[i] = lnfact[i - 1] + log(i) / log(2);
	}
	int tc;
	cin >> tc;
	for (int t = 1; t <= tc; t++) {
		cout << "Case #" << t << ": ";
		solve();
	}
}