79brue의 PS 블로그

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]$을 하나의 인터넷으로 덮는 ..

이번 문제들은 Round 1보다 까다로웠던 것 같다. A1, A2, C를 풀어 85등으로 Round 3에 진출하였다. B는 답안을 제출했으나 끝나고 틀린 것으로 밝혀졌다. A1. Cottontail Climb (Part 1)문제의 조건을 만족하는 수의 개수가 매우 적으므로 (45개로 기억하지만 정확하지 않다), 모두 만들어둔 뒤 나이브하게 계산하면 문제를 해결할 수 있다.#include using namespace std;typedef long long ll;int t;ll a, b;ll m;vector vec;void init();int main(){ init(); scanf("%d", &t); for(int tc=1; tc=s; i--) v = v * 10 + i; ..

랜덤한 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$이라고 정의하..

그동안 해커컵을 잘 못하다가 미국에 오니 시간대가 맞아서 편하게 할 수 있게 되었다. 앞 4문제를 풀어 69등으로 Round 2에 진출하였다.A. Subsonic Subway이 문제는 $N$가지 조건이 있고, 그 중 $i$번째 조건은 $i$번 위치에 도달하는 시간이 $A_i$ 이상 $B_i$ 이하라고 해석할 수 있다. 여기에서 속도에 대한 범위를 얻을 수 있다. 속도는 $\frac{i}{B_i}$ 이상 $\frac{i}{A_i}$ 이하가 된다. 이제 이 $N$개의 구간들의 교집합을 모두 구한 뒤, 해당 교집합이 공집합인지, 공집합이 아니라면 왼쪽 끝점 (가능한 최저 속도)가 얼마인지를 구해 주면 된다. 실수형으로 관리를 해도 통과를 할 수 있을 것 같긴 한데, 나는 안전하게 분수 자료형을 만들어서 해결했..

A. Walk the Line최적의 전략은 다음과 같다.$S_i$가 가장 작은 사람 한 명을 고른다.왼쪽 구간에 사람이 두 명 이하가 될 때까지 다음을 반복한다.$S_i$가 가장 작은 사람, 그리고 왼쪽에 남아 있는 사람 중 아무나 함께 오른쪽으로 이동한다. 이때 $S_i$가 더 큰 사람이 wheelbarrow에 탑승한다.$S_i$가 가장 적은 사람이 wheelbarrow를 타고 돌아온다.남은 사람이 오른쪽으로 이동한다.이때 걸리는 시간은 $\min S_i \times \left( \max(n, 2) - 3 \right)$인데, 이보다 답이 더 작아질 수는 없다. $\times$ 오른쪽의 항은 최소 이동 횟수인데, 한 번의 이동이 $\min S_i$보다 짧을 수 없기 때문이다.#include using ..

11주간의 마라톤 끝에 드디어 450km를 찍었다. 특별한 동기가 없는 한 더 이상 마라톤을 지속하지는 않을 것 같다.앞으로 마라톤을 풀지 않으니 점점 난이도가 떨어질 텐데, 난이도 변경폭을 최소로 바꿔 놓으려고 한다. A. Расписание기초적인 그리디 문제로, 가장 작은 수부터 차례대로 $1$부터 수를 붙여 주면 된다. 나는 $O(n^2)$에 풀었고, 그 이하의 시간 복잡도로도 풀 수 있다.#include using namespace std;typedef long long ll;int n;int arr[102];int ans[102];int main(){ scanf("%d", &n); for(int i=1; iB. Crazy tea party원탁에 있는 $n$개의 수들을 최소 횟수의 (..

랜덤 마라톤은 계속 나를 한계로 몰아붙이는 것 같다. 아무래도 랜덤 문제가 뽑히다 보니 실력 향상을 크게 느끼지는 못하고 있고, 그나마 승부욕 때문에 계속 푸는 것 같다. 이제는 재미로 문제를 푼다기보다 압박처럼 느껴지는 부분이 더 많은데, 450km를 달성하면 아마 그만둘 것 같다. 리롤 기록: 1회(B, E, H), 2회(H), 3회(H)A. Fair and Square (Small)나이브를 돌려 보면 이 성질을 만족하는 수가 거의 없다. 리스트를 precomputation해 두면 Large1 문제까지도 쉽게 풀 수 있다. precomputation으로 풀었기 때문에 정답 코드를 첨부하지 않는다.B. Kind of a Blur문제를 잘 읽어 보면 단순히 연립방정식을 풀면 되는 문제라는 것을 알 수 있..

점점 다이아가 많아지고 있다. 아무래도 몇 주 정도만 더 하게 될 것 같은데, 얼마 뒤에 루비가 나올 수도 있을 것 같다.리롤 기록: 1회(F, H), 2회(H)A. Make America Grade Again역시 문제에 적힌 것을 그대로 구현하면 되는 문제이다.l,h,p,e,n=map(int,input().split())dct = {'l': [0, 0], 'h': [0, 0], 'p': [0, 0], 'e': [0, 0]}for i in range(n): s = list(input().split()) s[0] = s[0].lower() r = s[-1].split('/') dct[s[0][0]][0] += int(r[0]) dct[s[0][0]][1] += int(r[1])a..