Go Gradually - Repository

실제 contest중에는 풀지 못한, 난이도 높은 문제였다.Upsolving 을 진행하며, 정리한 내용을 공유하고자 한다.문제https://codeforces.com/contest/1905/problem/Dnn^2 으로는 절대 풀 수 없는 문제이다.핵심 아이디어1. 반드시 맨 앞 원소가, 맨 뒤로 간다.중요한 통찰을 얻을 수 있는 단서 중 하나는, a[0]이 맨 뒤로 간다는 것이다.이 사실을 응용해보자2. MEX값은, 범위가 넓어지면 넓어질수록 무조건 증가하는, 단조증가 형태를 띈다.단조증가 성질 또한, 무궁무진한 활용 가능성을 갖추고 있다.그리디한 접근 혹은, 파라매트릭 서치에도 응용이 가능하니, 기억하고 있도록 하자.3. 값이 순열로 주어진다.중요한 통찰을 얻을 수 있는 마지막 단서는, 값이 순열로 ..

기본적인 0-1 BFS 문제처럼 보인다.deque를 이용하면, push_front() 및 push_back() 을 이용해 열어야 하는 문의 갯수를 셀 수 있다.근데 단순 최단거리가 아니다.죄수 두명을 탈옥시켜야 한다.탈옥의 정의는, 현재 보여지는 지도 밖으로 죄수가 나간다는 의미이다.우리는 여기서, 지도 밖에 padding 을 한 줄 추가함으로서, 탈옥을 시킬 수 있다.단순히 bfs 하면?다음과 같이, 겹치는 지점을 제외해줘야 한다.근데 두개의 거리를, 중복 없이 어떻게 잴 수 있지?시나리오를 그려보며, 규칙성이 있는지 탐색해보면 반드시 어딘가에서 죄수 2명과 외부지점이 만날 수 있다.문제를 두번에 나눠서 풀면, 해를 구할 수 있지 않을까?다음과 같은 경우, 두 죄수 사이의 최단 거리는 5이고, 이 최단..

[2213] 트리의 독립집합문제를 천천히 읽어보자.독립집합이란, 모든 정점 쌍이 인접하지 않은 정점들의 집합이라고 한다. 간단하게 그림을 그려보면, 다음과 같은 예시를 들 수 있다.그리고 다음과 같은 애들은 독립집합이 아니다.여기서 문제는 한가지 새로운 정의를 내린다.독립집합의 크기란? 독립 집합 내 정점들의 가중치의 합정점의 가중치는 정수로 주어지고, 10000 이하로 제한되어 있다.우리의 목표는 독립집합을 이루는 경우의 수 중, 가장 큰 "집합 내 원소의 가중치의 합"을 구하는 것이다.문제에 그래프 형태가 트리 구조로 되어있다고 하는데, 여기에서 우리는 중요한 관찰을 할 수 있다.트리구조로 되어있다는 것은,정점 A가 어떤 독립 집합 S에 포함/제외되는 것이 재귀적으로 자기 자신에게 영향을 주는 "사이..

[1475] 방 번호어떠한 사람(기능) 이 필요한가?항상 설명이 너무 복잡하다면, 일단 문제를 단순화해서 보자. → 조건을 몇개 제거해보자.(6은 9를 뒤집어서 이용할 수 있고, 9는 6을 뒤집어서 이용할 수 있다는 조건을 제외해보자.)만약, 122 라는 숫자를 만들어야 한다면, 플라스틱 세트는 2세트가 필요할 것이다(2를 2개를 수급하려면, 플라스틱 세트 2세트가 필요할 것이고, 3~9까지 각각 숫자 2개씩은 모두 버려질 것이다. 아깝네)만약, 9999라는 숫자를 만들어야 한다면, 플라스틱 세트는 4세트가 필요할 것이다.(9를 4개를 수급하려면, 플라스틱 세트는 4세트가 필요할 것이고, 9를 제외한 나머지 숫자들 각 4개들은 모두 버려질 것이다.)우리는 여기서, 다음과 같은 결과를 찾을 수 있다.가장 ..

[2577]숫자의 갯수세개의 자연수 A, B, C가 주어질 때, A × B × C를 계산한 결과에0부터 9까지 각각의 숫자가 몇번씩 쓰였는가?순서대로, 하나씩 차근차근 풀어보자.어떤 사람이 필요한가?문제의 예제를 분석하며 한번 우리가 직접 세보고, 어떠한 과정을 거쳤는지 생각해보자.A, B, C를 곱한 결과값을 계산한다. 그 결과로 17037300 이라는 숫자가 등장했다.우리는 그 다음, 각 자릿수별로 어떠한 숫자가 있는지를 확인했다.근데 총 10종류의 숫자가 각각 등장한 횟수를 머릿속에서 다 외우고 있긴 어렵기 때문에, 아래에 각 숫자가 몇번 등장했는지를 기록하며 풀었다.최종 결과로 3 1 0 2 0 0 2 0 0 이라는 결과가 등장했다.이때 재미있게 볼만한 정보는 다음과 같다.기존 숫자의 170373..

