남남서의 블로그

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

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개만 수납할 수 있다. 수납된 마트료시카의 속에 또다른 마트료시카를 수납하는 것도 가능하다.어느 날, 마트료시카 인형 공장에서 연락이 왔다. 주문한 개의 마트료시카 인형을 모두 한번에..

JOI일본 정보 올림피아드는 예선(予選, yosen)과 본선(本選, honsen)이 있다. 본선 이후의 춘계 트레이닝 합숙(春季トレーニング合宿)에서 국가대표를 선발한다.일본에서는 올림피아드와 올림픽을 구분하지 않고 올림픽(オリンピック)이라고 부른다고 한다. 그래서 일본 정보 올림픽, 日本情報オリンピック. JOI!공식 사이트는 여기. 예선과 본선 문제와 해설은 여기. 문제, 채점 데이터, 해설 슬라이드, 모범 소스, 그리고 점수 분포가 공개되어있다.춘계 트레이닝 합숙의 문제와 해설은 여기. 合宿概要은 합숙 개요이고, 合宿における競技問題가 문제이다. 각 경기일의 문제, 채점 데이터, 해설 슬라이드, 모범 소스, 그리고 점수 분포가 공개되어있다.예선 / 予選예선은 12월 10일경 이루어진다. 정확히는 다음과 ..

ojuz 링크 Baekjoon Online Judge 링크먼저 해야 할 observation은, 최종적인 점수에 관한 것이다. 쪼개진 \(k+1\)개의 부분의 각각의 합을 \(s_{1}, s_{2}, \cdots , s_{k+1}\)이라고 할 때, 점수는 \( \large \displaystyle{\sum_{1 \leq i