코드포스 Codeforces Round #485 (Div.2) 이번꺼는 버추얼후기. A. Infinity Gauntlet map을 적극 활용하자. map이 없다고? 거짓말하지마세요 그런언어가 어딨어. source : https://codeforces.com/contest/987/submission/65464832 B. High School: Become Human xy 과 yx을 직접 구해서 비교하려면 당연히 터진다. 양 변에 로그를 씌워서 ylogx와 xlogy를 비교하자. source : https://codeforces.com/contest/987/submission/65465055 C.
코드포스 Codeforces Round #601 (Div.2) A. Changing Volume abs(a-b)를 5로 최대한 채우고, 나머지를 2로 최대한 채우고, 마지막을 1로 채우는 그리디. source : https://codeforces.com/contest/1255/submission/65352313 B. Fridge Lockers 구데기문제. 원래 조건이 2<=n<=1000, 1<=m<=2000 이었는데 m>n 일때 정해에서 잘못된 답을 내놓는 것이 대회중에 발견되어서 중간에 급하게
백준 BOJ 17143 낚시왕 문제 : https://www.acmicpc.net/problem/17143 아마 코테시즌이 되면 백준에 질문이 가장 많이 올라오는 문제가 아닐까싶은 문제, 낚시왕이다. 개인적으로 기출로 나왔던 시뮬레이션 문제들이 대부분 디스크립션을 한 번에 알아보기 힘들어서 늘 몇 번씩 읽어봤었는데 이 문제는 바로 로직을 구성할 수 있을 정도여서 코드를 짜는데 그렇게 오래걸리지는 않았다. 이런 시뮬레이션 문제에서
자료구조 Persistent Segment Tree 다음과 같은 문제를 생각해보자. 크기가 N인 배열에서 주어지는 [l,r] 범위들의 합을 각각 구하여라. 어디서 본 것같지 않은가? 그렇다. hld 글을 시작했던 그 문제이다. 저 글에서 우리는 이 문제에 update를 얹고 배열을 트리형태로 바꾸었을 때 어떻게 처리해야할 지를 다루었는데 이번에는 문제를 약간 바꿔보겠다. 크기가 N인 배열에서 주어지는 [l,r] 범위의
코드포스 Codeforces Round #598 A. Payment Without Change 요약 : q개의 케이스가 주어지고 각 케이스마다 n의 가치를 가진 동전 a개와 1의 가치를 가진 동전 b개가 주어진다. 이 때 이 동전들의 가치의 합을 정확히 S로 만들 수 있는가? min(S/n,a)*n + b >= S 인 경우 가능하고 그 외의 경우 불가능하다. S를 넘지 않는 선에서
백준 BOJ 17274 카드 공장 문제 : https://www.acmicpc.net/problem/17274 지문이 짧고 간단하다. 앞면은 A, 뒷면은 B로 카드쌍이 주어지는데 K라는 숫자가 주어질 때마다 전체 카드 중 현재 보이고 있는 면이 K이하인 카드를 모두 뒤집어주면 된다. 가장 먼저 떠오르는 방법은 매 쿼리마다 전체 카드를 보면서 하나씩 뒤집어주는 것이지만 전체 카드의 개수와 쿼리의 개수는 각각
알고리즘 Heavy Light Decomposition 다음과 같은 문제를 생각해보자. 크기가 N인 배열에서 주어지는 [l,r] 범위들의 합을 각각 구하여라. 이 글을 찾아올 정도의 사람이라면 아마 일일이 더하는 것이 아니라 누적합을 구해서 각 쿼리를 O(1)에 처리할 것이다. 저 배열에 단일점 업데이트가 있다면 세그먼트 트리를 쓸 것이고, 구간 업데이트가 있다면 Lazy propagation을 얹어서 쓸 것이고.
백준 BOJ 15481 그래프와 MST 문제 : https://www.acmicpc.net/problem/15481 어떤 임의의 연결그래프가 주어졌을 때, 모든 간선에 대해서 해당 간선이 포함되는 MST의 가중치의 합을 구하라는 문제이다. 잘 생각해보면 간선을 MST에 이미 포함된 간선과 포함되지 않은 간선으로 나눌 수 있는데, 이 때 MST에 이미 포함된 간선에서의 MST 가중치 합은 너무 당연하게도 전체 MST의 가중치