구사과

오랜만에 써 보는 후기 글 Qualification Round Rank 8381 / 42 points. 30점 통과로 다음 라운드 진출했다. 1번은 쉬운 문제였다. 2번은 DP로 했는데 그리디를 써도 잘 된다는 걸 나중에 알았다. 3번도 쉬운 문제 같았으나, 꼼꼼한 구현이 필요해 보였다. 어차피 3/4번 중 하나만 풀면 되어서 시도하지 않았다. 4번은 처음에 재밌는 문제라고 생각하고 짰다가 몇번 틀렸고, 알고 보니 지문을 잘못 읽었었다. 적당히 통과할 정도로만 풀고 넘어갔다. 5번은 뭐 뭔소리인지 모르겠네 알기 싫다. Round 1A 당시 육군훈련소 군사훈련으로 불참;; 인터넷 편지로 1A 3번 문제를 보내 주신 분이 두 분 계셨다. 감사합니다. (__) Round 1B Rank 641 / 59 poin..

사실 지금 쓰고 있는 글이 더 있긴 한데 일단 이 정도만 공개합니다. USACO FEB20 Silver. Triangles 일반성을 잃지 않고, 빗변이 직각 모서리의 우상향에 존재한다고 가정하자. 다른 방향들은 점들을 축에 대칭시킨 후 똑같이 해보면 된다. 직각인 점 $(x_1, y_1)$ 를 하나 고정시켰다면, 우리가 원하는 것은 이 점의 위에 있는 점 $(x_1, y_2)$ 과 오른쪽에 있는 점 $(x_2, y_1)$ 을 골라서 $(x_2 - x_1) (y_2 - y_1)$ 을 모두 합하는 것이다. 이 때 곱해지는 두 항이 독립이기 때문에, 모든 가능한 $(x_2 - x_1)$ 을 합하고, $(y_2 - y_1)$ 을 합한 후 이 값을 곱해줘도 된다. 이렇게 되면, 모든 점에 대해서 이 점 위에 있는..

Project-TCS 발표 자료 알고리즘에서 분할 정복 은 큰 문제를 부분 문제로 나누는 과정을 뜻한다. 이 때 부분 문제들이 가져야 하는 특징은, 원래 문제보다 쉬워야 하고, 부분 문제를 합칠 수 있어야 한다. 예를 들어서, Heavy Light Decomposition은 트리에서 큰 문제를 부분 문제로 나누는 과정에서 자주 등장한다. 각 문제가 쉽고 (직선), 합치는 것이 가능 (Light edge를 통해서 묶음) 하기 때문이다. 트리의 경우에는 HLD 외에도 다양한 분할 정복 기법이 존재하지만, 그래프를 분할 정복하는 것은 쉽지 않다. 일반적으로, Treewidth와 같이 그래프의 특수한 성질을 요구하는 경우가 많다. 이번에 다룰 Expander Decomposition 은, 그래프의 특수한 성질과..