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

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/해외리저널 (6)
2015 Asia - Singapore Regional Contest

문제 링크 E. Association for Computing Machinery N개의 문제가 있는 ICPC 세트가 있다. 각 문제별로 푸는 시간이 주어진다. p번 문제의 First Solve 상을 노려야하기 때문에 p번 문제를 제일 먼저 풀고 제일 좋은 전략으로 문제를 해결할 때, 푼 문제 수와 패널티를 구하는 문제다. 문제는 한 번에 맞는다고 가정한다.p번 문제를 0번지에 놓고 1번지부터 이후를 푸는 시간순서로 정렬한 다음에 순서대로 시간이 300분이 될 때까지 해결한다. #include using namespace std; int N, P; int A[99]; int main() { scanf("%d%d", &N, &P); for (int i=0;i

ICPC/해외리저널 2015. 12. 12. 01:48
2014 Asia - Jakarta Regional Contest

문제 링크 A. Cluster Analysis $N$개의 수가 주어진다. 두 수의 차이가 $K$ 이하면 두 수가 같은 cluster 안에 포함된다. 이 때 생기는 cluster의 개수를 구하는 문제다. $N \leq 100$으로 제한이 굉장히 작다. 따라서 $O(N^2)$ 안에 그래프의 간선을 그릴 수 있고, union-find나 flood-fill을 통하여 cluster의 개수를 세면 된다. #include #include int T, N, K; int A[101], par[101]; int find(int n){ return par[n]==n ? n : (par[n] = find(par[n])); } int main() { int ts = 0, i, j; for (scanf("%d", &T);T--;..

ICPC/해외리저널 2014. 12. 5. 23:08
2014 Benelux Algorithm Programming Contest

코드포스 GYM 링크 A. Avoiding the Apocalypse 내가 아직 풀지 않았다. B. Button Bashing $n$ 종류의 버튼을 눌러 전자레인지의 시간을 맞추는 문제다. 시간은 음수가 될 수 없고, 1시간보다 많이 지날 수 없기 때문에 0~3600 사이에서 BFS를 돌리면 된다. #include #include using namespace std; int T, N, K; int D[3601], A[17]; int main() { int i, j; for (scanf("%d", &T);T--;){ scanf("%d%d", &N, &K); for (i=1;i1, a&1?".5":""); continue; } int ans = 0; for (i=1;i scnt) q -= scnt; for ..

ICPC/해외리저널 2014. 11. 14. 14:23
2014 Asia - Kuala Lumpur Regional Contest

온라인 아카이브 링크 A. The Mountain of Gold? 0번 도시에서 시작하고 시공간을 이동할 수 있는 수단들이 주어졌을 때, 0번 도시의 과거로 돌아올 수 있는지 판별하는 문제다. 일반적으로 $O(NM)$ 시간복잡도의 Bellman-ford 알고리즘은 전체 그래프에서 음수 싸이클이 있는지 판별할 때 쓰인다. 이 문제에서는 0번 도시와 강하게 연결된 연결 요소(0번 도시에서 $x$로 갈 수 있고, $x$에서 0번 도시로 올 수도 있는 $x$들의 집합)에서 음수 싸이클이 있는지 Bellman-ford로 $O(NM)$만에 확인해주면 된다. #include #include #include using namespace std; typedef vector arr; int T, N, M; int D[10..

ICPC/해외리저널 2014. 11. 13. 13:37
2013 Asia - Jakarta Regional Contest

온라인 아카이브 링크 A. Number Assignment 문제에서 주어진 수들을 정렬한 다음 Dynamic Programming를 이용해 해결한다. D[i][j] = 1~i번 수가 있고, 이를 j개의 그룹으로 나눴을 때 가능한 최소 비용 합 점화시은 아래와 같다. D[i][j] = min(D[k][j-1] + A[i] - A[k+1]) (for j-1 ≤ k < i) 총 시간복잡도는 $O(N^2M)$이다. #include #include using namespace std; int T, N, M; int A[101], D[101][101]; int main() { int ts = 0, i, j, k; for (scanf("%d", &T);T--;){ printf("Case #%d: ", ++ts); s..

ICPC/해외리저널 2014. 11. 12. 14:17
2014-2015 ACM-ICPC, NEERC, Southern Subregional Contest

코드포스 GYM 링크 B. Colored Blanket 이 문제에서 입력이 어떻게 들어오든 상관 없이 답은 항상 존재한다. 이 사실을 간략하게 보이겠다. 담요가 $k$개 있고, 색상 종류가 최대 $n$개 일 때 아래와 같은 두 조건을 만족한다. 가장 공이 적은 색상의 공의 개수 ≤ $\frac{k}{n}$가장 공이 많은 색상의 공의 개수 ≥ $\frac{k}{n}$ 위 두 조건을 만족하기 때문에 하나의 키트에 가장 공이 적은 색상의 공들을 모두 넣고 남은 빈 공간을 가장 공이 많은 색상의 공으로 채우면 하나의 키트에는 두 색만 존재하여 문제 조건을 만족한다. 그리고 문제는 귀납적이게 한 단계로 줄어든다. 남은 공의 개수는 $k - \frac{k}{n}$개이며, 색상의 종류는 최대 $n-1$개다. #inc..

ICPC/해외리저널 2014. 11. 12. 13:09
이전 1 다음
이전 다음
공지사항
최근에 올라온 글
  • Bostan Mori 알고리즘
  • 선형점화식 빠르게 계산하기
  • 다항식 나눗셈의 몫을 빠르게 구하는 방법
  • Nexon Youth Programming Cha⋯
최근에 달린 댓글
  • 왜 이렇게 되는지 정말 궁금했는데 깔끔하게 정리해주셔서⋯
  • 네, 확인하였습니다. 윗 분께서 말씀해주신 것처럼 원래⋯
  • 댓글 확인이 매우 늦었네요. 네, 확인해보니 그래프 디⋯
  • 감사합니다~
Total
253,749
Today
16
Yesterday
73
링크
TAG
  • Segment tree
  • BOI 2001
  • Tree
  • vote
  • moore
  • TRIE
  • optimization
  • IOI2013
  • Parametric Search
  • Dijkstra
  • HackerRank
  • IOI2012
  • Knuth Optimization
  • Dynamic Pramming
  • Splay Tree
  • IOI2014
  • Algorithm
  • IOI2011
  • USACO
  • Boyer
  • BOI 2009
  • dynamic programming
  • idea
  • z-trening
  • BOI
  • ioi
  • Boyer-Moore Majority Vote Algorithm
  • majority
  • Greedy Method
  • Divide & Conquer
more
«   2023/02   »
일 월 화 수 목 금 토
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
글 보관함
  • 2022/11 (3)
  • 2022/10 (1)
  • 2022/09 (1)
  • 2022/08 (1)
  • 2022/07 (1)

Blog is powered by Tistory / Designed by Tistory

티스토리툴바