kth990303의 코딩 블로그

이번에도 UCPC 문제 포스팅이다. 트라이 구현코드를 바꾼 후, 처음으로 해결해본 응용 문제인데, 구현코드가 익숙하지 않아서였는지 꽤나 고생을 했던 문제이다. 문제는 아래와 같다. https://www.acmicpc.net/problem/17365 17365번: 별다줄 먼 옛날에 문래빗어라는 언어가 있었다. 문래빗어에는 여러 개의 단어가 있었고, 사람들은 단어들을 나열해서 문장을 만들었다. 예를 들어 "ryan", "is", "lion" 세 단어로 "lion is ryan is lion"이라는 문 www.acmicpc.net 의식의 흐름 및 해설 예제입력1의 결과가 왜 109인지 직접 생각해보면 문제 이해에 도움이 된다. 해석하려는 단어가 aaaa 일 때, a는 예제입력1의 세 단어 모두 가능하므로 3*..

예전에 UCPC 연습용으로 풀다가 해결하지 못한 문제이다. 기댓값 표현이 겁을 한사발 먹게 해주기도 했고, 그 때 당시 dp를 어려워했기 때문이 아닐까 생각된다. 문제는 아래와 같다. https://www.acmicpc.net/problem/17367 17367번: 공교육 도박 공교육의 수호자 수찬이는 공교육의 정수라고 할 수 있는 한국정보올림피아드의 문제를 가지고 게임을 하려고 한다. 수찬이는 2010년도 한국정보올림피아드 시·도 지역본선 중등부 1번 문제를 www.acmicpc.net 의식의 흐름 및 해설 먼저, 주사위값마다 행동에 영향을 끼치는 것은 확실하다. 마침, 주사위도 최근 3개의 결과만 영향을 미치기 때문에 dp[100000+1][6+1][6+1][6+1]의 재귀 탑다운dp로 접근해볼 수 ..

학교랭킹 랭작을 위해 풀은 문제인데, 꽤나 아이디어 면에서 얻어갈 게 많았다. 문제는 아래와 같다. https://www.acmicpc.net/problem/17038 17038번: The Great Revegetation (Silver) A lengthy drought has left Farmer John's $N$ pastures devoid of grass. However, with the rainy season arriving soon, the time has come to "revegetate". In Farmer John's shed, he has two buckets, each with a different type of grass seed. He wants to plant g www.acm..

재밌어보이는 그래프 문제. 문제는 아래와 같다. https://www.acmicpc.net/problem/2311 2311번: 왕복 여행 첫째 줄에 나라의 개수 N과 도로의 개수 M이 주어진다. (3 ≤ N ≤ 1,000, 2 ≤ M ≤ 10,000) 둘째 줄부터 M개의 줄에 걸쳐 각 도로를 나타내는 세 자연수 A, B, C가 주어진다. 이는 A번 나라와 B번 나라가 www.acmicpc.net 의식의 흐름 및 해설 1->N->1로 돌아가는데, 이미 방문했던 길은 방문할 수 없다. 일단 가중치가 존재하기 때문에 dijkstra나 binary_search를 적절히 이용해볼까 생각이 들었다. 그러나, dijkstra로 1->N까지의 최소 시간은 구한다 치나, N->1로 다시 돌아갈 때, 중복방문을 허용하지 ..

마찬가지로 solvedac 빼빼로 이벤트때문에 막대과자 얻으려고 둘러보다가 발견한 문제. 근데 정말 문제를 잘만드신 것 같다. 문제는 아래와 같다. https://www.acmicpc.net/problem/14950 14950번: 정복자 서강 나라는 N개의 도시와 M개의 도로로 이루어졌다. 모든 도시의 쌍에는 그 도시를 연결하는 도로로 구성된 경로가 있다. 각 도로는 양방향 도로이며, 각 도로는 사용하는데 필요한 비용이 존재 www.acmicpc.net 이 문제는 알고리즘 분류를 보지 말고 풀길 바란다. 오로지 알고리즘 분류를 떠올리는 난이도 때문에 티어가 올라간 문제라 생각된다. 의식의 흐름 및 해설 1번부터 시작해야되는데, 최소비용으로 접근해야 되니까 BFS를 생각해봤다. BFS는 간선 비용이 있기 ..

