AtCoder ABC 260 풀이

https://atcoder.jp/contests/abc260/tasks

Tasks - AtCoder Beginner Contest 260

 

A. 

1개만 나오는 문자를 출력해주면 됩니다. s[0], s[1], s[2] 개수를 세주고 경우를 나누면 됩니다.

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

int main() {
    cin.tie(0)->sync_with_stdio(0);
	string s; cin >> s;
	int c1 = count(s.begin(), s.end(), s[0]);
	int c2 = count(s.begin(), s.end(), s[1]);
	int c3 = count(s.begin(), s.end(), s[2]);
	if (min({ c1, c2, c3 }) == 1) {
		if (c1 == 1) cout << s[0];
		else if (c2 == 1) cout << s[1];
		else if (c3 == 1) cout << s[2];
	}
	else {
		cout << -1;
	}
}

 

 

 

B. 

수학점수 순으로 X명 뽑고, 나머지 중에서 영어 점수 순으로 Y명, 나머지 중에 두 점수 합 순으로

Z명을 뽑아주면 됩니다. 정렬을 3번 해주면 됩니다. 

#include<bits/stdc++.h>
using namespace std;
int n, x, y, z;
struct test {
	int math, eng, idx;
};
test tt[1001];

bool cmp1(test a, test b) {
	if (a.math == b.math) return a.idx < b.idx;
	return a.math > b.math;
}

bool cmp2(test a, test b) {
	if (a.eng == b.eng) return a.idx < b.idx;
	return a.eng > b.eng;
}

bool cmp3(test a, test b) {
	if (a.math+a.eng == b.math+b.eng) return a.idx < b.idx;
	return a.math + a.eng > b.math + b.eng;
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
	cin >> n >> x >> y >> z;
	for (int i = 0; i < n; i++) cin >> tt[i].math;
	for (int i = 0; i < n; i++) cin >> tt[i].eng;
	for (int i = 0; i < n; i++) tt[i].idx = i + 1;
	vector<int> ans;
	sort(tt, tt + n, cmp1);
	for (int i = 0; i < x; i++) {
		ans.push_back(tt[i].idx);
	}
	sort(tt + x, tt + n, cmp2);
	for (int i = x; i < x + y; i++) {
		ans.push_back(tt[i].idx);
	}
	sort(tt + x + y, tt + n, cmp3);
	for (int i = x + y; i < x + y + z; i++) {
		ans.push_back(tt[i].idx);
	}
	sort(ans.begin(), ans.end());
	for (int& i : ans)cout << i << '\n';
}

 

 

C.

2가지 시행을 합니다. r[i], b[i]를 각각 blue 1에서 r, b level i를 만드는 경우의 수라고 정의합니다. 

점화식은 문제에서 하라는대로 짜주면 됩니다. 답은 r[n]이 됩니다. 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
ll n, x, y, r[11], b[11];

int main() {
    cin.tie(0)->sync_with_stdio(0);
	cin >> n >> x >> y;
	b[1] = 1;
	for (int i = 2; i <= n; i++) {
		b[i] = r[i - 1] + y * b[i - 1];
		r[i] = r[i - 1] + x * b[i];
	}
	cout << r[n];
}

 

 

D.

i번째 카드를 뽑을 때 그 전까지 나온 수들중 최솟값을 찾고 그 수 위치에 1을 더해줍니다. 

수 위치에 더해진 값이 k가 되는 순간 더해지는데 쓴 모든 카드를 제거할 수 있다고 합니다. 

우선 최솟값을 찾고 지우고 넣는 과정이 필요하므로 std::set을 써줍니다.

더해지는데 쓴 모든 카드를 제거하는 방법은 크게 2가지로 구현해줄 수 있습니다.

1. 매번 더할 때마다 최솟값인 그 수를 제거하고 자기 자신을 최솟값처럼 만들어주는 것입니다. 

2. 맨번 더할 때마다 최솟값인 그 수의 벡터에 i번째 카드를 저장해준 후 k가 되면 출력해주면 됩니다.

D치곤 까다로운 문제네요.  

#include<bits/stdc++.h>
using namespace std;
const int MAX = 2000005;
int par[MAX], cnt[MAX], ans[MAX];
set<int>s;

int main() {
    ios::sync_with_stdio(0), cin.tie(0);

    int n, k;
    cin >> n >> k;
    vector<int>ans(n + 1, -1);

    for (int i = 1; i <= n; i++) {
        int p; cin >> p;
        auto it = s.lower_bound(p);
        if (it != s.end()) {
            par[p] = *it;
            cnt[p] = cnt[*it] + 1;
            s.erase(*it);
            s.insert(p);
        }
        else {
            cnt[p]++;
            s.insert(p);
        }
        if (cnt[p] == k) {
            s.erase(p);
            int x = p;
            for (int j = 0; j < k; j++) {
                ans[x] = i;
                x = par[x];
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        cout << ans[i] << '\n';
    }
}

 

E. 

풀이 예정

 

 

F. 

S에 비해 T가 작네요. 뭔가 O(T^2)이내에 해주면 될 것 같습니다. 

4사이클이 이루는 경우는 예제를 그려보면 쉽게 알 수 있습니다. 

이제 V1의 각 원소 u에 대해 mark[x][y]=u 라는 것은 g[u]안에 u와 연결된 x와 y가 존재한다는 뜻입니다. 

그럼 각 원소마다 이중문을 돌면서 mark[x][y]가 갱신되는지 봅니다. 만약 mark[x][y]가 -1이 아니라면

이미 mark[x][y]=v인 v가 존재하므로 그 v , x, y와 현재 원소 u를 출력하고 끝내주면 됩니다. 

근데 시간복잡도는 얼마일까요? 그냥 생각했을 땐 최악의 경우 O(ST^2)인 것 같지만

M<=3e5이므로 모든 쌍을 보는데  O(M)이 걸립니다. 따라서 시간내에 해결할 수 있습니다.   

#include<bits/stdc++.h>
using namespace std;
int s, t, m, u, v;
vector<int>g[300003];
int mark[3003][3003];

int main() {
    cin.tie(0)->sync_with_stdio(0);
	cin >> s >> t >> m;
	for (int i = 1; i <= m; i++) {
		cin >> u >> v;
		v -= s;
		u--, v--;
		g[u].push_back(v);
	}
	memset(mark, -1, sizeof(mark));
	for (int from = 0; from < s; from++) {
		for (auto& u: g[from]) {
			for (auto& v:g[from]) {
				if (u == v) continue;
				if (mark[u][v] == -1) {
					mark[u][v] = from;
				}
				else {
					int to = mark[u][v];
					cout << u + s + 1 << " " << v + s + 1 << " ";
					cout << from + 1 << " " << to + 1 << "\n";
					return 0;
				}
			}
		}
	}
	cout << -1 << '\n';
}