본문 바로가기

분류 전체보기

 (20)
IOI 2020 Day 1 풀이 2020.09.19 - A는 준비중이며, B와 C의 풀이를 작성했습니다. 나는 5시간을 잡고 셋을 돌았고, 5 / 100 / 41점으로 총 146점을 받았다. C번 문제는 연습이 끝나고 한 30분 정도 더 고민해서 해결할 수 있었다. A. 식물 비교 Subtask 1 (5점) 어떤 수와 직후에 있는 수의 대소관계가 주어진다고 생각하면 된다. 그러면, 전체 $n$개의 수들을 시계방향으로 볼 때 수들의 대소관계 (증가/감소)가 일정한 구간들로 나누어서 볼 수 있고, 두 수가 비교 가능할 필요 충분 조건은 증감 상태가 같은 연속된 구간에 포함됨을 관찰할 수 있다. 따라서, 증감의 상태가 바뀌는 구간 개수의 prefix sum을 계산해놓으면, 쿼리당 $O(1)$에 처리할 수 있다. Subtask 2 (14점) ..
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을 맡..
공상 어린 시절부터 나는 여유로운 시간에 멍 때리며 공상하는 것을 굉장히 좋아한다. 멍 때리며 공상하면 현실에 구애받지 않고 자유롭게 생각하고 상상할 수 있기 때문이다. 그간 멍 때리며 한 공상 중 기억에 남는 것을 블로그에 기록해두고자 한다. 이 글은 나의 허무한 생각을 기록한 가장 첫 글이 될 것이다. 초등학생 때 학교 수업시간에 멍때리며 했던 생각 하나가 아직도 기억에 남아있다. 인간처럼 생각하는 기계를 만들 수 있을지에 대한 것이었다. 당시 나름 열심히 고민해봤는데, 생각이란 무엇인지 부터 정의해야 한다는 결론에 다다랐고, 결국 생각이란 무엇인지를 열심히 고민해봤었다. 여기에서 다음과 같은 질문에 다다랐다. Q. 인간이 하는 생각(혹은 인간이 꾸는 꿈)은 반드시 인간의 언어로 표현될 수 있는가? 만일 ..
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..
최대 부분합과 쿼리 최대 부분합 문제를 $O(n)$에 푸는 것은 쉬운 일이다. 하지만, 배열을 업데이트 하는 질의가 주어진다면, 이는 쉬운 일이 아니다. 이와 관련한 문제가 근 몇 년간 여러 대회에 출제되었으며, 신기하게도 한국인들 사이에서는 유독 잘 알려져 있는 테크닉이다. 이 글에서는 다음 두 가지 쿼리를 $O(n \log n)$ 전처리 후 쿼리당 $O(\log n)$에 처리하는 방법을 제시한다. update(i, value) - 배열의 i번째 index의 값을 value로 업데이트한다 maxsum(left, right) - [left, right] 범위의 최대 부분합을 반환한다 기본적으로, 세그먼트 트리를 응용하여 문제를 해결한다. 세그먼트 트리의 노드를 다음과 같이 정의해주자. struct Node{ int left..
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..
나의 zsh 및 Vim 세팅 내가 사용하는 Mac(들)에다 하는 세팅.. 어딘가 기록해두고 싶어 기록해둔다. 1) oh-my-zsh 등 설치 brew install wget vim zsh tmux git clone https://github.com/VundleVim/Vundle.vim.git ~/.vim/bundle/Vundle.vim cp .vimrc ~/ vim +PluginInstall +qall sh -c "$(wget https://raw.githubusercontent.com/robbyrussell/oh-my-zsh/master/tools/install.sh -O -)" git clone https://github.com/zdharma/fast-syntax-highlighting.git ~/.oh-my-zsh/custom..