본문 바로가기 메뉴 바로가기

PS 이야기

프로필사진
  • 글쓰기
  • 관리
  • 태그
  • 방명록
  • RSS

PS 이야기

검색하기 폼
  • 분류 전체보기 (141)
    • 문제 (1)
    • 해법 (18)
    • IOI (42)
      • IOI2011 (6)
      • IOI2012 (5)
      • IOI2013 (7)
      • IOI2014 (8)
      • IOI2016 (2)
      • IOI2015 (3)
      • IOI2017 (3)
      • IOI2018 (2)
      • IOI2019 (0)
      • IOI2020 (6)
    • ICPC (52)
      • 2012 대전 (3)
      • 2013 인터넷예선 (11)
      • 2014 전대프연 (1)
      • 2014 인터넷예선 (10)
      • 2014 대전 (11)
      • 2015 이후 한국대회 (6)
      • 해외리저널 (6)
      • World Finals (4)
    • Codejam (2)
      • Korea 2012 (1)
    • 우분투&서버 (0)
    • 공부 (24)
    • 잡담 (2)
  • 방명록

ICPC/2014 대전 (11)
L. Two Yachts

두 개의 요트가 있고, 요트를 이용하고 싶은 사람들의 예약 정보 시작 날짜, 끝 날짜, 대여 비용이 주어졌을 때, 최대 이윤을 구하는 문제다. 이 문제는 weighted interval scheduling의 확장판으로 two room weighted interval scheduling이다. 만약 요트가 두 개가 아니라 한 개라면 $O(N \lg N)$ Dynamic Programming 으로 해결할 수 있다. 이와 관련된 자료는 구글에 검색하여 쉽게 찾을 수 있다. 편의상 입력으로 주어진 예약(proposal)을 구간으로 표현하겠다. 이 문제를 $O(N^2)$ Dynamic Programming으로 해결할 수 있지만, 제한 시간을 초과한다. 이 방법에 대한 설명은 생략한다. 문제 입력 형식에 가장 중요한..

ICPC/2014 대전 2014. 11. 10. 17:39
K. Travel Card

버스를 타는 버스 정기권과 버스와 기차를 모두 타는 전체 정기권이 기간 별로 주어지고, 각 날 마다 버스와 기차 타는 회수가 주어졌을 때, $N$일 동안 버스와 기차를 타는 최소 비용을 구하는 문제다. 문제에서 정기권의 기간과 요금, 그리고 단일 회수로 탑승할 때의 비용은 입력과 상관없이 항상 같게 정해져있다. Dynamic Programming을 생각해볼 수 있다. D[i][j] = i번째 날 까지 버스와 기차를 타고, 현재 남은 버스 정기권의 기간이 j일 때 최소 비용 위와 같이 다이나믹 배열을 정의하자. 이처럼 정의하는 이유가 있다. 전체 정기권을 산 경우 정기권 기간내에는 고려할 사항이 아무 것도 없지만, 버스 정기권을 산 경우 정기권 기간 내에 전체 정기권을 사는게 더 이익일 수 있기 때문이다...

ICPC/2014 대전 2014. 11. 10. 11:55
J. Tours

문제에서 toroidal triangular lattices와 toroidal hexagonal lattices에 대해 그림 예시가 있다. Triangular lattices는 $M$이 짝수이며, hexagonal lattices는 $M$, $N$ 둘 다 짝수란 조건이 있다. 이런 그래프에서 해밀턴 회로 중 임의의 하나를 찾는 문제다. 이 문제는 2014 인터넷예선 그리드 그래프 문제와 흡사하다. 아래와 같은 방법으로 정점 순회를 하면 해밀턴 회로가 된다. #include int T, M, N, P; int main() { int i, j; for (scanf("%d", &T);T--;){ scanf("%d%d%d", &M, &N, &P); puts("1"); if (P == 3){ for (i=0;i

ICPC/2014 대전 2014. 11. 10. 11:05
I. Three Squares

