준연구소

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

A - Very Very Primitive Game

간단한 구현 문제입니다. 먼저 시작하는 사람의 캔디가 더 많으면 먼저 시작하는 사람이 이기고, 그렇지 않으면 다른 사람이 이깁니다.

int main() {
	int a, b, c; cin >> a >> b >> c;
	if (c == 0) {
		if (a > b) cout << "Takahashi";
		else cout << "Aoki";
	}
	else {
		if (b > a) cout << "Aoki"; 
		else cout << "Takahashi";
	}
}

B - Magic 3

간단한 구현 문제입니다.  X < S and Y > D인 (X, Y)가 존재하면 Yes, 아니면 No를 출력하면 됩니다.

int main() {
	int n, s, d; cin >> n >> s >> d;
	int x, y;
	while (n--) {
		cin >> x >> y;
		if (x<s && y>d) {
			cout << "Yes"; return 0;
		}
	}
	cout << "No";
}

C - Bowls and Dishes

완전탐색 문제입니다. K명의 사람이 C or D를 선택하는 모든 경우(2^K)에 대하여 가장 많은 조건을 만족하는 경우를 출력하면 됩니다

typedef pair<int, int> p;
 
int N, M, K, ans, S[100];
p ab[100], cd[100];
 
void f(int idx) {
	if (idx == K) {
		int dish[104], i;
		for (i = 1; i <= N; i++) dish[i] = 0;
		for (i = 0; i < K; i++) {
			if (S[i] == 1) dish[cd[i].x] = 1;
			else dish[cd[i].y] = 1;
		}
		int sum = 0;
		for (i = 0; i < M; i++) {
			if (dish[ab[i].x] && dish[ab[i].y]) sum++;
		}
		ans = max(ans, sum);
		return;
	}
	S[idx] = 1; f(idx + 1);
	S[idx] = 2; f(idx + 1);
}
 
int main() {
	int i;
	cin >> N >> M;
	for (i = 0; i < M; i++) cin >> ab[i].x >> ab[i].y;
	cin >> K;
	for (i = 0; i < K; i++) cin >> cd[i].x >> cd[i].y;
	f(0);
	cout << ans;
}

D - Staircase Sequences

수학 문제입니다. 등차수열의 시작과 끝을 각각 a, b라고 할 경우 a + (a+1) + ... + b = N 인 (a, b) 쌍의 개수를 구하면 됩니다. 좌변은 (1+2+...+b) - (1+2+...+a-1) 이므로, b(b+1) - a(a-1)= 2N --> (b+a)(b-a+1)=2N이 됩니다.

2N을 xy꼴로 나타내서 x=b+a, y=b-a+1 or x=b-a+1, y=b+a가 성립하는지 확인하면 됩니다.

ll N;

inline int f(ll x, ll y) {
	if ((x + y - 1) % 2 == 0) return 1;
	return 0;
}
 
int main() {
	cin >> N;
	N *= 2;
	ll ans = 0;
	for (ll i = 1; i*i <= N; i++) {
		if (N%i) continue;
		ll j = N / i;
		if (f(i, j)) ans++;
		if (f(-i, -j)) ans++;
	}
	cout << ans;
}

E - Magical Ornament

Graph + bit DP 문제입니다. M개의 이웃한 쌍 (A,B)를 edge, N개의 gem이 node인 graph를 생각하자. K개의 C에 대하여 Ci에서 Cj의 shortest path를 구하자.(BFS 이용) 모든 (Ci, Cj) 쌍의 shortest path를 D[K][K]라고 하자. K개의 C를 node, D를 edge로 갖는 Graph에서 임의의 정점에서 다른 모든 노드를 방문하는 최소 비용 (salesman problem)을 구하면 된다.

int N, M, K, C[20], CC[100004], CI[100004], S[20];
vector<int> adj[100004];
int adj2[20][20];
const int INF = (int)1e9;
int dp[1 << 17][17];
 
int dfs(int state, int u) {
	int &ret = dp[state][u]; if (ret != -1) return ret;
	if (state == ((1 << K) - 1)) return ret = 0;
 
	ret = INF;
	for (int v = 0; v < K; v++) {
		if (state&(1 << v)) continue;
		if (adj2[u][v] == -1) continue;
		int a = dfs(state | (1 << v), v) + adj2[u][v];
		if (a < INF) ret = min(ret, a);
	}
	return ret;
}
 
int main() {
	int i, j;
	cin >> N >> M;
	for (i = 0; i < M; i++) {
		int a, b; cin >> a >> b;
		adj[a].push_back(b); adj[b].push_back(a);
	}
	cin >> K;
	for (i = 0; i < K; i++) {
		cin >> C[i]; CC[C[i]] = 1; CI[C[i]] = i;
	}
 
	for (i = 1; i <= N; i++) {
		if (CC[i] == 0) continue;
		queue<int> q; q.push(i);
		vector<int> dist(N + 1, -1); dist[i] = 0;
		while (!q.empty()) {
			int u = q.front(); q.pop();
			for (auto v : adj[u]) {
				if (dist[v] != -1) continue;
				dist[v] = dist[u] + 1;
				q.push(v);
			}
		}
		for (j = 1; j <= N; j++) {
			if (CC[j] == 0 || i == j) continue;
			adj2[CI[i]][CI[j]] = adj2[CI[j]][CI[i]] = dist[j];
		}
	}
 
	int ans = INF;
	for (i = 0; i < (1 << K); i++) for (j = 0; j < K; j++) dp[i][j] = -1;
	for (i = 0; i < K; i++) {
		int ret = dfs(1 << i, i);
		if (ret < INF) ans = min(ans, ret + 1);
	}
	if (ans == INF) ans = -1;
	cout << ans;
}

F - Shift and Inversions

Segment Tree 문제입니다. i ~ i + N -1 구간의 inversion count를 구하면 됩니다. (0<= i <N) i=0일 경우는 segment tree를 이용하면 됩니다. (소스코드 rev_cnt) i=1 ~ N-1일 경우는 A[i]보다 작은 숫자와 큰 숫자는 O(1)에 찾을 수 있습니다. (소스크도 up, dn) 이유는 0 ~ N-1 숫자가 한 번씩 나오기 때문입니다.

struct sg {
	int st[1200004];
	void upd(int a, int b, int node, int node_st, int node_en) {
		if (a < node_st || node_en < a) return;
		if (node_st == node_en) {
			st[node] = b; return;
		}
		upd(a, b, node * 2, node_st, (node_st + node_en) / 2);
		upd(a, b, node * 2 + 1, (node_st + node_en) / 2 + 1, node_en);
		st[node] = st[node * 2] + st[node * 2 + 1];
	}
	int qry(int a, int b, int node, int node_st, int node_en) {
		if (a > node_en || node_st > b) return 0;
		if (a <= node_st && node_en <= b) return st[node];
		return qry(a, b, node * 2, node_st, (node_st + node_en) / 2) +
			qry(a, b, node * 2 + 1, (node_st + node_en) / 2 + 1, node_en);
	}
}S;
 
int main() {
	int i, n; cin >> n;
	vector<int> A(n + 1);
	ll rev_cnt = 0;
	for (i = 1; i <= n; i++) {
		cin >> A[i]; A[i]++;
		S.upd(A[i], 1, 1, 1, n);
		rev_cnt += (i - S.qry(1, A[i], 1, 1, n));
	}
	cout << rev_cnt << '\n';
	for (i = 1; i < n; i++) {
		int dn, up;
		dn = A[i] - 1; up = n - A[i];
		rev_cnt = rev_cnt - dn + up;
		cout << rev_cnt << '\n';
	}
}

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';
	}
}