본문 바로가기

2017/09

2017 ACM-ICPC Daejeon Regional 인터넷 예선 후기 2016년 3월 PS라는걸 처음 알게 되고 ,2016년 8월 처음으로 이걸 제대로 공부해 봐야겠다는 생각이 들었고, 2016년 12월 블로그 이름을 ACM-ICPC 상 탈 사람이라고 달아버리고, 마침내 어제 목표로 하던 ACM-ICPC 대전 리저널 본선으로 가는 티켓을 따기 위한 인터넷 예선을 치루게 되었다. SCPC, 카카오 코드 페스티벌 등.. 이제 대회 경험이 꽤 생겼지만 이렇게 가슴이 떨린적은 처음인것 같다. 처음부터 이 대회를 목표로 공부를 시작하였으니 그런듯 하다 .. 2시에 대회가 시작된 뒤 등록 문제가 바뀐 걸 인지 못해서 엉뚱한 답안을 작성할 뻔 했지만 팀원들이 잘 지적해주어서 제대로 고쳐서 냈다. 초반 스퍼트는 굉장히 좋았다.. 아니 솔찍히 기대 이상이였다. 우리가 4문제를 풀어낸 시간.. 더보기
좌표압축 기법 좌표압축 기법은 Problem Solving을 하다보면 정말 정말 정말 자주 쓰이는 테크닉이다. 세그트리(or BIT) 등등.. 구간 쿼리와 함께 같이 쓰이는 경우도 많고, 오프라인 쿼리등을 처리할 때 등등 많은 경우에서 유용하게 이용된다. 개념에 대한 설명을 하기 위하여 한 문제를 예시로 들어보겠다. N( 더보기
BOJ)5542 JOI 국가의 행사 문제: icpc.me/5542 쿼리에서 받는 두 도시간의 경로 중 경로에 포함 된 도시들의 축제하는 도시와의 떨어진 거리의 값들 중 최솟값이 최대가 되는 경로를 구하는 문제이다. 우선 다익스트라 알고리즘을 사용하여 각 정점들의 가중치(축제가 열리는 도시와의 최단거리)를 구해줄 수 있다. 이후 쿼리를 처리해주어야 하는데 disjoint set을 이용하여 쿼리를 처리해주려고 한다. 우선 각 쿼리 번호에 해당되는 양 끝 정점들에 쿼리 번호들을 저장해준 뒤 간선의 가중치가 큰 순서대로 간선을 정렬하여 간선을 보면서 정점을 dsu를 이용하여 병합해 줄것이다. 이 때 만약 두 정점이 같은 쿼리 번호를 가지고 있다면 해당 쿼리 번호의 답은 그 간선의 가중치가 될 것이다. 1234567891011121314151617.. 더보기
BOJ)13330 유사 팰린드롬 문제: icpc.me/13330 w를 구성할 수 있는 세타 팰린드롬의 최소 개수를 출력하는 문제이다. 이 문제를 해결하기 위하여 두가지 디피 테이블을 정의해야한다. dp1[l][r]은 l,r 구간의 u의 개수 dp2[pos]는 0~pos 의 문자열을 구성 할 수 있는 세타 팰린드롬의 최소 개수라 정의하면 n^2으로 dp2를 채우기 위해 for문을 돌릴 때 이터레이터 j에 대한 검사를 dp1으로 할 수있다. 123456789101112131415161718192021222324252627282930#include #include #include using namespace std;int n, k, l, dp[10010];int a[10010][10010];char s[10010];int func(int l.. 더보기
BOJ)13352 석양이 진다... 문제: icpc.me/13352 n개의 점들이 주어질 때 두직선만으로 모든 점을 커버가능한지 판별하는 문제이다. 얼마전 코포 B번에서 유사한 문제 http://codeforces.com/contest/849/problem/B 가 등장하였지만 코포 문제는 N^2으로 해결할 수 있었던 반면 이 문제는 N제한이 10만이기 때문에 N^2으로는 풀 수 없다. 그래서 정해를 생각해보다가 도저히 떠오르지 않아서 작년에 들었던 야매 풀이를 떠올려서 풀었다. 풀이는 랜덤하게 두 점을 뽑아서 직선을 하나 만든 다음 나머지 모든 점이 한 직선으로 놓일 수 있는지 확인한다. 여기서 나머지 모든 점이 한 직선으로 놓인다면 당연히 두직선으로 커버되는 것이니 답이 되고 안된다면 위의 행동을 반복한다. 위의 행동을 충분히 반복하였는.. 더보기
BOJ)5842 Partitioning the Farm 문제: icpc.me/5842 n*n 격자가 주어질 때 주어진 격자를 가로나 세로로 k번 분할 할 수 있다. 분할 된 각 부분들의 합의 최댓값의 최솟값을 구하는 문제이다. 최대중에 최소를 구하는 문제이므로 파라메트릭 서치로 접근할 수 있다. 다만 격자에서 처리해야하는게 좀 까다로울 수 있는데 n이 15밖에 안되므로 2^15의 모든 경우로 세로 격자를 세워준 뒤 파라메트릭 서치로 가로 격자를 세우며 답을 구할 수 있다. 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667#include #include #include using name.. 더보기
BOJ)2337 트리 자르기 문제: icpc.me/2337 트리에서 임의의 몇개의 간선을 잘라서 크기가 m인 트리를 얻고 싶을 때 잘라야하는 간선의 최소 개수를 구하는 문제이다. 트리디피로 풀 수 있는 문제이다. 기존에는 트리 디피를 n^3의 방법으로 풀어왔지만 이번에 smu형님의 도움으로 n^2 log n으로 푸는 방법을 알게 되었다. 우선 dp테이블을 dp[here][k]를 here번 정점이 루트인 크기가 k인 트리를 만드는데 필요한 간선컷의 최솟값으로 정의하면 dp[here][k]를 어떤식으로 빌드할거냐면 here가 가지는 자식들은 여러개의 서브트리를 이룰것이다. 이 서브트리를 하나씩 병합하면서 dp[here][k]를 채울 것이다. 당연히 처음에는 dp[here][1]밖에 없을 것이다 .여기서 1은 곧 자기 자신이다 이는 0으.. 더보기
deque를 이용한 다이나믹프로그래밍 BOJ)5977 Mowing the Lawn 라는 문제를 풀 때 이용한 테크닉이다. 문제: icpc.me/5977 시퀀스가 주어질 때 주어진 시퀀스에서 수를 선택하여 최댓값을 만들어야 하는데 수를 연속으로 k이하로 선택가능할 때 답을 출력하는 문제이다. 예를 들어서 n이 5고 k가2라면 (1,2) (4,5) 이런식으로 연속된 수열은 최대 k까지 선택하여야 한다. 문제만 보면 당연히 다이나믹 프로그래밍을 떠올릴 수 있다. 하지만 점화식을 세우다보면 n이 너무 크기때문에 곤란할 수 있다. 하지만 일단 점화식을 세워보자 dp[i]는 i번째 인덱스까지 수열을 처리하였을 때 최댓값이라고 정의를 한다면 dp[i] =max(psum[i]- psum[j]+ dp[j-1]) j:(i-k+1 ~ i) 라는 수식이 세워진다.. 더보기
BOJ)11003 최소값 찾기 문제: icpc.me/11003 구간 n에서 ai-l+1 ~ai의 최솟값을 매번 찍어내는 문제이다. RMQ 문제로 생각하여 세그트리나 multiset을 이용한 풀이를 예전에 제출했지만 n이 너무나도 커서 tle를 맞은 후 잊고 있던 문제였지만 오늘 다른 문제에서 다이나믹프로그래밍을 공부하다가 필요에 의해 다시 풀게 된 문제이다. 이 문제는 deque를 이용하여 해결할 수 있다. 연속 된 시퀀스에서 deque에는 pair형으로 해당 값과 해당 인덱스를 가지고 있을것이다. 우리는 답을 출력할 때 deque에 삽입 되어있는 구간에서 최솟값을 출력해야 하기때문에 앞이나 뒤에 최솟값을 가지고 있어야한다. 일단 deque의 front에 최솟값을 가지고 있다고 해보자. 그러면서 만약 deque의 front의 값의 인.. 더보기
BOJ)1460 진욱이의 농장 문제: icpc.me/1460 n*n 크기의 격자에 씨를 뿌리는 방법이 주어지고 격자에서 임의의 정사각형을 선택하여 정사각형 내부의 점에 서로 다른 씨앗이 최대 2개가 되도록 정사각형을 선택할 때 가장 넓은 정사각형의 넓이를 출력하는 문제이다. 씨앗의 종류인 F의 범위가 0~7인걸 이용하여 F^2+F로 모든 경우의 씨앗을 정한다면 현재 상태에서 해당하는 씨앗이 뿌려져있는 가장 넓은 정사각형을 구하는 문제로 치환하여 풀 수 있다. 이는 다이나믹 프로그래밍을 이용하여 n^2에 해결할 수 있다. 1234567891011121314151617181920212223242526272829303132333435#include #include #include using namespace std;int res, a[10.. 더보기

티스토리툴바