solvedac 빼빼로 이벤트 중, 막대과자가 부족해서 골드 문제 아무거나 랜덤으로 뽑아서 풀게 된 문제. 문제는 아래와 같다. https://www.acmicpc.net/problem/22863 22863번: 원상 복구 (large) 수가 적혀있는 $P_1, P_2, ..., P_N$ $N$개의 카드가 있다. 1부터 N까지 수가 하나씩 존재하는 $D_1, D_2, ... , D_i , ... D_N$ 가 있다. 이때 $D_i$는 $P_{D_i}$ 값을 $i$ 번째로 가지고 오는 것을 의미한다. 이러한 www.acmicpc.net 의식의 흐름 및 해설 문제가 정말 permutation_cycle(순열사이클)처럼 생겼다. 근데 K가 최대 1e15니까 K번 순열 사이클을 돌리는 단순한 풀이는 안되겠다. 순열..

엄청나게 높은 난이도임에도 불구하고, KOI 고등부도 아닌 중등부에 나와서 굉장히 유명해진 문제. 이 문제의 하위호환이 https://www.acmicpc.net/problem/16993 인데, 이것마저도 나에겐 굉장히 어려웠다. 위 문제를 푼 이유가 바로 '금광'을 해결하기 위해서일 정도로 이 문제는 웰노운인데, 이번 기회에 복습 겸 포스팅해보려 한다. 문제는 아래와 같다. https://www.acmicpc.net/problem/10167 10167번: 금광 첫 줄에는 금광들의 개수 N (1 ≤ N ≤ 3,000)이 주어진다. 이어지는 N개의 줄 각각에는 금광의 좌표 (x, y)를 나타내는 음이 아닌 두 정수 x와 y(0 ≤ x, y ≤ 109), 그리고 금광을 개발하면 얻게 되는 이 www.acmi..

개인적으로 꽤 어렵게 느껴졌기 때문에 풀고난 후 티어를 보고 깜짝 놀랐다. 내가 정점/간선 인덱스를 헷갈리게 하는 유형에 약해서 그런진 모르겠지만, 나는 G1~P5 급이라 생각한다. 하지만 그만큼 배울점도 많았던 문제. 문제는 아래와 같다. https://www.acmicpc.net/problem/20553 20553번: 다오와 디지니의 데이트 첫 줄에 두 정수 $N$과 $T$가 주어진다. ($2 \le N \le 100\,000$, $1 \le T \le 10^{9}$) 두 번째 줄에 $N$개의 정수가 공백으로 구분되어 주어지며, $i$번째 수는 $h_i$를 의미한다. ($-10^9 \le h_i \le 10^9$, $h_1 = 0$) www.acmicpc.net 얘들아 근데 너네 데이트는 어떻게 하니..

2009 KOI 고등부 1번 문제이다. 문제는 아래와 같다. https://www.acmicpc.net/problem/2487 2487번: 섞기 수열 A1, A2, …, AN으로 표시된 N 개의 카드를 정해진 방법으로 섞고자 한다. 그 섞는 방법은 1에서 N까지의 숫자로 이루어진 수열로 표시된다. 이 수열을 섞기 수열이라 하자. 섞기는 현재 가지고 있는 www.acmicpc.net 문제를 요약하자면, 섞기 전 index에 위치한 value값을 섞은 후의 index로 위치하게 할 때, 맨 처음 순서와 똑같은 순서로 놓이게 되는 때는 몇 번째인지 구하는 문제이다. 의식의 흐름 및 해설 섞기 전 index에 위치한 value가 섞은 후에는 index에 위치하게 된다. 이를 그림으로 나타내면 아래와 같다. 위 ..

문제는 아래와 같다. https://www.acmicpc.net/problem/11406 11406번: 책 구매하기 2 총 N명의 사람이 책을 구매하려고 한다. 각 사람은 1번부터 N번까지 번호가 매겨져 있고, 각 사람이 사려고하는 책의 개수는 A1, A2, ..., AN권이다. 이 책을 판매하는 온라인 서점은 총 M곳이 있다.각 www.acmicpc.net 예전에 애드몬드 카프 알고리즘 공부 후, flow 기본문제들을 거의 다 풀어버린 줄 알았는데, 다행히 아직 안 푼 문제가 있어서 디닉을 적용해보았다. 의식의 흐름 및 해설 얼마나 많이 구매자들에게 책을 전달할 수 있을지, 그리고 구매자와 서점이 명확한 이분그래프 모양을 띄기 때문에 flow문제임을 확인할 수 있다. N, M 0) { e.c -= f;..