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

PS 이야기

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

PS 이야기

검색하기 폼
  • 분류 전체보기 (141)
    • 문제 (1)
    • 해법 (18)
    • 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)
    • 공부 (24)
    • 잡담 (2)
  • 방명록

2018/09/05 (1)
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 다음
이전 다음
공지사항
최근에 올라온 글
최근에 달린 댓글
Total
Today
Yesterday
링크
TAG
  • Dijkstra
  • TRIE
  • Boyer-Moore Majority Vote Algorithm
  • BOI
  • IOI2014
  • ioi
  • dynamic programming
  • optimization
  • USACO
  • Segment tree
  • IOI2013
  • z-trening
  • Greedy Method
  • IOI2012
  • BOI 2001
  • Dynamic Pramming
  • BOI 2009
  • Splay Tree
  • Divide & Conquer
  • vote
  • Tree
  • idea
  • majority
  • Algorithm
  • moore
  • Knuth Optimization
  • HackerRank
  • IOI2011
  • Boyer
  • Parametric Search
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
글 보관함

Blog is powered by Tistory / Designed by Tistory

티스토리툴바