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

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/2015 이후 한국대회 (6)
2017년 대학생 프로그래밍 경시대회 풀이

문제 링크 D. Happy Number 문제에 적혀 있는 함수 $f$가 있다. $f(f(f(...f(n))))$을 했을 때, 1이 되는지를 구하는 문제다.입력으로 주어지는 수는 최대 1,000,000,000인데, 큰 수가 주어진다하더라도 $f(n)$의 결과값은 작다. 때문에 이 문제는 함수 $f$를 구현하고 결과값이 1이 되는지만 확인하는 간단한 문제가 된다. #include using namespace std; int N; int main() { set vis; scanf("%d", &N); while (N > 1){ if (vis.count(N)){ puts("UNHAPPY"); return 0; } vis.insert(N); int nxt = 0; for (int v=N;v;v/=10) nxt +=..

ICPC/2015 이후 한국대회 2017. 11. 16. 00:22
2016년 대학생 프로그래밍 경시대회 풀이

문제 링크 I. Robot 로봇은 초기에 동쪽을 바라보고 있고, $(0, 0)$ 위치에 있다. 회전하는 명령과 앞으로 이동하는 명령이 주어졌을 때, 주어진 정사각형 범위를 벗어나는지 아닌지 확인하고 벗어나지 않으면 최종 위치를 출력하는 문제다. 단순한 구현 문제이므로 설명은 생략한다. #include using namespace std; int yy[] = {0, -1, 0, 1}, xx[] = {1, 0, -1, 0}; int M, N; int y, x, dir; int main() { scanf("%d%d", &M, &N); for (int i=1;i M || x > M){ puts("-1"); return 0; } } printf("%d %d\n", x, y); } G. Percolation $M ..

ICPC/2015 이후 한국대회 2016. 11. 9. 20:07
2016년 대학생프로그래밍 경시대회 인터넷예선 풀이

문제 링크 I. Q-Index $n$개의 논문들에 대한 인용횟수가 주어지고, $k$번 이상 인용된 $k$편의 논문이 있고, 나머지 $n-k$편의 논문은 모두 인용횟수가 $k$이하일 때, Q-Index는 $k$라고 얘기한다. 가능한 Q-Index 중 가장 큰 값을 구하는 문제다. 매우 쉬운 문제라 0이상 $n$이하의 $k$를 정한 뒤, 실제로 $k$가 Q-Index가 되는지 확인하는 $O(n^2)$ 방법과 인용횟수 배열을 내림차순으로 정렬한 뒤에 이를 더 빠르게 계산하는 $O(n \lg n)$ 방법 두 가지가 있다. #include using namespace std; int N; int A[1001]; int main() { scanf("%d", &N); for (int i=1;i= i){ printf(..

ICPC/2015 이후 한국대회 2016. 10. 2. 21:35
2016년 전국 대학생 프로그래밍 대회 동아리 연합 여름 대회

문제 링크 E. 닉네임에 갓 붙이기 $N$개의 닉네임이 음절 단위로 쪼개져 주어진다. 첫 음절을 제외하고, 맨 앞에 "god"을 붙여 출력하는 문제다. 줄 별로 입력받고 입력 받은 문자열을 공백으로 나누어 문자열 배열로 만들어주면 된다. C, C++에서 이는 strtok 함수를 통해 간단히 해결할 수 있다. #include using namespace std; int T; char buf[999]; int main() { for (scanf("%d ", &T);T--;){ fgets(buf, 997, stdin); bool sw = 0; printf("god"); for (char *pt=strtok(buf, " \n\r");pt;pt=strtok(0, " \n\r")){ if (sw) printf(pt..

ICPC/2015 이후 한국대회 2016. 8. 24. 18:22
2015년 대학생 프로그래밍 경시대회 풀이

문제 링크 L. Wheel of Numbers 숫자 N개가 적힌 원판이 있다. 원판에 다트를 던져 한 곳을 맞춘다. 그 다트를 기준으로 시계방향으로 숫자 M개를 읽어 수 Z를 만든다. X ≤ Z ≤ Y 라면 점수를 획득한다. 원판과 X, Y가 주어졌을 때, 점수를 획득하는 경우의 수를 구하는 문제다.아주 간단한 구현 문제다. M ≤ 9이므로, 64bit 정수형을 사용해서 X, Y, Z를 표현할 수 있다. #include using namespace std; typedef long long lld; int T, N, M; int A[100]; lld X, Y; int main() { for (scanf("%d", &T);T--;){ scanf("%d%d", &N, &M); X = Y = 0; for (in..

ICPC/2015 이후 한국대회 2015. 11. 12. 16:12
2015년 대학생프로그래밍 경시대회 인터넷예선 풀이

문제 링크 A. Awkward Group $N$개의 정점이 간선에 가중치가 있는 완전 그래프가 있다. 정점의 전체 집합 $P$의 부분 집합 $F$가 있다고 했을 때,문제에 적힌 조건을 만족하는 $F$의 개수를 구하는 문제다. 초기에 간선이 전혀 없는 그래프를 생각하자. 가중치가 작은 간선들부터 차례로 추가해나간다. 간선 하나를 추가할 때마다 그 간선이 속한 연결 요소(connected component)가 완전 그래프인지 확인한다. 만약 완전 그래프라면 그 연결 요소에 있는 정점들이 문제의 조건을 만족하는 집합 $F$가 됨이 자명하다. 완전 그래프인지 확인하는 것은 연결 요소 내의 정점 개수와 간선 개수를 비교하여 O(1)에 해결 가능하다. 만약 가중치가 같은 간선이 여러 개라면 한 번에 추가해야한다. ..

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

티스토리툴바