총평후반부에 너무 루즈했다. 뒷심 + 멘탈이 딸리는 거 같은데 발전이 필요. 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에 대한 조건이..
Timeline내 관점에서 본 대회 타임라인은 대충 다음과 같다. 우리 팀은 여느 때처럼 컴퓨터 1대에 인터넷 끊고 팀노트 손으로 치면서 진행했다. * 0분 ~ : 프린터가 고장났어?? (대혼란) * 3분 : 혼란 속에서 A 약간 늦게 accept * 10분 ~ 20분 : J가 풀렸네?? 근데 bitset에 매칭인데?? (대혼란 + 멘탈붕괴) * 20분 ~ 30분 : 딴 걸 아는게 없어서 코딩 시작. 이후 J AC * 30분 ~ 60분 : C 아이디어 나오고 코딩 준비 완료. 혜아 초반부터 BEF 잡다 멘붕. 민규 I 디테일을 정리 * 60분 ~ 75분 : C 코딩하고 예제 맞왜틀. D가 쉽다는 제보 도착 * 75분 ~ 90분 : 민규 D 코딩 * 90분 ~ 92분 : C 몇글자 고치고 AC * 93분 ..
총평I를 못풀어서 어쩌나 했는데 그거 빼고 다 풀어서 다행이다. 말린거 같았는데 생각보다 나쁘지 않았음 Short Diary (스포일러 주의) A (0:34 +1)(hyea) 처음과 끝 조건을 잘 보자, 실수를 쓰면 풀리는 문제지만 BigInteger를 쓰는게 안정적인것 같다 B (4:09)(alex9801) Yet another ant problem. 개미에 색깔이 추가되었지만, 어렵지 않게 풀 수 있다.(koosaga) 기본적으로 원에 올려놓은 개미 문제. 일반적인 개미 문제랑 관찰이 크게 다르지 않다. 사실 원이라서 엄청 헷갈렸는데 민규가 많이 도와줬다. C (1:44)(hyea) 적당한 관찰을 하면 풀 수 있는 문제이다. 숫자가 작아서 DB를 만들어도 된다. D (2:47 +3)(hyea) 수식을..
(2017.10.06 초판)(2017.10.07 Weeping Fig 문제의 해설을 보완해서 다시 작성했다.) 전대프연 2016. 분단의 슬픔최소 비용을 구하고자 한다 -> min cut과 최소 비용이 동치임을 찾는다 -> min cut으로 풀린다 류의 문제 중에서 제일 쉬운 것 같다. 이유는 간단하다. 그런 문제는 보통 풀 수 없거든source와 sink를 만들고, 그 사이에 사람들을 정점과 간선으로 적절히 이어서, source쪽 cut에 속한 정점을 A 진영 / 그렇지 않은 정점을 B 진영으로 둘 것이다. 방법은 간단하다. Min cut에 속하는 정점 집합을 $S$라 하고, 그렇지 않은 정점 집합을 $T = V\setminus S$ 라 하면, * 무조건 $S$에 들어가는 정점은 source와 $\in..
[2016.11.02 초판][2017.10.05 트리와 쿼리 7/11 추가]https://www.acmicpc.net/contest/scoreboard/195 시간이 남을때마다 하긴 했는데... 너무 힘든 연습이었다 ㅠㅠ 아주 간략하게 풀이를 설명한다. 트리와 쿼리 2 Sparse table로 level ancestor를 빠르게 구할 줄 안다면, 간단한 케이스 분석으로 풀 수 있다. 트리와 쿼리 1 / 3 Heavy Light Decomposition으로 풀 수 있다. 1번의 경우 range max segment tree, 3번의 경우 std::set으로 해결 가능하다. 어렵지 않고 개념도 유용하니 모른다면 배워보자. https://blog.anudeep2011.com/heavy-light-decompo..
(9/30 초판) (9/30 ~ 10/10 PDF 연습 문제 17/22개 해결. 나머지는 시험 끝나고 시작할 것 같습니다.) (자료 출처는 이 사이트 내부 어딘가. 난 혜아한테 받아서 잘 모른다) 수학적 귀납법이란? 어떠한 명제 $P(1), P(2), P(3), \cdots$ 가 다음 두 성질을 만족한다고 하자. * (기저 조건) $P(1)$ 이 참이다. * (귀납 조건) $n \geq 1$ 일 때, $P(1), P(2), \cdots P(n)$이 참이면, $P(n+1)$이 참이다. 그렇다면 $P(1), P(2), P(3), \cdots$가 모두 참이다. 왜? 사실 위에 적은 수학적 귀납법을 "강한 수학적 귀납법" 이라고 부르고, 조금 더 약한 폼의 수학적 귀납법을 "수학적 귀납법" 이라 한다. 진짜 "..
(2017.9.26 : 초판)(2017.9.30 : J번을 제외한 모든 문제의 풀이를 추가했습니다. 블로그에 LaTeX 조판을 설치했고, G번 문제 풀이를 시험적으로 전부 LaTeX 수식으로 변경했습니다. J번 문제를 포함해서 앞으로 올라오는 글들은 모두 다 예쁘게 조판되어서 올라갈 예정이에요!)(2017.9.30 : J번의 풀이가 추가되었습니다.) Scoreboard잘해서 좋당 ㅋㅋ Problems / Solution sketch대충 난이도 순으로 정렬했다. 사실 5번째부터 10번째까지는 이견이 있을 수도 있고 나도 잘 모르겠지만 (…) 푼 사람 수와 개인적인 의견 등을 감안하여 적당히 정렬했다.마음에 들었던 문제는 D / G / J였다. B도 풀이가 상당히 재미있다.K. RegistrationH. M..
1. 도어맨굉장히 간단한 O(N) 그리디 풀이도 있는 거 같은데 난 잘 모르겠어서 DP로 해결했다. DP[i] = (1 ~ i번 사람이 모두 럽에 들어갔을 때 더 넣을 수 있는 사람의 수) 라고 정의하자. 두가지 케이스가 있다. * 첫번째 사람을 클럽에 영영 안 넣고 두번째 사람부터만 계속 추가. 이 방법으로 K명이 추가로 들어갔다면 DP[i] = K가 가능해진다. * 두번째 사람 이후를 K번 정도 더 넣고, 첫번째 사람을 추가. 차이에 문제가 생기지 않는다면 DP[i] = DP[i + K + 1] + K + 1가 가능해 진다. 모든 K에 대해서 대충 시뮬레이션한 후, 시뮬레이션 과정에서 문제가 없었으면 값을 갱신해주면 된다. 이런 식으로 DP 테이블을 채우면 DP[0]이 답이 된다. 잘 구현하면 O(N..
- Total
- Today
- Yesterday