노력하는 공대생의 공부일지

13536을 풀며 머리를 탁 치고 짠 후 24915를 풀었다. 문제 풀이에 비하인드가 있는데, 24915는 한 이틀정도 고민한 문제였다. 고민했는데 모르겠어서 풀이를 찾아보려 해도 최근 문제라서 풀이가 없다;;; 그래서 포기했었다. 오늘 학회 채점현황에서 20052 가 풀렸는데, 나는 아직 안 풀려 있길래 풀었다. 그래서 세트로 13536을 풀어보려 갔는데, 이것도 안풀림;; 한 1시간 정도 고민하다가 설마 금광 세그? 라는 생각으로 들어갔는데 바로바로 풀려버린다. 13536은 struct로 3개를 관리해주면 된다. 이건 설명이 어려워서 생략하고 24915 중심으로 설명을 해보자면, 어떤 구간 [l , r]을 나타내는 노드에 대해서 1. l> b >> c; if (a == 1)update(b - 1, c..

2022년 3월 26일 즈음 팀연습으로 풀어보았던 셋이다. 일주일이 지난 지금 시점 한 문제 빼고 모든 문제를 업솔빙해서, 풀이를 올려보고자 한다. 개인적으로 에듀케이셔널 한 느낌이 강한 측면이 있었다. 구현/지문이 더럽지 않아서 너무 좋았다. dp가 많이 나오는 듯한 경향은 우리나라랑 잘 맞는듯 하기도 하다. 연습셋 하기 전에 처음이니까 쉬운셋 하자고 해서 골랐고, 연습 때는 C D E I 4문제를 못 풀고 9솔로 마무리 했었다. 연습셋 후기는 귀찮아서 다음에 잘 봤을때 쓰겠다 ㅋㅋ. A. Circle Bounce 이 문제는 마음에 쏙 드는 문제였는데, 풀면서 얻어간 것이 좀 있었다. 우선 확률을 기약분수로 나타내는 문제에 대해서, modulo를 취하면 곱하기를 해도 일정하게 유지된다는 성질이 있는데,..

https://www.acmicpc.net/workbook/view/8646 많이 풀어주세요.

공식 해설을 봤는데, 나처럼 푼 사람이 없는거 같아서 올려본다. 보통 아름다운 풀이는 간선을 뒤집는다는 아이디어 이다. 이제 무지성 풀이는 scc/위상정렬을 잘 쓰는 풀이가 있다. 나는 쉬운 무지성 풀이로 풀었는데, 그냥 실제로 그래프에서 사이클 찾아주면 된다. #include //#define double long double //T.erase(unique(T.begin(),T.end()),T.end()); //written by djs100201 #define all(v) v.begin(),v.end() using namespace std; using ll = long long; using P = pair; using PP = pair; const ll n_ = 1e6 + 100, inf = 1e18..

문제요약. 300*300 grid에서 거리의 정의를 manhatan distance로 했을때 정삼각형의 개수를 구하여라. 우선 유클리드 좌표게에서 정수 좌표 3개의 꼭짓점을 가지는 정삼각형은 존재하지 않는다. tan 60이 무리수이기 때문. 따라서 이 문제에서는 맨해튼 거리로 변형되었는데, 접근 방식은 다음과 같다. 일단 점 2개가 일직선인 경우는 예외처리 했다. 이는 간단한 sweeping으로 예외 처리 할 수 있다. 이제 3점의 x와 y좌표는 전부 distinct하다고 가정하자. 우리는 이제 이런걸 생각해보자. 어떤 점 3개를 뽑았을때 이 3개의 점이 정삼각형이 되는지를 어떻게 판정할 지를 생각해보면 되자. 우선 이 3점을 x좌표로 정렬하자. 그렇다면, x좌표로 정렬하고 봤을때, y좌표의 대소관계에 ..

야심한 새벽에 만난 너무 좋은 문제 문제풀이는 크게 2가지로 나뉘어 진다. 1. 관찰 2. dp로 문제풀기 1번이 2번보다 조금 더 어려운거 같기는 하지만 2번도 쉽지는 않다. 일단 결론부터 말하면, k개의 연속한 문자가 한번이라도 등장한다면, 이 문자열은 항상 조건에 따라 만들 수 있다. 나는 이걸 종이에 몇개 써보면서 관찰에 성공했다. 증명은 꽤나 쉬운데, 우리는 k개의 연속된 substring을 골라서 같은 문자로 치환하는 작업을 반복할 것이다. 그러면 이건 순서가 있는 작업이기 때문에 마지막에 결과 string에서는 k개의 연속된 substring이 반드시 존재해야 한다. 그렇다면 k개의 연속된 substring이 존재하는 모든 string은 만들수 있을까? 만들 수 있다. 아이디어는 다음과 같다..

2021 icpc 본선 문제. 다양한 풀이가 많은 것 같아서 내 풀이를 남기고자 한다. 문제요약. 정렬되지 않는 수열 A, B가 있다. 이때, A에서 딱하나 빼고, B에서 딱하나 빼자. 그리고 적절히 매칭했을때, 매칭된 모든 원소의 차이의 최댓값을 최소화하게 매칭됐을때 A에서 어떤 걸 빼는게 최적인가? 차이의 최댓값을 최소화를 동일하게 할 수 있다면, A중 값이 가장 작은걸 출력하라. 1. 빼는게 없다고 가정하면 정렬했을 때 매칭하는게 최적해다. 이건 well known 입니다. 증명은 넘기겠습니다. 2. 빼는게 있을 때 이런걸 생각해봅시다. 우선 정렬을 하고 matching을 합니다. 그런 상태에서 차이를 전부 계산해줍시다. 이때 최댓값을 dif라고 합시다. 최적으로 A,B를 하나씩 빼면 dif는 절대..

현재 시각 기준 15명에게밖에 풀려있지 않은 문제다. 매우 좋은 dp문제라는 생각이 들어서 풀이를 올린다. 1.배송비가 없다면 어떤 문제일까? mcmf의 기본형태이다. 2.배송비가 있을때 naive한 dp를 떠올려보자. 그렇게 되면 시간복잡도가 test case1개당 $O(NMS)$정도에 풀수 있고, 이는 너무 크다. (tc가 1개라면 적당히 최적화 할 여지가 존재한다.) 여기서 최적화를 잘하면 $O(NS)$정도에 줄일수도 있는데, 이렇게 해도, tc가 100개라 tle가 난다.(해보진 않음..ㅋㅋ!) 3.그리디한 전략 하나를 섞자. i번째 쇼핑몰에서 구매하기로 결정했으면, 그 쇼핑몰에서 항상 모든 물건을 구매하거나, 그 쇼핑몰이 마지막 쇼핑몰인 경우가 최적해이다. proof: 모든 물건을 구매하지 않은..

https://www.acmicpc.net/problem/22900 문제요약: 트리가 주어지고 간선에 가중치가 주어진다. 간선은 가중치가 존재할 때만 이용할 수 있다. 한번 움직일때마다 가중치를 원하는 만큼 뺀다. 움직일 수 없게 되는 사람이 지게 된다. 모든 시작위치에 대해서 선/후 공 중 누가 이기는지 구해라. 우선 가중치를 없애자. 어차피 모든 간선은 1번만 이용하는 걸로 생각해도 된다. (왜 그런지는 생각해보자.) 그럼 다음과 같은 tree dp형태로 바뀐다. 승리를 1, 패배를 0으로 칠한다면, 시작정점과 인접한 정점들 중에 0인 정점이 있다면 승리하고, 아니면 패배한다. 근데 모든 시작점에 대해 이걸 다 구하기는 어렵다. 그래프가 아니라 트리라는 걸 이용하자. 1번 정점을 루트로 잡고 dfs로..

slope trick 연습문제 이다. 기억이 휘발되기 전에 풀이를 써본다. https://www.acmicpc.net/problem/19693 개인적으로 이 문제는 풀이를 보지 않고 푸는 거를 추천한다. 풀면서 slope trick에 대한 이해가 깊어졌다.. 더보기 기본으로 배웠던 boj수열 문제와는 다르게 함수의 왼쪽 오른쪽 구간을 동시에 관리해야 한다. 우선 $dp(x,y)=min(dp(x-1,y))+|a(x)-x|$가 된다. 단 ($x-k