구사과

(2018.01.17 : 일이 바빠서 잊고 있다가 1월 17일에야 모든 연습의 풀이를 공개할 수 있었습니다. 여전히 풀이가 준비되지 않은 문제들이 있는데 꼭 풀이를 쓰도록 하겠습니다..) 동아리 내부에서 방학 BOJ 연습에 대한 수요가 있어서, 여름방학 동안 BOJ RUN@KAIST 그룹에서 (비공개 그룹이다.) 방학 연습을 진행했습니다.연습 까먹고 안 열기, 제멋대로 널뛰기하는 문제 난이도, 잘못된 디스크립션과 시간 제한, 제때 올라오는 일이 없는 연습 풀이 등.. 이슈가 너무 많았습니다. 사실 방학 내내 문제 세팅 노예여서 방학 연습 외에도 여기저기 문제 세팅을 하고 있느라 시간을 많이 할애할 수 없었습니다. 그래도 8월에 여유가 생겨서, 이슈도 줄고 풀이 쓰는 속도가 밀리는 속도보다 빨라졌네요.이런..

1. Lazy Spelling Bee각각의 스텝에서 선택할 수 있는 문자의 개수는 최대 3가지다. 이 중 서로 다른 문자의 개수가 우리가 이번에 택할 수 있는 경우의 수다. 문제를 풀 때는, 스텝을 순서대로 처리한다. 각 스텝마다 선택할 수 있는 서로 다른 문자의 개수를 계산한 후, 이 문자의 개수를 경우의 수에 곱해주면 된다. 2. Sums of Sums쿼리 개수가 많지 않으니 각각의 쿼리를 독립적으로 보자. 일단. 구간 $[L, R]$ 에 있는 수의 합를 계산한다고 하면 복잡하니, 구간 $[1, R]$ 에 있는 수의 합을 계산하고, $[1, L-1]$에 있는 수의 합으로 빼주는 것이 생각하기 편하다. 고로, 구간 $[1, X]$ 에 있는 부분 합들의 sum을 계산하는 문제를 풀면 된다.$X$번째까지의..

1. 공간을 만들어 봅시다미팅 공간을 잡는다는 것은, 미팅 공간의 왼쪽과 오른쪽 경계 파티션을 잡는다는 것이다. 0과 W를 포함한 모든 파티션의 쌍을 돌면서, 해당 파티션 쌍 사이에 생기는 공간의 크기는, 가능한 미팅 공간 크기라고 체크하면 된다. 2. Unique Encryption Keys어떠한 구간에 대해서 수들이 다 unique하다는 것은, 그 수와 같은 값을 가지는 수들이 (자신을 제외하고는) 해당 구간에 존재하지 않는다는 것을 뜻한다. 구간 $[S, E]$에 있는 수가 unique한지를 보려면, 그 수와 가장 가까운 두 수 (왼쪽 / 오른쪽) 을 본 후, 이것이 $[S, E]$ 구간 안에 있는지를 보면 된다. 이 풀이를 조금 더 정리하면 다음과 같다. $prev[i]$ 를 $i$의 왼쪽에 있으..

A. 약 팔기 1000000=1000*1000이므로, 1을 1000개, 1000을 1000개 나열하면 된다. 1

먼저 “Alice가 답을 TT 이상으로 하는 게임을 진행할 수 있는가, 없는가?” 라는 변형된 문제를 풀어보자. 변형된 문제를 빠른 시간 안에 풀 수 있다면, 이분 탐색을 통해서 Alice가 진행할 수 있는 게임 중 TT가 가장 큰 것을 찾을 수 있고, 이것이 Alice가 얻을 수 있는 최댓값이기 때문이다.이후부터는 문제를 그래프로 변형해서 해결한다. ∣Au−Av∣ 3이고 짝수인 경우에는, Bob이 정점을 지운다. ⌈n/2⌉=⌈(n−1)/2⌉\lceil n/2 \rceil = \lceil (n-1)/2 \rceil 이기 때문에 어떤 정점을 지우더라도 귀납 가정을 만족해서 Alice가 이긴다.n>3이고 홀수인 경우에는, Alice가 이번 턴을 진행한다. 만약에 최대 클리크의 크기가 ⌈n/2⌉\lceil n..

