생각날때마다 올리는 블로그

Link 문제 링크 Problem JOI시에는 1개의 충분히 긴 도로가 있습니다. 이 도로는 수직선으로 간주할 수 있으며, 각 지점은 1개의 실수에 의한 좌표로 표시됩니다. 또한 JOI시에는 이 도로를 따라 N개의 시설이 설치되어 있으며, 좌표가 작은 순서대로 1부터 N까지의 번호가 매겨져 있습니다. 시설 $i(1\leq i\leq n)$의 위치는 좌표 $A_i$입니다. JOI 시에서는 이제 시설 안전 점검을 할 것입니다. 시설 i에는 점검해야 할 항목이 $B_i$개 있습니다. 이제 점검할 수 있는 K명의 목수가 모였습니다. 안전 점검이 시작될 때 목수는 모두 좌표를 0에 두고 있습니다. 점검이 시작되면 각 목수는 1분 동안 다음 두 가지 행동 중 하나를 취할 수 있습니다. 거리 1만큼 좌표를 이동합니다..

Link 문제 링크 Problem The JOI plain is a wide plain spreading from west to east. We can consider the JOI plain as a number line. A spot on the JOI plain is denoted by a coordinate. The positive direction of the number line corresponds to the east direction. Now winter comes in the JOI plain. There are N snowballs on it, numbered from 1 to N from the west to the east. In the beginning, the coordinat..

Link 문제 링크 Problem 수열 A가 주어졌을 때, 가장 긴 증가하는 부분 수열과 개수를 구하는 프로그램을 작성하시오. 예를 들어, 수열 A = {10, 20, 10, 30, 20, 50} 인 경우에 가장 긴 증가하는 부분 수열은 A = {10, 20, 10, 30, 20, 50} 이고, 길이는 4이고, 1개이다. A = {10, 20, 30, 10, 20, 30}인 경우에는 가장 긴 증가하는 부분 수열의 길이는 3이고, 4개가 있다. Input 첫째 줄에 수열 A의 크기 N (1 ≤ N ≤ 1,000,000)이 주어진다. 둘째 줄에는 수열 A를 이루고 있는 Ai가 주어진다. (-1,000,000,000 ≤ Ai ≤ 1,000,000,000) Solution Part I 일단 LIS 문제이고, L..

Problem 민혁이는 매주 금요일마다 지수와 함께 논다. 이번 주 금요일은 지수와 민혁이가 친구가 된지 십 년이 되는 날이다. 따라서, 둘은 엄청난 게임을 하기로 결정했다. 민혁이는 바닥이 흙인 운동장을 예약했고, 지수는 조약돌 한 개를 들고 왔다. 먼저 민혁이는 운동장 바닥에 나뭇가지로 방향 그래프를 그린다. 이 그래프에서 모든 정점은 많아야 한 개의 나가는 간선(outgoing edge)를 가질 수 있다. 그 다음 민혁이는 조약돌을 한 정점 위에 올려 놓는다. 만약, 조약돌이 있는 정점에 나가는 간선이 있다면, 조약돌은 그 간선을 통해서 이동할 수 없을 때까지 계속해서 이동한다. 더 이상 이동할 수 있는 정점이 없다면, 조약돌은 그 자리에서 멈춘다. 조약돌은 그래프를 무한히 이동할 수도 있고, 방문..