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

PS 이야기

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

PS 이야기

검색하기 폼
  • 분류 전체보기 (134)
    • 문제 (1)
    • 해법 (15)
    • IOI (42)
      • IOI2011 (6)
      • IOI2012 (5)
      • IOI2013 (7)
      • IOI2014 (8)
      • IOI2015 (3)
      • IOI2016 (2)
      • 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)
    • 공부 (21)
    • 잡담 (1)
  • 방명록

2018/09 (2)
IOI 2018 Day 2 문제 및 해법

문제: 공식 홈페이지채점: Yandex 1. doll 0번 정점을 시작점이라고 부르고 0번 정점은 나가는 간선이 정확히 1개다. 1번부터 M번까지 번호가 매겨진 나가는 간선이 정확히 1개인 트리거 정점 M개가 존재한다. 그리고 스위치라고 불리는 정점들은 번호가 음수로, 개수가 S개일 때, -1번부터 -S번까지 번호가 매겨진다. 스위치 정점은 나가는 간선이 정확히 2개이며 스위치 상태가 'X'일 때는 'X'로 표시된 간선으로 나가게 되며, 스위치 상태가 'Y'일 때는 'Y'로 표시된 간선으로 나가게 된다. 정점을 나가면서 동시에 스위치 정점의 상태가 뒤집힌다. 초기 0번 정점에서 이동을 시작하며, 이동을 하다가 다시 처음 0번 정점으로 돌아오는 순간 모든 스위치 정점의 상태는 'X'여야하며 트리거 정점은 ..

IOI/IOI2018 2018. 9. 7. 17:09
IOI 2018 Day 1 문제 및 해법

문제: 공식 홈페이지 채점: Yandex 1. combo 길이가 N인 'A', 'B', 'X', 'Y'로만 이루어진 문자열 S가 있다. 문자열 S의 첫 글자로 나타나는 알파뱃은 오직 한 번만 등장한다. press(p)라는 함수를 문제에서 제공하는데, press(p)에서 p는 길이가 4N 이하인 문자열이며, p의 부분문자열 중 문자열 S의 prefix 중 하나와 동일하며 가장 긴 문자열의 길이를 반환한다. 문제는 적은 횟수의 press(p) 함수 호출을 통해 문자열 S의 내용을 정확하게 알아내는 것이다. 여담으로, p의 부분문자열 중 문자열 S의 prefix 중 하나와 동일하며 가장 긴 문자열의 길이란, 즉, 문자열 S를 패턴이라고 생각하고 p를 전체 문자열이라고 생각했을 때, KMP 알고리즘의 실패 함수..

IOI/IOI2018 2018. 9. 5. 11:14
이전 1 다음
이전 다음
공지사항
최근에 올라온 글
  • Google Code Jam 2022 Rou⋯
  • Hu-Tucker Algorithm
  • Skew Heap
  • Nexon Youth Programming⋯
최근에 달린 댓글
  • gumgood 님이랑 ㅇㅇ 님이 말⋯
  • 왜 4N개가 되는지 잘 모르겠⋯
  • 그 부분은 서브태스크2에 대⋯
  • 지금 적혀있는 것이 맞습니다.
Total
227,245
Today
106
Yesterday
92
링크
TAG
  • USACO
  • Parametric Search
  • BOI
  • moore
  • BOI 2009
  • Dynamic Pramming
  • Divide & Conquer
  • idea
  • Dijkstra
  • TRIE
  • Tree
  • Splay Tree
  • IOI2012
  • Algorithm
  • Boyer
  • BOI 2001
  • IOI2011
  • dynamic programming
  • IOI2014
  • IOI2013
  • Knuth Optimization
  • ioi
  • vote
  • z-trening
  • Boyer-Moore Majority Vote Algorithm
  • Greedy Method
  • Segment tree
  • HackerRank
  • majority
  • optimization
more
«   2018/09   »
일 월 화 수 목 금 토
            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            
글 보관함
  • 2022/05 (3)
  • 2021/08 (1)
  • 2021/03 (2)
  • 2020/09 (7)
  • 2019/05 (2)

Blog is powered by Tistory / Designed by Tistory