IOI2016 Day 2 문제 및 해법
0. 문제 패키지 1. paint 길이가 $n$인 문자열이 있고 각 문자는 'X'혹은 '_'이다. 연속한 'X'끼리 묶어 블록이라 부르고, 총 $k$개의 블록이 있다. 문자열의 전체가 주어지지 않고 일부만 주어진다. 그리고 블록의 개수 $k$와 왼쪽부터 순서대로 블록들의 크기가 길이 $k$인 정수배열로 주어진다. 이 때 가능한 문자열이 여러 개가 있을 수 있는데, 가능한 모든 문자열에 대해서 항상 'X'가 놓이는 위치, 그리고 항상 '_'가 놓이는 위치를 구하는 문제다. 모든 위치에 대해서 '_'를 놓을 수 있는지, 'X'를 놓을 수 있는지를 나눠서 계산하면 된다. 아래와 같은 세 개의 DP 배열을 계산해놓으면 편하다.D[i][j] = 1번 블록부터 i번 블록을 1번째 문자부터 j번째 문자까지의 부분 문..
IOI/IOI2016
2016. 8. 16. 21:22
공지사항
최근에 올라온 글
최근에 달린 댓글
- Total
- Today
- Yesterday
링크
TAG
- IOI2014
- Boyer-Moore Majority Vote Algorithm
- z-trening
- IOI2013
- HackerRank
- vote
- BOI 2001
- Segment tree
- Divide & Conquer
- TRIE
- Splay Tree
- IOI2012
- BOI
- BOI 2009
- Boyer
- Algorithm
- optimization
- Greedy Method
- Dijkstra
- IOI2011
- USACO
- dynamic programming
- Dynamic Pramming
- ioi
- majority
- moore
- Tree
- Knuth Optimization
- idea
- Parametric Search
일 | 월 | 화 | 수 | 목 | 금 | 토 |
---|---|---|---|---|---|---|
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 |
글 보관함