JOISC 문제 몇 개를 땅따먹기에서 풀어 보았다. BOJ 24137. 塗り箸 (Chopsticks)옛날 NYPC의 어떤 output only와 상당히 비슷해 보이는 문제이다. 형태를 봤을 때 구간 DP로 진행하는 것이 가장 좋아 보인다. 어떤 구간 $[l, r]$에 대해 최소 비용으로 칠하는 방법을 구한다고 생각해 보자. 먼저 이 구간 전체에 색칠할 색 $c$를 정한다. 다음으로 이 위에 덮어쓸 구간을 정한다. 모든 $c$에 대한 최소 비용을 $[l, r]$에 대한 최소 비용으로 정한다. 이렇게 하면 $O(N^3)$ 풀이가 나온다. 상수가 $52/6$ 정도로 다소 커서 걱정되지만, 짜 보면 문제없이 통과된다.#include using namespace std;typedef long long ll;int..
백준 땅따먹기에서 열린 Hanbyeolforces Global Round 2에 참여해 보았다.링크BOJ 11712. JAG-channel IIBitmask DP를 할 것이다. 그런데 무슨 사람을 썼는지 말고 post가 어떤 순서로 있는지도 저장해야 하는 게 까다롭다.$1 \le N-K \le 3$이라는 특이한 조건 때문에 마지막 사람을 저장하면, 마지막 사람에 포함되지 않은 post의 개수가 최대 $3$개이므로 그 순서들만 따로 저장해도 충분함을 알 수 있다. 이렇게 하고 Bitmask DP를 돌리면 문제를 $O(2^N \times N^2 \times 3!)$ 정도의 시간에 풀 수 있다.#include using namespace std;typedef long long ll;struct State{ ..
Problem Solving Diary #27
BOJ 땅따먹기가 생겼다는 소식을 들어서, 테스트 삼아 몇 개 풀어 보았다. https://blobnom.xyz/room/90BOJ 1626. 두 번째로 작은 스패닝 트리먼저 최소 스패닝 트리를 하나 잡은 뒤, 각 간선에 대해 해당 간선을 자르고 넣을 수 있는 가장 작은 가중치의 간선을 구해 보는 식으로 풀면 될 것 같다. 하지만 단순히 이렇게 하면 같은 가중치의 간선을 고를 수도 있으므로, 최소 가중치를 두 개까지 저장해 주는 식으로 문제를 풀 수 있을 것이다. 처음에 Kruskal 알고리즘 등으로 MST를 찾아 준 후, 사용되지 않은 간선들을 양끝점 사이의 경로에 업데이트해 주고, 세그먼트 트리 등을 이용하는 방식으로 문제를 해결할 수 있다. 여러 가지 사소한 edge case들에 주의해야 할 것 같..
Problem Solving Diary #26
BOJ 13874. Internet Trouble문제수직선 상에 $N$개의 마을이 있고, $K$개의 마을에 인터넷을 설치할 것이다. 하나의 마을에 인터넷을 설치하는 데는 $B$의 비용이 든다.$i$번째 마을에는 $A_i$개의 집이 있으며, 각 집과 인터넷을 연결하는 케이블을 설치해야 한다. 이때 $i$번 마을의 집 하나와 $j$번 마을의 인터넷을 연결하는 비용은 $|i-j|\times C$이다.$1 \le K \le N$인 모든 $K$에 대해, $K$개의 마을에 인터넷을 설치할 때 드는 최소 비용을 구하시오.$1 \le N \le 6000$풀이일단 문제의 생김새를 보아 DP로 푸는 것 같다. 그러나 상태 전이를 어떻게 시켜야 할지가 잘 보이지 않는다. 모든 구간 $[l, r]$을 하나의 인터넷으로 덮는 ..
랜덤한 ICPC 문제 몇 개를 뽑아 풀어보았다.BOJ 17551. Jumbled Journey문제를 solvable하게 만들기 위해 이상한 제한들이 덕지덕지 붙었는데,$i$에서 $j$로 가는 비용 $c$인 간선이 있다면, 이 간선을 통하지 않는 모든 경로의 길이가 $c$보다 크다.어떤 두 정점 $x$와 $y$를 연결하는 서로 다른 경로는 최대 $1000$개이다.따라서, 일단 $O(1000n^2)$ 짜리 (여기에 아마 로그가 붙을 수도 있는) 풀이를 생각하는 것이 가장 합리적인 것으로 보인다.일단 몇 가지 사실을 관찰하고 가면 편리하다.입력에 주어지는 행렬을 $a_{ij}$라고 하자. 또한 $i$에서 $j$로 가는 간선이 있다면 $c_{ij}$를 그 비용으로, 아니라면 $c_{ij} = -1$이라고 정의하..
인터랙티브 문제와 투스텝 문제 몇 개를 풀어보았다.BOJ 31975. Staring Contest만점을 받기 위해서는 $q \le n + 25$회 이내에 문제를 해결해야 한다. 데이터가 사전에 결정되어 있고 제한이 애매하므로 무작위화 알고리즘을 고려해볼 수 있다. 어떤 사람 $s$를 정하고, 이 사람과 다른 사람들에 대한 쿼리를 계속 날린다. 날리다가 이미 들어온 값 $v$가 또 들어오는 시점이 있을 것이다. 두 사람의 실력이 다르므로 이 값은 사람 $s$의 실력이라고 생각할 수 있을 것이다. 즉, 사람 $s$의 실력을 $v$로 고정할 수 있다. 또한 앞에서 쿼리를 날렸을 때 $v$보다 작은 값이 들어온 경우 그 값들을 해당 사람들의 실력으로 확정할 수 있을 것이다. 이제 $v$라는 결과가 나온 두 사람..
BOJ 17670. 난난을 $N$조각으로 잘랐을 때, 마지막 난을 누가 가져가야 할 지 생각해 보자. 각 사람별로, 왼쪽부터 $P_i$만큼의 난을 먹었을 때 전체 행복도의 $\frac{i}{N}$만큼을 얻게 되는 $P_i$를 구하자. 이때 $P_{N-1}$이 가장 큰 사람에게 맨 오른쪽 조각을 $P_{N-1}$부터 잘라서 주면, 마지막 사람은 $\frac{1}{N}$만큼의 행복도를 얻고, 남은 사람들 모두 남은 조각들로 최소 $\frac{N-1}{N}$의 행복도를 얻을 수 있는 상태가 된다. 이제 여기서 다음 사람은 아직 난을 받지 못한 사람 중 $P_{N-2}$가 가장 큰 사람에게 주고, 그 다음 사람은 $P_{N-3}$이 가장 큰 사람에게 주고, 이를 반복하면 모든 사람에게 항상 조건을 만족하도록 난..
조이슥 맛 셋을 하나 돌고 싶었는데, 리프가 추천해줘서 풀었다. 딱히 시간을 재면서 풀진 않았다.https://codeforces.com/contest/1943A. MEX Game 1Alice가 $[0, v]$ 사이의 모든 값을 가져갈 조건이 다음과 동치임을 보일 수 있다.$[0, v]$ 사이의 모든 값이 1개 이상 있다.$[0, v]$ 사이의 값 중 $a_1, \cdots, a_n$에 정확히 1개 있는 값이 최대 하나이다.증명은 단순하다. 저 조건을 만족하기만 하면, Alice는 현재 남아 있는 가장 적은 값을 가져가는 그리디로 모든 값을 가져갈 수 있다. 반면, 저 조건을 만족하지 않는다면, Bob은 정확히 1개 있는 여러 개의 값 중 하나를 소진해 Alice가 해당 수를 가져가지 못하게 막을 수 있..