(2017.04.01 초본) 집나간 PS실력을 살리기 위해 앳코더 문제를 풀어보려고 한다. 일단 제일 어려운 것만...(실제로는 저대로 안 썼습니다. 스샷 다시 찍기 귀찮아서)이 스크립트가 제대로 작동하는 가장 옛날 라운드인 ARC035부터 돌기로 했다. (그전에는 _4 로 suffix를 붙인듯) + Grand Contest F를 추가했다. 진짜 다 풀 수 있을까 (...) + (2018.01.17 : 오랫동안 동결된 걸 보고 역시 현실성이 없다는 걸 깨달았습니다 (...) 문제를 쓰는 것 뿐만 아니라 제대로 된 풀이까지 써야 해서 더 부담이 됐던 것 같습니다. 번역이 안 된 ARC를 제외하고는 전부 리스트에서 삭제했습니다. 여기 있는 ARC 정도만 클리어하는 걸 목표로 하겠습니다. 여기 원래 적혀있던 ..
(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$의 왼쪽에 있으..
먼저 “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..
온사이트 대회가 끝나고 후기를 쓴 경험이 많지 않다. 쓸 내용이 많은 것도 있고, 대회가 끝난 이후에는 항상 일정이 바빴기 때문이기도 하다. 이번에도 예외는 아니지만, 집에 가는 기차에서 짧게나마 경험담과 느낀 점을 적어보려고 한다. 는 개뿔… 글이 길어져서 한 달 뒤 태국 리저널 가는 비행기에서까지 후기를 쓰고 있다. 그리고 크리스마스에 마감. Qualification 상식적으로 앳코더 대회에서 세계 20등을 할 가능성이 당연히 없다고 생각해서 Qual A는 그냥 걸렀다 (아마 그 날 어디 나갔던 것 같다). Qual B도 비슷한 생각이었지만, 바쁘지 않고 앳코더 대회가 있으면 쳐야지. 그래서 쳤다. D를 열고 시작했는데, 상당히 어려웠던 문제였다. 굉장히 ad-hoc한 느낌이 강했던 문제였고, 풀이의..
(1995)
- Total
- Today
- Yesterday