2차원 평면에 점들이 $N$개 주어졌을 때, 동일한 크기인 정사각형 세 개로 모든 점들을 덮을 때 가능한 정사각형의 최소 크기를 구하는 문제다. 주어진 $N$개의 점을 포함하는 최소 직사각형을 생각하자. 서로 다른 점이 4개 이상일 때 아래와 같은 명제가 성립한다. 최소 크기의 정사각형 세 개로 모든 점을 덮을 때, 그 정사각형 중 하나는 직사각형의 네 꼭지점 중 하나의 점을 꼭지점으로 한다. 비슷한 상황으로 최소 크기의 정사각형 두 개로, 서로 다른 점 3개 이상을 모두 덮는다고 할 때, 아래와 같은 명제가 성립한다. 최소 크기의 정사각형 두 개로 모든 점을 덮을 때, 두 정사각형은 서로 대각으로 마주보는 두 꼭지점을 꼭지점으로 한다. 이분 검색으로 정사각형의 크기 $s$를 정하고 모든 점을 덮을 수 ..

ICPC/2014 대전 2014. 11. 10. 01:24
H. String Transformation

문제에서 well-formed라고 정의된 'a'와 'b'로만 구성된 문자열 A와 B가 주어진다. 두 인접한 문자를 바꾸면서 문자열 A를 문자열 B로 만드는 최소 회수를 구하는 문제다. 문자 'a' 를 '(' 로 바꾸고 문자 'b'를 ')'로 바꾸면 괄호 문자열이 되고 well-formed의 정의가 직관적이게 된다. 이 문제에서 문자열 A를 문자열 B로 바꿀 수 없는 경우는 두 문자열의 길이가 다른 경우 뿐이다. 문자 두 개로만 구성된 문자열이기 때문에 바꾸는 최소 회수 또한 직관적이게 생각할 수 있다. #include #include #include using namespace std; #define MAXN 100005 int T, N, M; char A[MAXN], B[MAXN]; int main()..

ICPC/2014 대전 2014. 11. 10. 00:36
G. Road Repair

노드가 $N$개인 트리가 주어진다. 트리의 간선에는 비용과 이익 두 가지 값이 있다. 우리는 임의의 경로를 선택하는데 경로에 있는 간선의 비용 합이 C를 넘지 않으면서 이익 합의 최대값을 구하는 문제다. 트리에서 경로는 연결되어 있으면서 경로를 부분 그래프로 봤을 때 정점의 차수가 3을 넘으면 안된다. 즉, 갈래가 없으면 안된다. 이 문제는 IOI 2011 Race 문제와 굉장히 유사한 면이 있다. 우선 분할 정복으로 접근할 수 있다. 이는 트리에서 아래 조건을 만족하는 정점이 항상 존재하기 때문이다. 관련 증명은 Race 문제의 글을 참고하자. 정점이 $N$개인 트리에서 어떤 점을 지웠을 때, 생기는 여러 개의 서브트리 중 정점의 개수가 가장 많은 서브트리의 정점 개수가 $\frac{N}{2}$ 이하다..

ICPC/2014 대전 2014. 11. 10. 00:20
F. Permutation Cycles

1 부터 $N$ 까지의 수 $N$개가 포함된 순열이 주어졌을 때 문제에서 정의한 그래프를 그릴 수 있다. 그 그래프에서 포함된 회로(cycle)의 개수를 세는 문제다. 순열로 표현한 그래프의 특징상 회로의 개수는 곧 연결 요소의 개수가 된다. 따라서 DFS, BFS 등 여러 가지 방법으로 Flood-Fill 을 하여 연결 요소의 개수를 구하면 된다. #include int T, N; int A[1001]; bool V[1001]; void dfs(int n) { if (V[n]) return; V[n] = 1; dfs(A[n]); } int main() { int i; for (scanf("%d", &T);T--;){ scanf("%d", &N); for (i=1;i

ICPC/2014 대전 2014. 11. 9. 23:07
E. Marbles

