이동식 저장소

친구가 학교 대회에서 낸 문제이다. 27979번: 볼링장 아르바이트 건구스는 볼링장에서 아르바이트하고 있다. 건구스의 퇴근 전 마지막 업무는 $N$개의 볼링공의 순서를 볼링공의 무게 순서대로 정리하는 것이다. 즉, 모든 $i, j\ ( 1 \le i < j \le N )$ 에 대해 $w_i \le w www.acmicpc.net 공을 뺄 때는 어디에서나 뺄 수 있지만, 넣을 때는 맨 앞에만 넣을 수 있다. 주어진 정수를 오름차순으로 정렬하려면 공을 최소 몇 번 빼야 하는지 구하면 된다. 어디선가 많이 본 세팅인데.. LIS 문제인가 싶어서 생각해 봤으나 아니었다. 정렬 말고는 딱히 알고리즘은 없는 듯하다. 예제를 관찰한 결과, $i$번 공 앞에 $i$번 공보다 큰 공 $j$가 있다면 $i$번 공과 $k

Acka는 ``악어``라고 읽는다. 모 랭커분의 닉네임이다. 12996번: Acka 첫째 줄에 앨범에 포함된 곡의 개수 S와 dotorya, kesakiyo, hongjun7이 불러야 하는 곡의 수가 주어진다. (1 ≤ S ≤ 50, 1 ≤ dotorya, kesakiyo, hongjun7 ≤ S) www.acmicpc.net 세 사람이 불러야 하는 곡의 개수 $a$, $b$, $c$가 주어질 때, 만들 수 있는 앨범의 개수를 구해 보자. 뭔가 고등학교 확통 느낌이 나는 문제이다. 일단 특이 케이스부터 먼저 살펴보자. $a+b+c

1572번: 중앙값 중앙값이란, 수열을 정렬했고, 그 크기가 N일 때, 1부터 시작해서 (N+1)/2번째 있는 원소가 그 수열의 중앙값이다. 예를 들어, {1, 2, 6, 5, 4, 3}에서는 3이고, {11, 13, 12, 15, 14}에서는 13이다. 오세준은 1 www.acmicpc.net 길이 $N$인 수열에 대해 중앙값 내지는 중간값을 연속적으로 구하는 문제이다. 잘 알려진 대로(하지만 모르면 모르는) 세그먼트 트리를 응용하여 풀 수 있다. 값의 범위가 $[0,~65536]$으로 꽤 작아서, 각 값이 등장한 횟수를 저장해 놓은 뒤 합이 mid가 되는 최소의 인덱스를 찾으면 된다. 나는 ``std::multiset`` 두 개를 사용하여 풀었다. 길이 $K$인 구간을 ``left``와 ``right..

1615번: 교차개수세기 첫 줄에 N과 간선의 개수 M이 주어진다. 그 다음 줄부터 M+1번째 줄까지 두 개의 수(i, j)가 주어지는데 이는 왼쪽 그룹의 i번 정점과 오른쪽 그룹의 j번 정점을 연결하는 간선이 있다는 의미이다. www.acmicpc.net 뭔가 많이 본 듯한 문제이다. 어디서 봤나 했더니 2568번 전깃줄 문제와 매우 유사하다. 물론 풀이가 유사하다는 건 아니고 그림이 비슷하다는 소리. 이 문제에서는 전깃줄이 교차하는 횟수를 세어야 한다. 문제에 두 전깃줄이 교차하는 조건이 주어져 있는데, 계산의 편의를 위해 왼쪽에 있는 정점을 오름차순으로 살펴보면서, 각 정점의 전깃줄이 다른 전깃줄과 몇 번 교차하는지 계산해 보자. 왼쪽 정점 $i$와 오른쪽 정점 $j$에 연결된 전깃줄을 $(i, ~..

14719번: 빗물 첫 번째 줄에는 2차원 세계의 세로 길이 H과 2차원 세계의 가로 길이 W가 주어진다. (1 ≤ H, W ≤ 500) 두 번째 줄에는 블록이 쌓인 높이를 의미하는 0이상 H이하의 정수가 2차원 세계의 맨 왼쪽 위치 www.acmicpc.net 블록 사이에 빗물이 얼마나 고이는지 구하는 문제이다. 2차원 공간의 바닥은 막혀 있다고 가정한다. 바닥이 막혀 있으므로 물이 빠져나갈 수 있는 방향은 왼쪽 또는 오른쪽이다. 설마 물이 위로 증발하지는 않을 것이고.. 그렇다면 블럭을 제외한 모든 빈 공간을 물로 채운 후, 왼쪽 또는 오른쪽으로 빠져나가는 물을 제외하면 된다. 2차원 공간에 다음과 같이 물을 채운다. 검은색은 블록이다. 왼쪽과 오른쪽으로 물이 얼마나 빠져나갈 수 있는지 시뮬레이션해 ..