남남서의 블로그

지금(13일 토요일 오후 9시 40분) 쓰고 비공개로 설정해놓았다가 내일 풀 예정! 이따가 오후 11시에 코드잼 round 2도 있는데.....ㅠㅠㅠ 피곤해...대회 시작까지전날에는 최근 코드포스 문제랑 앳코더 문제, 그리고 친구가 풀고 있던 APIO 2013 문제들 잠깐 보다가 잤다. 재작년에는 내가 APIO를 안 쳤고, 작년에는 아주대에서 봤고 boat에서 말려서 아주 망했던 아픈 기억이 있다. 올해는 국민대학교였다. 정보 관련해서 건국대 서강대 아주대 한림대는 가봤는데 국민대는 처음 가봤어..APIO는 보통 쉬움-중간-어려움의 박자가 있었던 것 같았고, 그래서 일단 쉬운 문제가 하나 있을 걸로 생각했다. 예를 들면 2016년(한국)의 세트에서는 gap-boat-fireworks, 2012년(일본)의..

기하 코딩은 고통이다. 덜 고통스럽게 하자.점 관리하기점을 나타내는 struct를 만들어 쓰는 경우가 많이 있는데, 개인적으로는 std::pair가 더 낫다고 생각한다. std::pair는 헤더에 포함되어있다. 보통 헤더가 이걸 포함하고 있기 때문에 #include 만 해도 쓸 수 있게 된다. PS에서는 대부분 using namespace std;를 하기 때문에 여기서도 이걸 한 걸로 가정한다. pair가 입력하기 불편하기 때문에 이렇게 할 수 있다. AخAtypedef pair pii; // C-styleusing pii=pair; // C++11또한 코드를 직관적으로 만들기 위해 이런 전처리를 시킬 수 있다. xxxxxxxxxx#define x first#define y second벡터 기하를 하다 ..

BOJ 2430 : 거울대칭트리 그래프.주어진 그래프가 거울대칭트리 그래프면 만족해야 하는 충분조건들을 생각해보자.Case 1 : 복사 전의 루트가 degree 1인 경우결과 그래프에는 반드시 degree가 1인 정점이 두 개 존재해야 한다. 그 두 정점을 기준으로 그래프가 대칭적이어야 하고, 그 중심에는 모든 leaf들이 있어야 할 것이다. 즉 그 두 정점을 a와 b라고 하고, a를 기준으로 BFS한 거리 배열을 d1, b를 기준으로 한 BFS 거리 배열을 d2라고 했을 때, d1[i]=d2[i]인 점들의 집합은 b를 기준으로 한 rooted tree를 이루며, 그 두 rooted 트리가 같은 모양이어야 한다.Case 2 : 복사 전의 루트가 degree 2 이상인 경우결과 그래프는 degree가 1인..

JOI Spring Camp 2016 풀이Available on AtCoder.Day 1Matryoshka지름 Ri, 높이 Hi인 마트료시카 안에는 지름과 높이가 둘 다 작은 마트료시카를 최대 한 개 넣을 수 있다. 그리고 이것이 중첩이 가능하다. 다른 마트료시카에 들어가지 않는 마트료시카를 바깥 마트료시카라고 하자.어떠한 마트료시카들의 집합이 있을 때, 여기서의 바깥 마트료시카의 최소 갯수를 구하는 방법에 대해 생각해보자. 잘 생각해보면, 바깥 마트료시카의 갯수가 많아지는 이유는 마트료시카들이 같은 마트료시카에 들어가지 못해서이다. 즉, 마트료시카 중 몇 개를 선택하여 그 집합을 S라고 할 때, S에 속하는 마트료시카들이 모두 서로 포함할 수 없다면, 이들은 모두 서로 다른 바깥 마트료시카에 들어가야 ..

JOI Spring Camp 2016 문제설명을 대충 해놓았으니 문제 PDF와 같이 읽도록 하자.Day 1마트료시카 인형 (マトリョーシカ人形, Matryoshka)당신은 마트료시카 인형을 파는 가게를 열고자 한다. 당신은 공장에 개의 인형을 주문했다. 이것들에는 1번부터 번까지의 번호가 붙어있다. 번째의 마트료시카 인형은, 직경 , 높이 의 속이 비어있는 원기둥으로 생각할 수 있다.마트료시카 인형은 하나를 다른 하나에 넣어서 보관할 수 있다. 각각의 마트료시카 인형은 그보다 직경과 높이가 모두 작은 다른 마트료시카 인형을 1개만 수납할 수 있다. 수납된 마트료시카의 속에 또다른 마트료시카를 수납하는 것도 가능하다.어느 날, 마트료시카 인형 공장에서 연락이 왔다. 주문한 개의 마트료시카 인형을 모두 한번에..