(2021년 1월 28일에 작성한 글입니다.)
Dashboard - Codeforces Round #697 (Div. 3) - Codeforces
codeforces.com
ㅎㅎㅎ
벌써 며칠 됐네...
이 날...
파이썬 멘토 첫 날이 끝나고 너무 피곤했고
내가 뭔데 감히 어떤 말을 하는 바람에
너무 미안해서 몇 시간동안 끙끙 앓고
심장이 뛰다가 막 열도 나고(코로나일까봐 무서웠다..)
몸이 안 좋아서 코포 전에 자고 일어났다
그랬더니 갑자기 15분 연기래
이 날 동훈이랑 같이 하기로 했었어서
아 연기야!!!! 하면서 같이 화내고
동훈이는 N-Queen을 풀었고(나 아직도 그거 안 풂..)
나는 뭘 했는지 모르겠지만 시간이 지났고
또 열심히 해보자! 했는데 10분 더 연기되서
12시에 시작함...
그래서 열심히 문제를 풀었어!
그치만 queue가 정말 정말 느렸고
얼마나 느렸냐면
A, B 낼 때도 느려서 한 3분? 걸린거 같은데
C는 제출하고 나서 20분동안 채점이 안 됐다...
결국 언레 됐고....ㅜㅜ
효규가 블루 갔겠다고 아쉽다고 얘기해줘서
나도 그렇게 생각하고 아쉬워했는데
지금 보니까 조...금 애매하다
D를 한 번에 풀었으면 가능했을지도...?
블루는 못 가더라도 레이팅 많이 올랐을텐데... 아쉽다
A.
pow2라는 배열을 만들어서 2의 제곱수들을 저장해놓고
binary_search로 N이 2의 제곱수인지 찾아봤다
만약 그렇다면 NO, 아니면 YES.
근데 이렇게 할 필요가 없다..
그냥 2로 나누어 떨어지는 동안 계속 나눈 후에
남은 수가 1이면 2의 제곱수라는 뜻이니까 NO,
1이 아닌 홀수이면 YES
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int TC;
vector<ll> pow2(60);
pow2[0] = 1;
for (int i = 1; i < 60; i++) {
pow2[i] = pow2[i - 1] * 2;
}
cin >> TC;
while (TC--) {
ll N;
cin >> N;
if (N % 2 == 0) {
if (binary_search(pow2.begin(), pow2.end(), N)) {
cout << "NO" << ENDL;
continue;
}
}
cout << "YES" << ENDL;
}
return 0;
}
B.
오히려 이게 A보다 쉬웠다.
N을 2020으로 나눈 몫이 나머지 보다 크거나 같으면 된다.
이 경우 2020에 1씩 더해 2021을 만들어 나머지를 충당할 수 있다는 의미니까!
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int TC;
cin >> TC;
while (TC--) {
ll N;
cin >> N;
ll a = N / 2020;
ll b = N % 2020;
if (a >= b) {
cout << "YES" << ENDL;
}
else {
cout << "NO" << ENDL;
}
}
return 0;
}
C.
고민을 많이 했는데 다행히 잘 풀었다
내 풀이는 남, 여 각각에 대해 그 수가 나오는 횟수를 저장해놓고
arr 배열에 (남, 여) 쌍도 저장한 뒤
모든 쌍에 대해 그 쌍과 남, 여가 겹치는 쌍의 개수를 세 주었다.
cntBoy[arr[i].first] + cntGirl[arr[i].second] - 1
-1을 해주는 이유는 지금 확인중인 쌍이 두 번 세어지니까.
그리고 겹치는 두 쌍이 있을 때
서로가 서로를 카운트 하므로
구하고자 하는 경우의 수의 2배가 구해진다.
그래서 답을 출력할 때는 2로 나눠서 출력해줘야 한다.
근데...이건 좀 돌아간 풀이다...
다른 분들 코드 보니 훨씬 더 좋은 풀이가 있다..
좋은 풀이인것도 맞지만
그냥 그렇게 풀어야 됐던거 같다..ㅋㅋㅋㅋㅋ
전체 경우의 수 nC2에서
남남끼리, 여여끼리 숫자가 같은 쌍의 개수를
또 cntC2로 구해주고
전체에서 빼주면 된다....
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int TC;
cin >> TC;
while (TC--) {
ll A, B, K;
cin >> A >> B >> K;
vector<pair<ll, ll>> arr(K + 5);
vector<ll> cntBoy(A + 5), cntGirl(B + 5);
for (ll i = 0; i < K; i++) {
ll a; cin >> a;
arr[i].first = a;
cntBoy[a]++;
}
for (ll i = 0; i < K; i++) {
ll a; cin >> a;
arr[i].second = a;
cntGirl[a]++;
}
ll result = 0;
for (int i = 0; i < K; i++) {
result += K - (cntBoy[arr[i].first] + cntGirl[arr[i].second] - 1);
}
cout << result / 2 << ENDL;
}
return 0;
}
D.
대회때는 D보다 E를 푼 사람이 더 많았어서
E부터 풀고, 언레가 된 후 D를 풀었다
이때 시간이 늦었었고.. 또 피곤했어서 고민을 많이 안 하고 풀이를 봤다..
태그에 two pointer가 있어서 아무 생각 없이 two pointer로 합 구하는 걸로 풀었는데
말도 안 되는 풀이다.. 왜 그랬을까...?ㅎ
그래서 결국 풀이를 봤고
그리디 + 이분탐색 느낌이었다. 진짜 신기했다.
point가 1인 것끼리, 2인 것끼리는
어차피 소요되는 비용이 동일하기 때문에
memory가 큰 친구부터 처리하는 것이 이득이다.
따라서 point별로 memory를 저장해놓고 내림차순 정렬한 뒤
prefix sum을 구한다.
그리고 point가 1인 배열에 대해 point가 2인 배열을 탐색하거나
그 반대로 시행하거나
여튼 한 쪽의 prefix sum에 대해 다른 쪽에 lower_bound를 실행하면서
합에 가장 가까울 때 필요한 point를 구하고, 그것들의 최솟값을 구한다.
point는 인덱스를 통해 몇 개의 앱이 삭제됐는지를 확인해 구할 수 있다.
이때 포인트는
*두 배열의 시작 인덱스를 1로 설정*하는거다.
prefix sum으로 문제를 풀 때 많은 경우에서 시작 인덱스를 1로 하긴 하는데,
이 문제를 풀 때는 그럴 필요 있겠어? 라는 생각을 했다.
그런데...정말... 인덱스를 1로 안 한 것 때문에 너무 처리할 게 많았다...
예를 들어서 모든 앱의 point가 1이고, 2인 앱이 없다고 해보자.
각자의 스타일마다 다르겠지만
나는 one, two라는 벡터를 만들고
point에 따라 각각에 push_back()으로 값을 추가하는 방식으로 짰는데
이렇게 하니까 만약 벡터가 비어 있으면
two.back() 이런 식으로 맨 마지막 값을 갖고 오는데 에러가 뜨기 때문에
이런 예외를 처리해줘야 하고...
그리고 또 인덱스를 1부터 시작하면 그 인덱스 번호가 거기까지 더해진 수들의 개수인 반면
0부터 시작하면 (인덱스 번호 + 1)의 값이 해당하는 앱의 개수이다.
이건.. 위에 비하면 별로 번거로운 일은 아니지만
1부터 시작하면 더 깔끔하게 할 수 있으니까...ㅎ
그래서 인덱스가 0부터 시작하는 버전, 1부터 시작하는 버전 모두 짜봤는데
1부터 시작하는 버전에서 주의할 점은
비교대상인 배열을 1이 아니라 0부터 확인해야 한다는 거.
그 포인트의 앱을 하나도 삭제 안 하는 게 최선일수도 있으니까
0부터 확인해야 한다...
흠...
만약 이걸 다른 분이 보게 되면 이해하실 수 있을까...?ㅜ
이해하시면 좋겠다.
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int TC;
cin >> TC;
while (TC--) {
int N;
ll M;
cin >> N >> M;
vector<ll> memory(N + 5);
for (int i = 0; i < N; i++) {
cin >> memory[i];
}
vector<ll> one = { 0 }, two = { 0 };
for (int i = 0; i < N; i++) {
int a; cin >> a;
if (a == 1) {
one.push_back(memory[i]);
}
else {
two.push_back(memory[i]);
}
}
sort(one.begin() + 1, one.end(), greater<>());
for (int i = 1; i < one.size(); i++) one[i] += one[i - 1];
sort(two.begin() + 1, two.end(), greater<>());
for (int i = 1; i < two.size(); i++) two[i] += two[i - 1];
if (one.back() + two.back() < M) {
cout << -1 << ENDL;
continue;
}
int ans = INT_MAX;
for (int i = 0; i < one.size(); i++) {
if (one[i] + two.back() < M) {
continue;
}
int idx = lower_bound(two.begin(), two.end(), M - one[i]) - two.begin();
ans = min(ans, i + 2 * idx);
}
if (ans == INT_MAX) {
cout << -1 << ENDL;
}
else {
cout << ans << ENDL;
}
}
return 0;
}
E.
E는 대회 중에 풀었는데
이것도 그리디한 느낌이다.
무조건 팔로워가 많은 사람을 뽑는 게 이득이다.
그렇다면 경우의 수는 어디서 나오느냐
팔로워 수가 가장 적은 사람이 여러명이라면
그 팔로워 수를 갖는 사람 중 필요한 명수를 고르는 경우의 수를 조합으로 계산하면 된다.
(저 문장에 '수'가 세 번이나 나왔다...
마음에 들진 않지만 특별한 아이디어가 없어서 고치진 않겠다..)
const ll MOD = 1e9 + 7;
vector<vector<ll>> combi;
void Combination(ll N)
{
ll i, j;
combi.resize(N + 1, vector<ll>(N + 1));
for (i = 1; i <= N; i++) {
combi[i][0] = combi[i][i] = 1;
}
for (i = 1; i <= N; i++) {
for (j = 1; j <= i - 1; j++) {
combi[i][j] = combi[i - 1][j] + combi[i - 1][j - 1];
combi[i][j] %= MOD;
}
}
}
int main()
{
Combination(1010);
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int TC;
cin >> TC;
while (TC--) {
int N, K;
cin >> N >> K;
vector<ll> cnt(N + 5, 0);
vector<ll> arr(N + 5);
for (int i = 0; i < N; i++) {
cin >> arr[i];
cnt[arr[i]]++;
}
sort(arr.begin(), arr.begin() + N, greater<>());
int chk = 0;
for (int i = K - 1; i >= 0; i--) {
if (arr[i] == arr[K - 1]) {
chk++;
}
else {
break;
}
}
cout << combi[cnt[arr[K - 1]]][chk] << ENDL;
}
return 0;
}
오늘 또 코포가 있는데
잘 하면 좋겠다
ㅎㅎ