본문 바로가기
반응형

프로그래밍 대회 풀이

SCPC 2021 Round 2 후기 본선 한번 가보고 싶어서 12시간 거의 다 써서 참여했다. 작년 2라운드 0점의 성적보단 낫지만, 본선가기엔 턱없이 부족한 결과다. 아무리 생각해도 PS 실력이 너무나 애매한 수준인 것 같다.... 점점 퇴보하고 있는걸지도..? 우선 문제 자체도 어려웠다. 2번 문제는 초반에 페널티 신경쓰지 않고 막 제출하다가 어느 순간 1번의 기회만 남아버려서 잠시 미뤘는데, 나중에 다시 봤을 땐 풀이가 떠올랐지만 구현 실수인지 1틀을 더해버려서 제출을 더 못했다.... 무조건 풀었어야 하는 문제인데.. 3번 문제에만 거의 6~7시간은 쏟아부은 것 같다. 풀이를 들으니 문제가 너무 극혐이다... 4번 문제는 일단 완탐으로 4-1 테케만 긁고 3번에 올인했는데, 4-2 테케가 생각보다 할만했나보다. 아쉬움이 많이 남는 ..
SCPC 2021 Round 1 후기 SCPC 2021 Round 1에 참가하였다. 문제 풀이는 너무 많은 다른 고수들이 작성해두어서 굳이 작성하진 않겠다. 시프트님이 풀이를 아주 잘 써두셔서 참고하면 도움이 될 것 같다. https://blog.shift.moe/2021/07/17/scpc-2021-round-1/ SCPC 2021 1차 예선에 참가했습니다 (1/3) – Shifted 1차 예선 — 800/800 올해는 예년보다 문제들이 쉬워진 느낌이었습니다. 다섯 문제를 전부 풀었습니다. 제 풀이를 공유합니다. 1차 1번 – 친구들 사람이 $N \leq 100\,000$명 있습니다. 번호 $i$인 사람 blog.shift.moe 이번 대회는 개인적으로 1년간 얼마나 많이 발전했는가를 시험해볼 수 있는 대회이다. 그 이유는, 작년 SCPC..
Atcoder Beginner Contest 206 (ABC 206) 풀이 A. Maxi-Buying 단순 계산 문제이다. N을 입력받고, 1.08*N을 정수단위로 올림 했을 때 206과 대소 비교하는 문제이다. #include using namespace std; int main(void) { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); double n; cin >> n; n *= 1.08; int ans = (int)n; if (ans == 206) cout = n) { cout > n; map mp; for (int i = 0; i > a; mp[a]++; } ll ans = 0; for (auto [a, b] : mp) { ans += 1LL * b * (..
Atcoder Beginner Contest 205 (ABC 205) 풀이 오랜만에 참가한 ABC인데, 마침 오랜만에 ABC 문제들이 괜찮아서 풀이를 작성해보려고 한다. 결과도 나쁘지 않았다. 문제 링크 : https://atcoder.jp/contests/abc205/tasks 공식 해설 : https://atcoder.jp/contests/abc205/editorial (*) = 난이도 A. Kcal (*6) 단순 계산 문제이다. 100ml당 A kcal을 얻을 수 있을 때 Bml이 있으면 몇 kcal를 얻을 수 있는지를 구하면 된다. #include using namespace std; int main(void) { ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); double a, b; cin >> a ..
Google Kickstart Round A 2021 풀이 Rank = 861 (KR 37) 1. K-Goodness String (12 pts) 길이가 N인 문자열 S가 주어지고, 각 글자를 원하는 만큼 변경할 수 있다. 1≤i≤N/2 인 i에 대해서 S[i] != S[N-i+1]인 i의 개수가 K가 되기 위한 최소 변경 횟수를 구하는 문제이다. 단순 구현 문제이다. S[i]나 S[N-i+1] 둘 중 하나를 바꾼다면 상태를 바꿀 수 있으니 처음 문자열에서 S[i] != S[N-i+1]인 i의 개수를 구한 다음 K와의 차이만큼 문자를 바꿔주면 된다. (멍청하게도 S[i] == S[N-i+1]이면 점수를 얻는다고 생각해서 1WA를 받았다. 왜 하필 예제 답이 같아서...) [소스 코드] #include using namespace std; int main(void..
[Codeforces] Round #709 (div. 2) A ~ D 풀이 2021.03.21 22:20 ~ 00:35 본 라운드 참여 (performance = 1844) 테크노컵은 뭔가 항상 어려운 느낌이다... 생각보다 퍼포먼스가 나쁘지 않게는 나왔는데, 개인적으로 요즘 코포 폼이 조금 올라왔다고 생각해서 더 아쉬운 기분이 든다. A. Prison Break (*800) 모든 칸들에서 밖으로 나갈 수 있기 위해서 제거해야 하는 벽의 수의 최소를 구하는 문제이다. 답은 가로 * 세로, 즉 칸의 개수이고 대회중에는 직관적으로 빠르게 해결했다. 정확한지는 모르겠으나 증명을 하자면, 각 칸마다 해당 칸에서 시작해서 밖으로 나갈 수 있는지 없는지를 상태로 표현하고, 벽이 제거된 이웃한 칸은 하나의 칸으로 합쳐진다고 생각하자. 벽을 하나 제거했을 때 밖으로 나갈 수 없었던 2개 이상..
[Codeforces] Round #706 (Div. 2) A ~ D 풀이 2021. 03. 10 21:05 ~ 23:05 참가 / performance = 1849 애드혹 범벅이었던 라운드.... D가 안터졌으면 2100 performance까지 나올 수 있었는데 아쉽다. (D 시스페일이 엄청 많았다) 다행히 C까지 빠르게 풀어서 레이팅이 하락하지는 않았다. A. Split it! 문자열을 2k + 1 개로 쪼갤 때, 앞의 k개와 뒤의 k개는 각각 서로 reverse된 형태로 나타낼 수 있는지에 대한 문제이다. 양끝에서부터 s[i]와 s[n-1-i]가 같은 최대 길이를 구하고, 이 길이가 k 이상이면 조건을 만족할 수 있다. k보다 크다면 남는 부분은 $a_{k+1}$에 모두 포함시켜주면 된다. 주의해야할 점은, 2k + 1이 n보다 큰 경우에는 애초에 2k+1개로 쪼갤 수 ..
[Codeforces] Round #705 (Div. 2) A ~ D 풀이 21.03.06 23:05 Round #705 참가 (Rating 1740 -> 1855 / Performance = 2137) 대회 시간도 2시간 15분이고, 세터의 예전 라운드도 어려운 난이도였고, 점수 분포를 보고도 대충 어려울 거라고 예상은 했지만, C부터 이렇게 어려울 줄이야.... 대회 때 C, D 솔브수가 1000명이 안되었다. 2시간이 아니어서 다행히 D까지 풀 수 있었다. A. Anti-knapsack (*800) n과 k가 주어질 때, {1, 2, ..., n}의 부분집합 중에서, 합이 k가 되도록 원소 일부를 고를 수 없는 최대 부분집합을 구하는 문제이다. 일단, k+1 ~ n까지는 항상 포함시켜도 된다. 그리고, (k-1, 1) , (k-2, 2) ... 등의 쌍이 둘을 더하면 k가..

티스토리툴바