본문 바로가기

ps (문제)

 (13)
ICPC 2021 Seoul Regional I번 Postman 문제 링크: https://www.acmicpc.net/problem/23573 23573번: Postman There is a straight road on which two types trams run. One is an east-to-west tram which moves from east to west, and the other is a west-to-east tram. For each type, several trams run regularly, so anyone can ride the tram in any direction at any time. To www.acmicpc.net $t=2$일 때 풀어보자. 시작점($x=0$)과 끝점이 정해진다. 각각 $s$, $e$라고 하자. 편의상 $s1$,..
CCO23 day1 CCO는 캐나다 국대 선발전으로 퀄리티가 좋고 다른 국대 선발전보다 덜 매워서 재미있게 돌기에 좋은 셋이다. 1. Binaria 문제 요약: 정수 $K$가 주어진다. 길이 $N$의 binary string의 SMS(sub-message sum)을 다음과 같이 정의하자. SMS는 길이 $N-K+1$의 수열이다. SMS의 $i$번째 값은 binary string의 $i$번째부터 $i+K-1$번째 문자의 합이다. $N$, $K$, 그리고 SMS가 주어졌을 때 가능한 binary string의 가짓수를 구하라. 가능한 binary string이 존재함이 보장된다. Full task (25 points) Binary string을 A, SMS를 B라고 하자. SMS가 우리에게 주는 정보는 다음과 같다. $1 \l..
백준 14421 The Kingdom of JOIOI 문제 링크: https://www.acmicpc.net/problem/14421 14421번: The Kingdom of JOIOI For example, in this sample input, we divide the country into two regions as follows. Here, ‘J’ denotes the JOI region, and ‘I’ denotes the IOI region. J J J I J J J I J J I I J I I I The following division does not satisfy the condition because, i www.acmicpc.net 문제를 보고 18871번이 떠오르면서 이차원 dp로 무언가를 해나가고 싶었다. 하지만 안타깝게 풀이는 그렇..
백준 8987 수족관 3 (KOI 2013 고등부 4) 문제 링크: https://www.acmicpc.net/problem/8987 8987번: 수족관 3 입력의 첫 줄은 수족관의 경계에 있는 꼭짓점의 개수 N(4 ≤ N ≤ 300,000)이 주어진다. N은 짝수이다. 수족관의 경계는 항상 꼭짓점 (0, 0)부터 시작한다. 그리고 마지막 꼭짓점은 (A, 0)의 형태로 끝난 www.acmicpc.net 이 문제는 주변에서 웰노운처럼 말하길래 한 번 풀어봤다. 심지어 solved.ac 클래스 문제이다. 그리고 KOI 문제들은 보통 좋은 퀄리티를 보여주기 때문에 풀어보기도 했다. 우선 문제에서 트리를 모델링할 수 있다. 높이가 높은 수평선 순서대로 트리 노드를 만들어주고 노드에 직사각형 넓이를 부여해준다. 그리고 수평선 아래로는 물이 생길 수 없으니까 수평선을 ..
백준 24971 262144 revisited 문제 링크: https://www.acmicpc.net/problem/24971 24971번: 262144 Revisited There are $\frac{6\cdot 7}{2}=21$ contiguous subsequences in total. For example, the minimum possible final number for the contiguous subsequence $[1,3,1,2,1]$ is $5$, which can be obtained via the following sequence of operations: original -> [1,3,1,2,1] www.acmicpc.net 백준에 문제를 푼 사람이 3명 밖에 없다! usaco 정풀이랑 본질적으로는 같은데 접근 방식이 조금 ..

티스토리툴바