방향 그래프의 Dominator Tree의 유래, 개념에 대해서 짤막한 글을 써보았습니다.Dominator Tree를 빠르게 구하는 알고리즘에 대한 언급은 없습니다. Dominator Tree를 빠르게 구하는 알고리즘은, 그 증명 방법과 내용이 상당히 길고 복잡하기 때문입니다. 개인적인 생각으로는 그 부분까지 이해할 필요는 없고, 구현체만 팀노트에 넣어도 문제 해결에 충분하다고 생각합니다.

Github을 통해서 올해 ICPC때 사용했던 팀 노트와, 연습 기록을 공개했다. https://github.com/koosaga/DeobureoMinkyuParty아직 완성된 팀 노트가 아니라, 추가적으로 내용이 찰 때마다 업데이트가 될 예정이다. 팀 연습 역시 하는 대로 결과를 올릴 예정이다.

총평후반부에 너무 루즈했다. 뒷심 + 멘탈이 딸리는 거 같은데 발전이 필요. Short Diary (스포일러 주의)A (0:04)(hyea) x좌표가 같은 경우와 아닌 경우로 나눠풀면 뚝딱이다. B (0:38)(koosaga) 짜증나는 dp인데 결국 어떠한 구간 s, e를 비교할 수 있는 경우의 수를 세면 된다. 각각의 구간에 대해서 [empty][a][b][c][d][...][z] 로 나누는 경우가 27승 정도인데 이건 dp안에 dp를 넣는 느낌으로 하면 된다 (물론 코드가 그렇진 않다..) C (1:23 +1)(alex9801) n

ScoreboardMy story혜아랑은 옛날부터 팀을 하기로 얘기가 되어 있었다. 2학기 개강 직전에 태평소국밥 (유성 홈플러스 근처에 있고 개꿀맛임) 에서 민규랑 팀을 하기로 최종 합의를 봤다. 예전부터 "지훈이나 민규 둘 중 하나" 라고 얘기를 했고 그래서 팀원을 말하기 참으로 눈치 보이는 상황이었는데 그때 마침 청하 한병을 깐 상황이어서 그냥 얘기해 버렸다. 팀명은 내가 지었고, 괜찮은가에 대해 고민을 아주 많이 했으나 이건 PC보다는 표현의 자유라고 생각해서 확정했다. 적당히 논란이 있어야 좋은 팀명이라는 나의 관종같은 철학이 반영되었다 그 이후 팀 연습은.. 세보니 7번 했다. 다들 바쁘고 시간이 잘 안 겹쳐서 저 정도면 열심히 잡았다고 생각.. 방학 때 최대한 열심히 할 계획이다. 크게 말린..

이 글의 대부분의 내용이 https://koosaga.com/243 에 재작성되었으니, 확인해 보는 것을 추천한다.[2017.07.29 초판][2017.11.10 증명 추가]IOI 2016에 출제된 Aliens 문제의 해법에서는, 굉장히 독특하면서 다양한 문제에 적용될 수 있는 최적화 기법이 나왔다. Aliens 문제와 비슷한 몇 개의 문제를 통해 이 기법을 설명하려 한다. #1. Aliens (IOI 2016 Day2 Problem3) 먼저 이 문제의 최적화 방법을 알기 위해서는 O(nk) 풀이를 알고 있어야 한다. 이 풀이에 대해서는 전명우님의 블로그에 서술되어 있다. 고로 여기서 설명하지 않는다. O(nk) 풀이를 보면, 다음과 같은 특징이 있다.k가 커질수록 답은 항상 감소한다. k에 대한 조건이..