본문 바로가기

Computer Science/Competition

 (14)
제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등은 나..
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];..
2020 UCPC 예선 대비 개인 연습 (1) 요 근래 UCPC 예선 대비로 개인연습을 진행중이다. 참고로 대회에는 Juney 님과 minfe 님과 함께 나갈 예정이다. 휴학한 나 이외에는 기말고사를 쳐야 하는지라, 일단 개인연습을 돌고 있다. solved.ac의 기능을 이용하여 난이도가 플래티넘 V ~ 플래티넘 I 범위에 속하는 문제 12개를 골라 셋을 만들고, 한 1주일 정도의 기간 동안 그 중 6개 이상 해결하는걸 목표로 하고 있다. 요지는 대회 시간 안에 풀이를 생각해낼 수 있을만한 문제들을 풀되, 특정 성향의 문제에 편중되지 않게 풀어보자는 것이다. solved.ac 플래티넘 연습 #01 문제 목록 A - Counting Friends B - 고속도로 C - 인재야 머쉬맘 잡았어? D - Random Number Generator E - K..
2019 ICPC 한국 리저널 인터넷예선 풀이 Note: 아직 미 완성인 글입니다. 20.06.03: A, B, C, D, F, H, I, J, L 풀이 수록 문제는 다음 사이트에서 일부 해결해볼 수 있다: 링크 A. All You Need is Dating $i$번째 IC 학생이 원하는 데이트의 최소 횟수를 $minIC_i$, 최대 횟수를 $maxIC_i$로 표기하자. 비슷하게 $minPC_j$와 $maxPC_j$를 정의하자. 그러면, 이 문제는 아래와 같이 간선을 지나가는 유량의 최소 제한과 최대 제한이 있는 플로우 그래프로 모델링 가능하다. 이는 전형적인 LR-flow 문제로, 해결법이 널리 알려져 있다. 일반적인 네트워크 플로우 알고리즘을 사용하여 해결하는 방법과 MCMF를 활용하는 방법이 있는데, 이 글에서는 생략한다. B. Balanced..

티스토리툴바