AtCoder Beginner Contest 189 후기

ABC 189 간단 후기 올립니다~ (atcoder.jp/contests/abc189)

A - Slot

간단한 구현 문제입니다.

int main() {
	string s; cin >> s;
	if (s[0] == s[1] && s[0] == s[2]) cout << "Won";
	else cout << "Lost";
}

 

B - Alcoholic

1번 부터 순차적으로 마시면서 alcohol이 X가 넘는 순간을 찾으면 됩니다. x에 100을 곱해서 소수점 계산을 피했습니다.

int main() {
	int n, x; cin >> n >> x; x *= 100;
	int sum = 0;
	for (int i = 1; i <= n; i++) {
		int a, b;
		cin >> a >> b;
		sum += a * b;
		if (sum > x) {
			cout << i; return 0;
		}
	}
	cout << -1;
}

 

C - Mandarin Orange

모든 l, r에 대한 A[l..r] 최소값 * (r-l+1) 중 최대값을 출력하면 됩니다.

(l, r) 순서쌍이 O(N^2), A[l..r] 최소값은 스위핑을 이용하여 O(1)에 구할수 있습니다. (전체 시간 복잡도 : O(N^2))

참고로, 분할정복으로 O(NlogN) , stack을 이용하여 O(N) 으로 구할 수 있을거 같습니다.

ll x[10004];
int main() {
	int i, j, n; cin >> n;
	ll ans = 0, mn;
	for (i = 1; i <= n; i++) cin >> x[i];
	for (i = 1; i <= n; i++) {
		mn = (ll)1e9;
		for (j = i; j <= n; j++) {
			mn = min(mn, x[j]);
			ans = max(ans, (ll)(j - i + 1)*mn);
		}
	}
	cout << ans;
}

 

D - Logical Expression

DP로 해결했습니다.

int n;
string x[1000];
ll dp[1000][2]; // 0=false, 1=true 
int main() {
	int i; cin >> n;
	for (i = 0; i < n; i++) cin >> x[i];
	dp[n][1] = 1; dp[n][0] = 0;
	for (i = n - 1; i >= 0; i--) {
		if (x[i].compare("AND") == 0) {
			dp[i][0] = dp[i + 1][0] * 2;
			dp[i][1] = dp[i + 1][0] + dp[i + 1][1];
		}
		else {
			dp[i][0] = dp[i + 1][0] + dp[i + 1][1];
			dp[i][1] = dp[i + 1][1] * 2;
		}
	}
	cout << dp[0][0] + dp[0][1] << '\n';
}

 

E - Rotate and Flip

연산 1,2,3,4을 원점(0,0), x축(1,0), y축(0,1)에 적용하여 시간복잡도를 O(N+M+Q)로 개선했습니다.

typedef pair<ll, ll> p; 
p O[200004], X[200004], Y[200004], xy[200004];
int N, M;
void rotate_one(p &src, p &dst, int op) {
	if (op == 1) {
		dst.x = src.y;
		dst.y = -src.x;
	}
	else {
		dst.x = -src.y;
		dst.y = src.x;
	}
}
 
void rotate_xy(int idx, int op) {
	rotate_one(O[idx - 1], O[idx], op);
	rotate_one(X[idx - 1], X[idx], op);
	rotate_one(Y[idx - 1], Y[idx], op);
}
 
void flip_one(p &src, p &dst, int op, ll center) {
	// vertical flip
	if (op == 3) {
		ll dx = center - src.x;
		dst.x = src.x + dx * 2;
		dst.y = src.y;
	}
	// horizontal flip
	else {
		ll dy = center - src.y;
		dst.x = src.x;
		dst.y = src.y + dy * 2;
	}
}
 
void flip_xy(int idx, int op, ll center) {
	flip_one(O[idx - 1], O[idx], op, center);
	flip_one(X[idx - 1], X[idx], op, center);
	flip_one(Y[idx - 1], Y[idx], op, center);
}
 
void solve(p &oo, p&xx, p &yy, p &src, p &dst) {
	dst.x = oo.x; dst.y = oo.y;
 
	ll dx, dy;
 
	// x축
	dx = xx.x - oo.x; dy = xx.y - oo.y;
	dst.x += dx * src.x;
	dst.y += dy * src.x;
 
	// y축
	dx = yy.x - oo.x; dy = yy.y - oo.y;
	dst.x += dx * src.y;
	dst.y += dy * src.y;
}
 
int main() {
	O[0] = { 0,0 }, X[0] = { 1,0 }, Y[0] = { 0,1 };
	int i;
 
	cin >> N;
	for (i = 1; i <= N; i++) cin >> xy[i].x >> xy[i].y;
 
	cin >> M;
	for (i = 1; i <= M; i++) {
		int op; cin >> op;
		if (op <= 2) rotate_xy(i, op);
		else {
			int a; cin >> a;
			flip_xy(i, op, a);
		}
	}
 
	int q; cin >> q;
	while (q--) {
		int a, b; cin >> a >> b;
		p dst;
		solve(O[a], X[a], Y[a], xy[b], dst);
		cout << dst.x << ' ' << dst.y << '\n';
	}
}