본문 바로가기

Computer Science

(20)
제2회 UNIST 알고리즘 프로그래밍 경진대회 Uni-CODE 2020 이번에 UNIST 알고리즘 프로그래밍 경진대회에 3문제를 출제했다. 출제와 검수의 전 과정을 도울 수 있어서 기뻤고, 좋은 경험이었던 것 같다. 간단한 풀이는 아래와 같고, 문제 채점은 다음 링크에서 할 수 있다. https://acmicpc.net/category/detail/2353 A. 트리플 소트 출제: queued_q 문제에서 주어진 swap 연산으로는 기우성이 같은 인덱스 끼리만 바꿀 수 있음을 알 수 있다. 고로, 홀수 번째 인덱스와 짝수 번째 인덱스를 별개로 생각해볼 수 있다. 버블 소트를 생각해보면, 인접한 인덱스의 스왑 연산으로는 모든 배열을 정렬할 수 있음을 알 수 있다. 따라서, 홀수 번째 인덱스에는 홀수만, 짝수 번째 인덱스에는 짝수만 있는 것이 정렬 가능할 필요충분조건임을 알 수..
SCPC 2020 짧은 후기 1차 예선 SCPC 1차 예선은 무난하게 통과했던 것 같아서 별 기억이 없습니다. 100 / 150 / 150 / 39 / 0을 받았습니다. 2차 예선 SCPC 2차 예선은 건강검진 예약일과 겹쳐서 많은 시간을 투자하지는 못했습니다. C번 문제가 풀이 자체는 쉬우나, 상수가 큰 풀이는 통과하지 못하는 빡빡한 제한이라 해결하지 못했던 점이 아쉬웠습니다. 100 / 150 / 61 / 41 / 47을 받았습니다. 본선 본선에 갈 것이라고 생각하지 못했지만, 본선에 참가하게 되었습니다. 본선 문제를 보니 생각보다 어려워 보여서, 점수만 열심히 긁어도 상은 받을 수 있다고 생각했습니다. 1번 문제는 쉬워서 간단히 100점을 받았습니다. 2번 문제는 지문이 더러워서 뭐 하라는건지 한참을 고민했는데, 결국 SCC를..
ICPC 2020 Seoul Regional 후기 이채준, 신민철 님과 함께 참가한 대학생 프로그래밍 경시대회에서 8솔브 / 1303분으로 전체 10등을 했고, 학내에서는 2등을 했다. 좋았던 점과 아쉬운 점 모두 있지만, 팀원들에게 수고했다는 말을 해주고 싶고, 우리 팀에 미래가 있다는 사실을 확인했다는 점이 너무나 좋았다. 사실 우리 팀은 인터넷 예선을 앞두고 팀 연습 1번, 인터넷 예선 이후에 팀 연습을 아예 안 할 정도로 별 준비 없이 봤음에도 불구하고, 전체 팀들 가운데 10등을 차지한 것은 사실 꽤나 잘한 성과라고 생각한다. 하지만, 인터넷 예선에서 운 좋게 8등을 한 덕택에 (객관적 실력상 진출이 힘듬이 명백한) 세계 대회에 갈 수 있다는 행복 회로를 돌리던 것은 썩 좋게 작용하지만은 않은 것 같다. 아무튼, 별 준비 없이 전체 10등은 나..
2020 천하제일 코딩대회 예선 또 인연이 닿아 선린인터넷고등학교의 천하제일 코딩대회 예선 및 본선을 출제하게 되었다. 출제는 junie님, wookje님과 함께 했으며, 서버 관리는 감사하게도 suckzo_o 님께서 맡아주셨다. (감사합니다) 예선은 junie 님이 2문제, 내가 2문제를 만들었다. 본선 팀을 선발하기 위한 대회인 만큼, 비교적 쉬운 문제들 위주로 구성하였다. 백준 온라인 저지에는 추후에업로드 할 예정이다. 간단한 풀이는 다음과 같다. A. 세금 출제: leejseo 정수 연산만을 이용해서 해결할 수 있도록 입력이 주어진다. $N / 1000 \times 780$ 와 $N / 1000 \times 956$을 사이에 공백을 두고 출력하면 된다. 오버플로우가 날 수 있는 입력 데이터를 준비해서 넣었다. 이 문제를 만든 ..
Minimums on the Edges 풀이 최근에 푼 문제 중 가장 재미있는 것 같아서 풀이를 기록해둔다. Link: www.acmicpc.net/problem/18664 18664번: Minimums on the Edges Print n numbers a1, a2, . . . , an (0 ≤ ai ≤ s), where ai is the number of tokens you put on the i-th vertex. The sum of printed integers must be equal to s. The sum of capacities of all edges must be the maximum possible. If there are multiple optimal www.acmicpc.net $N$개의 정점이 있고, $M$개의 간선 $(u_..
ICPC 2020 Seoul Regional 예선 후기 8솔브 / 563분 으로 전체 8등을 했고, 학내에서는 1등을 했다! (5등 팀은 휴학생 팀이기 때문이다.) 대회를 치기 전 사실 대회를 치기 전에 걱정이 많았다. 대충 아래와 같다. 다른 팀들은 모든 팀원이 최소 오렌지인데, 우리 팀은 내가 퍼플이다. 같은 학교 팀들 중 절반 이내에 들어야 리저널에 가는데, 이번에 대회가 온라인으로 개최되면서 웬만큼 PS에 관심 있는 팀이 아니면 참가 신청을 하지 않았다. 팀원 모두가 각자 할 일이 있어서 팀연습을 한 번 밖에 못했다. (교내대회 포함하면 두 번) 내가 최근에 수면에 있어 큰 어려움을 겪어서 컨디션이 굉장히 안좋았다. 그럼에도 불구하고 우리 팀이 잘 칠 수 있다는 근거 있는 자신감도 있었다. 전날 친 KAIST 교내 대회에서 8솔브 / 6등을 했고, 위..
2020 선린 정보 알고리즘경시대회 올해 선린인터넷고등학교의 교내 정보경시대회를 출제하게 되었다. 출제는 김준원님, 권욱제님과 함께 했으며, 정종인님이 서버 관리를 맡아주셨다. 일정이 워낙 촉박해서 대회 진행에 있어 다소 아쉬운 점이 있었으나, 문제 자체의 질은 괜찮다고 생각한다. 간단한 문제 해설과 함께 본인이 출제한 문제에 대해서는 출제 의도, 본인이 출제하지 않은 문제에 대해서는 출제 의도가 아닌 예상 난이도를 적어둔다. 문제는 BOJ에서 해결할 수 있다. 문제 풀이 A. 헛간 청약 출제: wookje 예상 난이도: Bronze IV - Bronze III 정답이 최대 $N$임에 유의하여 해결하면 된다. $\lfloor W/L \rfloor \times \lfloor H/L \rfloor$가 가장 많이 등장한 오답 중 하나였다. B...
UCPC 2020 참가 후기 팀 구성 RUN(KAIST의 알고리즘 동아리) 슬랙에서 UCPC 팀을 구하는 채널이 생겼고, 온라인으로 알던 분 두 분이 팀원을 구한다고 해서 같이 팀을 구성하게 되었다. 팀원은 Juney와 minfe였다. 예선 그럭저럭 무난히 풀었다. I번은 쉽지만 재밌는 문제라 Appendix에 풀이를 간략히 적어둘듯 하다. 7솔브/2446min.으로 24등을 하며 무난히 본선에 진출했다. 사진은 예선 대회 치는 우리의 모습 본선 첫 팀대회 본선이라 설렘도 있었고, 그와 동시에 부담감과 두려움도 있었다. 어찌되든 그 또한 경험이라 생각하며 마음을 비우고 대회를 쳤다. 타임라인 0 min. 대회가 시작하고, 팀원들이 각자 문제를 배분해서 보기 시작했다. minfe님이 A~D, Juney 님이 E~H, 내가 I~L을 맡..
2020 UCPC 예선 대비 개인 연습 (3) UCPC 2018 예선 굳이 풀이를 적지 않은 문제 중 A, B, F (+ J?) 정도는 현재의 내가 별 다른 무리 없이 해결 가능하다고 생각한다. (J의 경우는 대회 때 제출이 불가능해진 이후에 그럴싸한 선형 풀이를 찾았던지라, 내 답이 맞는지 모르지만..) 문제 풀이 문제 링크 C. 대회 형섭이의 최적 전략이 EDF(earlist deadline first) 형태의 그리디 전략임을 알 수 있다. 형섭이의 전략이 고정되어 있으므로, 다른 참가자들의 전략을 simulation해주면 되는데, 이 또한 형섭이의 전략과 유사하다. 대회들을 종료 시점이 빠른 순으로 정렬하고, 하나씩 보되, 형섭이가 참여 중인 대회와 시간대가 겹치면 건너뛰고, 해당 대회에 참여할 수 있는 형섭이가 아닌 참가자가 있다면, 그 중 ..
2020 UCPC 예선 대비 개인 연습 (2) AtCoder Beginner Contest 171 문제 풀이 문제 링크 D. Replacing $A$의 원소들의 합을 관리하는 배열과 $X[x]$ := ($A$에 $x$가 등장하는 횟수) 로 정의된 배열 $X$를 잘 관리해주면 된다. #include using namespace std; typedef long long ll; int N, Q; ll X[100005]; int main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cin >> N; ll sum = 0; for (int i=0; i> x; X[x]++; sum += x; } cin >> Q; while (Q--){ int b, c; cin >> b >> c; sum -= b * X[b];..