Codeforces Round #762 (Div. 3) 1562 -> 1607
Dashboard - Codeforces Round #762 (Div. 3) - Codeforces
Dashboard - Codeforces Round #762 (Div. 3) - Codeforces
codeforces.com
!!!! 모든 답은 제 풀이일 뿐 정해가 아닐 수 있습니다 !!!!
A. Square String?
Problem - A - Codeforces
codeforces.com
문제
문자열이 주어졌을 때 , 두번 연속 반복된 문자열인지 출력하는 문제
풀이
홀수면 NO로 처리하고, 짝수면 절반씩 따로 골라서 두 개의 스트링이 같은지 판별한다.
코드
#include <bits/stdc++.h>
using namespace std;
string s;
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int T;
cin >> T;
while (T--) {
cin >> s;
if (s.size() % 2) {
cout << "NO\n";
continue;
}
int n2 = s.size() / 2;
string s1 = "", s2 = "";
for (int i = 0; i < n2; i++)s1 += s[i];
for (int i = n2; i < s.size(); i++)s2 += s[i];
if (s1 == s2)cout << "YES\n";
else cout << "NO\n";
}
}
B. Squares and Cubes
Problem - B - Codeforces
codeforces.com
문제
n이 주어졌을때 n이하의 제곱수, 세제곱수가 몇개인지 출력하는문제
풀이
i*i <= n 인것과 i*i*i <=n인것을 bruteforce로 센다. 다만 중복검사는 map으로 검사한다.
코드
#include <bits/stdc++.h>
using namespace std;
string s;
map<long long,bool> Map;
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int T;
cin >> T;
while (T--) {
Map.clear();
long long n;
cin >> n;
long long ans = 0;
for (long long i = 1; i * i <= n; i++) {
if (Map[i * i] == false) {
ans++;
Map[i * i] = true;
}
}
for (long long i = 1; i * i*i <= n; i++) {
if (Map[i * i*i] == false) {
ans++;
Map[i * i*i] = true;
}
}
cout << ans << '\n';
}
}C. Wrong Addition
Problem - C - Codeforces
codeforces.com
문제
두 수 a+b를 캐리연산을 안하고 더한 결과값 c와 a가 주어졌을 때 b를 출력하는 문제
풀이
끝자리에서부터 하나씩 구한다. 만약 a의 끝자리 > c의 끝자리라면 10을 한개 더 빼와서 c끝자리-a끝자리를 계산해주고 , 이외에는 똑같이 c끝자리-a끝자리를 계산해주고 10이나 100을 나눠주면서 처리한다. 이 때 c만 숫자가 남으면 그대로 나머지 b에 더해주면 된다.
코드
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int T;
cin >> T;
while (T--) {
long long a, b;
cin >> a >> b;
bool flag = true;
string ans = "";
while (true) {
int alast = a % 10, blast = b % 10;
if (alast <= blast) {
ans += (blast - alast) + '0';
a /= 10;
b /= 10;
}
else {
blast = b % 100;
if ((blast / 10) != 1) {
flag = false;
break;
}
ans += (blast - alast) + '0';
a /= 10;
b /= 100;
}
if (a == 0 || b == 0)break;
}
if (a) {
flag = false;
}
if (b) {
while (b) {
ans += (b % 10) + '0';
b /= 10;
}
}
if (flag) {
reverse(ans.begin(), ans.end());
long long ans2 = stoll(ans);
cout << ans2 << '\n';
}
else {
cout << "-1\n";
}
}
}E. MEX and Increments
Problem - E - Codeforces
codeforces.com
문제
n길이의 배열이 주어졌을 때 한 번의 연산에 인덱스 j를 하나 골라 a[j]+=1 을 하는 연산을 할 수 있다. 이때 i ( 0~N ) 에 대하여 이 배열의 MEX값이 i가 되게하는 최소 연산의 수를 출력하는 문제, 다만 MEX가 i가 되게 할 수 없을 때는 -1을 출력한다.
풀이
각 숫자마다 count를 세고, 만약 1개 초과라면 맥스힙에 숫자와 갯수를 추가하고, 빈 공간이 생길 때 마다 1개씩 뺴서 채워주는 식으로 한다. 만약 MEX를 i로 만들어 줘야 하는데 i의 갯수가 여러개라면 그 숫자를 그대로 출력하고, 빈 공간이라면 미리 해둔 계산식 + i갯수로 출력해주면 된다.
코드
#include <bits/stdc++.h>
using namespace std;
long long a[200001];
long long cnt[200001];
priority_queue<pair<long long, int>> pq;
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
int T;
cin >> T;
while (T--) {
int n;
cin >> n;
for (int i = 1; i <= n; i++) {
cin >> a[i];
cnt[a[i]]++;
}
long long ans = 0;
bool flag = false;
for (int i = 0; i <= n; i++) {
if (flag) {
cout << -1 << ' ';
continue;
}
if (cnt[i] > 0) {
cout << ans + cnt[i] << ' ';
if (cnt[i] > 1)pq.push({ i,cnt[i] - 1 });
}
else {
cout << ans << ' ';
//메꿔줄게 없다면
if (pq.empty())flag = true;
else {
auto now = pq.top();
pq.pop();
now.second--;
ans += (i - now.first);
if (now.second > 0)pq.push(now);
}
}
}
cout << '\n';
while (!pq.empty())pq.pop();
for (int i = 1; i <= n; i++) {
cnt[a[i]] = 0;
}
}
}
자세한 설명에 중점을 두기보다는 대회 기록에 중점을 둔 글입니다 !
틀린 부분은 감사히 지적받겠습니다.