Dashboard - Codeforces Round #560 (Div. 3) - Codeforces
codeforces.com
학회 코포 스터디에서 버추얼을 돌았다
너무 오랜만의 코포/PS라서 어색했다
결과도 별로 좋지 않다
A.
편하게 생각할 수 있도록 string을 뒤집었다.
문자열 변수를 s라고 할 때
ans += s[0] ~ s[x-1] 중 1의 개수
s[x]가 0이면 ans++
ans += s[x+1] ~ s[y-1] 중 1의 개수
한 뒤 ans를 출력하면 된다
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n, y, x;
cin >> n >> y >> x;
string s; cin >> s;
reverse(s.begin(), s.end());
int ans = 0;
for (int i = 0; i < x; i++) {
if (s[i] == '1') ans++;
}
if (s[x] == '0')ans++;
for (int i = x + 1; i < y; i++) {
if (s[i] == '1') ans++;
}
cout << ans;
return 0;
}
B.
문제를 이해하는 데 시간이 많이 걸렸다.
정리하자면 1부터 k까지의 수 각각에 대해 그 수 이하의 값과 배열 값과 매치할 때
가능한 최대 k는 얼마인지 구하는거다.
배열을 오름차순으로 정렬한 뒤
i < n인 동안 k를 1부터 확인하면서
만약 현재 비교중인 배열 값이 k 이하이면 k++, i++
만약 그렇지 않으면 i++만 해준다.
그렇게 시행한 후에 k - 1이 답이다.
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n; cin >> n;
vector<int> arr(n);
for (int i = 0; i < n; i++) {
cin >> arr[i];
}
sort(arr.begin(), arr.end());
int k = 1;
for (int i = 0; i < n; ) {
if (k > arr[i]) {
i++;
continue;
}
else {
k++;
i++;
}
}
cout << k - 1 << ENDL;
return 0;
}
C.
이것도 풀이를 생각하는 데 조금 헤맸는데
현재 배열에서 확인중인 인덱스 i, 그리고 그 다음 인덱스 i2로 두고
i = 0부터 시작하면서 s[i] == s[i2]이면 i2++
두 값이 다르면 정답 문자열에 s[i], s[i2] 모두 넣고 i = i2+1, i2++로 업데이트 해줬다.
그리고 다 진행한 후 문자열의 맨 끝 문자를 놓쳤다면 현재 길이가 홀수일때 그걸 추가해줬다.
그런데 이렇게 할 필요가 없다.
버추얼 끝나고 풀이를 공유했는데
답을 문자열 벡터 ans에 저장할 때
만약 그 벡터의 크기가 짝수면 지금 확인중인 문자를 그냥 추가하면 되고
홀수면 ans의 마지막 문자와 다른 문자이면 추가한다.
연속적으로 같은 문자가 나올 때 개수가 최소가 되야 하기 때문에
문자를 빼는 위치와는 관계 없다.
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int n; cin >> n;
string s; cin >> s;
vector<char> ans;
int cnt = 0;
for (int i = 0; i < n; i++) {
if (ans.size() % 2 == 0) {
ans.push_back(s[i]);
}
else {
if (ans.back() != s[i]) {
ans.push_back(s[i]);
}
}
}
if (ans.size() % 2 == 1) {
ans.pop_back();
}
cout << n - ans.size() << ENDL;
for (char c : ans) cout << c;
return 0;
}
D.
맞왜틀이 시작되었다.
처음에는 x만 출력하면 되는 줄 알고 배열을 정렬한 후 arr[0] * arr[n-1]을 출력했다.
다시 문제를 읽어보니까 잘못된 배열일 경우 -1을 출력하라고 해서
ans = arr[0] * arr[n-1]로 두고
ans != arr[i] * arr[n-1-i]인 경우가 있으면 ans = -1로 업데이트했다.
그런데 계속 틀렸다.
더 심각한 건 끝까지 왜 틀렸는지 못 찾았다는거다.
버추얼 끝나고 풀이를 듣고 나서도 왜 내가 틀렸는지를 못 찾았다.
1, x를 제외한 모든 약수가 list에 있어야 한다는 점을 놓쳤다.
그래서 풀이 하실 때 ans = arr[0] * arr[n-1]의 약수를 모두 구하고
그것을 입력된 배열과 비교해서 동일하면 ans가 답, 그렇지 않으면 -1이 답인거다.
풀이를 듣고도 이걸 찾아내지 못했다는 게 좀 충격이다.
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int tc; cin >> tc;
while (tc--) {
int n; cin >> n;
vector<ll> arr(n);
for (int i = 0; i < n; i++) cin >> arr[i];
sort(arr.begin(), arr.end());
ll ans = arr[0] * arr[n - 1];
vector<ll> next;
for (ll i = 2; i * i <= ans; i++) {
if (ans % i == 0) {
next.push_back(i);
if (i * i != ans) next.push_back(ans / i);
}
}
sort(next.begin(), next.end());
if (next == arr) {
cout << ans << ENDL;
}
else {
cout << -1 << ENDL;
}
}
return 0;
}
E.
D를 계속 틀려서 E로 넘어왔는데 E도 맞왜틀을 반복하다가 끝까지 못 풀었다.
a의 원소들은 그대로 두고 b의 원소들만 옮길 수 있다.
그리고 답은 a[i]*b[i]*i*(n-i+1) 값들의 합이 된다.
여기서 a[i]*i*(n-i+1)은 고정된 값이기 때문에
이것들을 먼저 계산해놓고
그 결과 가장 작은 값들부터 b 중 큰 값들과 매치시켜 곱하고 모두 더한 게 답이 된다.
내가 틀렸던 이유는
a[i] * i * (n-i+1) 값을 계산한 후 나머지를 구해 저장해놨던 거 때문이다.
나머지 값이 아니라 저 값을 기준으로 내림차순 정렬해야 한다.
문제에
Note that you should minimize the answer but not its remainder.
라고 적혀 있는걸 보고 굳이 이런 걸 왜 언급하나 의아했는데
다 이유가 있었던거다...
이런 비슷한 경험을 예전에도 했었는데
BOJ 14698 전생했더니 슬라임 연구자가 된 건에 대하여
이 문제에서도 무작정 나머지 연산을 해서 몇 번이나 틀렸었다..
풀이 듣고 그 부분을 수정하니까 바로 맞았다.
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
ll n; cin >> n;
vector<ll> a(n), b(n);
for (ll i = 0; i < n; i++) {
cin >> a[i];
a[i] *= (i + 1) * (n - (i + 1) + 1);
}
for (int i = 0; i < n; i++) {
cin >> b[i];
}
sort(a.begin(), a.end());
sort(b.begin(), b.end(), greater<>());
ll ans = 0;
for (int i = 0; i < n; i++) {
a[i] %= MOD; b[i] %= MOD;
a[i] *= b[i];
ans += a[i];
ans %= MOD;
}
cout << ans << ENDL;
return 0;
}