https://codeforces.com/contest/1937/problem/C현재 주어진 연산으로 가능한 것최댓값 찾기: a|a 최솟값 찾기: a|a 현재 주어진 순열은 [0, n-1] 범위를 갖는다.따라서, XOR로 만들 수 있는 최대의 정수는 상한이 정해져 있다.px ^ py = (n - 1의 msb) * 2 - 1그렇다면, 저 상한을 어떻게 만들어낼 것인가?최댓값(n-1)을 찾는다.최댓값과 or 연산을 수행하여 가장 큰 값을 만드는 인덱스들을 찾는다.해당 인덱스들의 집합에 들어가기 위해선 최댓값의 하위 비트가 0인 비트들을 1로 채울 수 있어야 한다. 예시) 11010 -> 1101, 101, 111, 10111XOR 도 결국 OR 되어야 하는데, 그냥 이러면 어떻게 답 안나오나 라는 느낌으로 ..

오늘도 코드포스 문제풀이를 하던 도중, 익숙한 방정식의 형태가 등장했는데, 정확히 어떻게 풀어야 하는지 기억이 잘 나지 않아, 이번 기회에 확실하게 정리하려고 한다.Div.2 # 955 D번을 풀던 중, 다음과 같은 방정식을 마주하게 되었다.$$ D = px + qy + rz + ... (x, y,z,... \in \mathbb{Z}) $$다음과 같은 형태의 방정식을 "디오판토스 일차방정식" 이라고 한다.실제로 디오판토스 방정식은 차수가 하나씩 늘어갈수록 난이도가 지수적으로 증가한다고 한다.지나치게 깊게 들어가지 않으면서, 적절하게 해당 해의 존재성을 증명하는 방법을 알아보자.위 방정식의 해가 존재하는 지를 구성적 증명으로 처리하려면, 완전 탐색 or 그래프 탐색 방식으로 접근해야 하는데, 이는 지나치게..

문제 링크: https://codeforces.com/contest/1995/problem/C오버플로우를 막는 방법에 대한 고민핵심 아이디어a^x^2 a^x >= b^y 인 경우는 없다증명1 초과인 a, b, x, y에 대하여a^x a^x^2 > b^y 이면a^x^2 a^x = p, b^y = q 라고 하면p p * p p * p 따라서 핵심은, 몇번의 제곱을 수행해야 하느냐!오버플로우를 신경쓰지 않도록, 2^63 내에서 대소 비교를 수행하는 방법실제 문제를 풀진 못했으므로, 구현은 남기지 않음

k제일 큰 수에 1이 있으면?그냥 그거 쭉 늘리면 됨제일 큰 수에 1이 없으면?1이 붙은 수 중 가장 큰 수를 늘리거나큰수와의 차이만큼 낭비그 후 효율 떡상(1)중간값을 늘리거나효율 갈수록 안좋아짐이거 이분탐색 되려나?그래프가 ~자 모양이 됨효율 이김/안이김 이분탐색?몰빵보다 좋음/안좋음?이건 몰빵한테 따이는 시점 이분탐색인데중간값을 늘리는 시도를 점차 증가시켜본다?왜 그게 그렇게 되지?왜 최대 원소가 효율을 뽑기 시작하거나k 개 중 x개를 투자하면그 이후 k - x 개는 무조건 큰 수에 넣는게 제일 고효율이다문턱값을 넘으면 그 이후는 거기에 몰빵하는게 무조건 이득중간값을 올리는데 전부 몰빵하거나문턱값 안넘을거면 그냥 중간값 올리는데 몰빵이 나음그럼 중간값을 어떻게 올리지?순서가 동적으로 바뀌는데정해진 ..

트리 구조로 되어있는 숨겨진 그래프n-1 개의 간선을 찾아야 함15n 개의 쿼리를 통해n≤1000트리 구조의 특성상, 임의의 두 노드 사이의 경로는 유일하다한번에 하나씩 컴포넌트를 합쳐나가면?유니온 파인드 이용사이에 모르는 컴포넌트가 나오면?그냥 그거 찾지 뭐...?중요한건 임의의 두 컴포넌트를 "연결" 하고자 하는 것거리가 절반씩 줄어드니, logN서로 다른 두 컴포넌트 찾는 법유니온 파인드import java.io.BufferedReader;import java.io.BufferedWriter;import java.io.IOException;import java.io.InputStreamReader;import java.io.OutputStreamWriter;//Change Class Name to ..