빨강, 파랑, 초록색, 세 가지 색상의 공들이 2차원 평면에 배치 되어 있다. 빨간색 공을 세는 직사각형, 파란색 공을 세는 직사각형, 초록색 공을 세는 직사각형 세 개를 크기 제한 없이 겹치지 않게 잡았을 때 세어지는 공의 개수를 최대화 하는 문제다. 여기서 직사각형 변 위에 있는 공도 세어주고, 겹쳐서는 안된다. 우선 직사각형의 크기 제한이 없다는 점을 생각하자. 그러면 가능한 직사각형의 배치를 아래와 같이 크게 두 가지로 나눌 수 있다. 이 두 가지 경우에 대한 코딩을 하고 y축 대칭, 직선 y=x에 대한 선대칭 및 $3! = 6$가지의 색상 재배열등을 행해 모든 경우를 고려할 수 있다. 우선 각 점들을 x 좌표 기준으로 정렬을 한 뒤 빨간색 영역이 차지하는 범위를 정한 뒤 segment tree ..

ICPC/2014 대전 2014. 11. 9. 22:57
D. Exploration

정점의 개수가 $N$개고 간선의 개수가 $M$개인 그래프가 주어진다. 각 정점의 차수가 $K$ 이상인 부분그래프 중 가장 큰 부분그래프의 크기를 구하는 문제다. 입력으로 주어진 그래프에서 차수가 $K$ 보다 작은 정점들은 답이 되는 부분그래프에 들어갈 수 없으므로 제거한다. 그런 정점들을 제거하면 새로운 그래프가 나오는데, 마찬가지로 새로운 그래프에서도 차수가 $K$ 보다 작은 정점들은 답이 되는 부분그래프에 들어갈 수 없다. 위와 같은 방법으로 더 이상 제거할 정점이 없을 때까지 정점들을 제거한다. 그 후 남은 그래프가 문제에서 요구하는 최대 크기의 부분그래프가 된다. 총 시간복잡도는 $O(M)$이 된다. #include #include using namespace std; #define MAXN 20..

ICPC/2014 대전 2014. 11. 9. 14:14
C. Eureka Theorem

3 이상 1000 이하 자연수 $K$가 주어졌을 때, $K$를 정확히 3개의 삼각수의 합으로 표현할 수 있는지 판별하는 문제다. $K$는 1000 보다 크지 않으므로, 1000 이하의 삼각수 44개를 이용하여, 삼 중 for문으로 가능한지 판별할 수 있다. 테스트케이스 별로 삼 중 for문을 쓰면 시간 초과 될 여지가 있으므로, 전처리를 하면 좋다. #include int T,A[45],D[1001]; int main() { int i, j, k; for (i=1;i

ICPC/2014 대전 2014. 11. 9. 13:47
이전 1 2 다음
이전 다음
공지사항
최근에 올라온 글
  • Bostan Mori 알고리즘
  • 선형점화식 빠르게 계산하기
  • 다항식 나눗셈의 몫을 빠르게 구하는 방법
  • Nexon Youth Programming Cha⋯
최근에 달린 댓글
  • shortcut 만점 코드의 반례가 존재하는 것 같습니⋯
  • 왜 이렇게 되는지 정말 궁금했는데 깔끔하게 정리해주셔서⋯
  • 네, 확인하였습니다. 윗 분께서 말씀해주신 것처럼 원래⋯
  • 댓글 확인이 매우 늦었네요. 네, 확인해보니 그래프 디⋯
Total
257,047
Today
0
Yesterday
50
링크
TAG
  • Boyer-Moore Majority Vote Algorithm
  • IOI2014
  • idea
  • moore
  • Parametric Search
  • Knuth Optimization
  • Segment tree
  • Divide & Conquer
  • z-trening
  • IOI2013
  • vote
  • Tree
  • Dijkstra
  • Greedy Method
  • BOI 2001
  • optimization
  • IOI2011
  • BOI 2009
  • HackerRank
  • USACO
  • dynamic programming
  • majority
  • BOI
  • Splay Tree
  • ioi
  • Algorithm
  • Dynamic Pramming
  • Boyer
  • TRIE
  • IOI2012
more
«   2023/03   »
일 월 화 수 목 금 토
1 2 3 4
5 6 7 8 9 10 11
12 13 14 15 16 17 18
19 20 21 22 23 24 25
26 27 28 29 30 31
글 보관함
  • 2022/11 (3)
  • 2022/10 (1)
  • 2022/09 (1)
  • 2022/08 (1)
  • 2022/07 (1)

Blog is powered by Tistory / Designed by Tistory

티스토리툴바