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

Link 문제 링크 Problem JOI시에는 1개의 충분히 긴 도로가 있습니다. 이 도로는 수직선으로 간주할 수 있으며, 각 지점은 1개의 실수에 의한 좌표로 표시됩니다. 또한 JOI시에는 이 도로를 따라 N개의 시설이 설치되어 있으며, 좌표가 작은 순서대로 1부터 N까지의 번호가 매겨져 있습니다. 시설 $i(1\le i\le 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길이가 N인 수열 A1A_1A1​, A2A_2A2​, ..., ANA_NAN​이 주어진다. 이때, 다음 쿼리를 수행하는 프로그램을 작성하시오.i ji~ji j : Ai, Ai+1, ..., AjA_i,~A_{i+1},~...,~A_jAi​, Ai+1​, ..., Aj​에서 가장 큰 연속합을 출력한다. (1 ≤ i ≤ j ≤ N)수열의 인덱스는 1부터 시작한다.연속합은 연속된 몇 개의 수를 선택해서 구할 수 있는 합 중 가장 큰 합이며, 수는 한 개 이상 선택해야 한다.Solution Part I대충 구간에 대한 쿼리를 다루니, 세그먼트 트리가 제일 유력하다.물론, 플래티넘 2의 특성 상 Mo’s algorithm이 판을 치는 단계라지만.. 이건 뭐 구간을 나누어서 따..

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..

Link http://icpc.me/2873 Problem 상근이는 우리나라에서 가장 유명한 놀이 공원을 운영하고 있다. 이 놀이 공원은 야외에 있고, 다양한 롤러코스터가 많이 있다. 어느 날 벤치에 앉아있던 상근이는 커다란 황금을 발견한 기분이 들었다. 자신의 눈 앞에 보이는 이 부지를 구매해서 롤러코스터를 만든다면, 세상에서 가장 재미있는 롤러코스터를 만들 수 있다고 생각했다. 이 부지는 직사각형 모양이고, 상근이는 R행 C열의 표 모양으로 나누었다. 롤러코스터는 가장 왼쪽 위 칸에서 시작할 것이고, 가장 오른쪽 아래 칸에서 도착할 것이다. 롤러코스터는 현재 있는 칸과 위, 아래, 왼쪽, 오른쪽으로 인접한 칸으로 이동할 수 있다. 각 칸은 한 번 방문할 수 있고, 방문하지 않은 칸이 있어도 된다. 각..

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

http://icpc.me/2858문제가장자리에 까는 빨간색 타일 R, 가장자리가 아닌 곳에 까는 갈색 타일 B를 준다.이 때, 방의 크기를 맞추어라 풀이간단한 수학문제이다.$N\times M$의 타일을 생각해보자.그러면, 가로와 세로가 만나는 총 4개의 지점은 겹치게 된다.즉, $2\times (N+M)-4$가 되는 것이다.이가 빨간색 타일의 개수이다.또한 타일을 안 쓰는 부분이 없으므로 R+B하면 총 면적이 된다. 이는 $N\times M$ 이로써 우리는 $N+M=\frac{R+4}{2}$, $L\times M=R+B$를 얻을 수 있다.$R\le 5000$이므로 반복문을 돌리면서 $L$과 $M$을 찾아주면 된다. 코드 1234567891011121314#include using namespace std..

http://icpc.me/2075 문제N*N의 격자판에 숫자가 들어온다.이 격자판에 있는 숫자 중 N번째로 큰 수를 출력하라. 풀이이 문제는 메모리가 12MB밖에 안된다.왜 이렇게 작게 해놨느냐? 2차원배열을 만들거나 그냥 vector int해서 하면 MLE가 뜬다.계산했을땐 8MB였는데 왜 MLE 뜨는지 모르겠다. 에반데따라서 다른 전략을 써야한다.이 문제에서 가장 중요한 것은 N번째로 큰 수를 출력한다는 것에 있다.즉 우리가 실제로 필요한 수의 개수는 "이 때까지 받았던 수들 중 N번째로 큰 수들의 모임"이 필요하다.만약 다음에 받는 수가 저기에 들어가면 바꿔주면 되기 때문이다. 예를 들어보자.8번째로 큰 수를 출력하는 상황이고, 배열에 2, 4, 5, 6, 7, 8, 9, 10 가 있다.이 때 1..

https://docs.google.com/presentation/d/1Cik40Ngs-kr7-kgVVI4dor78c-Vv7M8vtZiUFxxpi9k/edit?usp=sharing A. 새로운 시작파이팅!!을 출력하는 문제Text를 쓰던가 C를 쓰던가 일단 출력하면 정답원래는… 이런 문제가 아니였는데….B. CASIO결론적으로 문제에서 요구하는 것은 들어오는 두 숫자가 같은가? 이다.최대 10자리까지 들어오므로 int형 배열을 사용할시 틀린다.long long을 이용해서 비교해주면 끝 C. 이상한 기호Subtask 1 : A,B

http://icpc.me/10974 문제1~N까지의 수들을 사전순으로 출력하라 풀이next_permutation(begin,end) : [begin,end)까지 중복 없이 사전순으로 순열을 구해준다.앙 개꿀띠 코드1234567891011121314#include using namespace std;int main(){ int n; scanf("%d",&n); vector v; for(int i=1;i