목록Algorithm/Problem Solving (95)
블로그 옮겼습니다
https://csacademy.com/contest/archive/task/second-minimum/ 반씩 나눠가며 각각의 l, r 에 대해 작은 값을 가지고 있다면 한번 분할정복 돌리면 가장작은 값은 바로 나오며그다음에 토너먼트의 승패표가 있을 때 2등의 후보는 lgN개로 정해져있는 성질이 있기 때문에 다시 순회하면서lgN개에 대해서만 반복문 한번 돌리면서 가장 작은놈을 구해주면 된다.2등의 후보는 결승에서 1등한테 진놈, 준결승에서 1등한테 진놈, 준준결승에서 1등한테 진놈, ..... ,1라운드에서 1등한테진놈이 된다. 12345678910111213141516171819202122232425262728293031323334353637383940414243#include using namespa..
https://algospot.com/judge/problem/read/COUNTPALIN \( 1\leq{N}\leq{10^6} \)길이가 N인 문자열 S가 입력으로 주어질 때 팰린드롬인 모든 부분 문자열의 개수를 구하는 문제이다.이 문제를 푸는 방법은 우선 각 중심마다 최대 팰린드롬의 길이를 구한뒤 그 길이/2 만큼을 모두 더해주는 것이다.왜냐하면 어떤 중심에서 최대 길이의 팰린드롬이 abccba 라면 같은 중심을 가지는 팰린드롬들은 반지름을 1씩 줄여나가면모두 팰린드롬이기 때문에다. 이것은 자명하다. 즉, abccba, bccb, cc 이게 다 팰린드롬이 되기 때문에 최대팰린드롬길이/2의 식이 나오는 것이다. 그리고 중심이 다르면 다른 팰린드롬이라는 것이 자명하기 때문에 모든 각각의 중심에 대해최대..
1 T; for(int t = 1; t > P; ll S = 1e12; ll GCD = gcd(P*S, S); ll C = S/GCD; S = P * C; S -= C; ans[4] = S/4; if(S%4) ans[S%4]++; ans[0] = C - ans[1] - ans[2] - ans[3] - ans[4]; cout
문제 링크 \(1\leq{a,b,c}\leq{10^9}\) 일 때, A * B = C 를 만족하면서 |A-a| + |B-b| + |C-c| 가 최소가 되게 하는 자연수 A,B,C 에 대하여|A-a| + |B-b| + |C-c| 를 구하는 문제이다. 처음에 삼분탐색 등으로 구하려 했는데 풀리지 않았다. 애초에 삼분탐색만으로는 풀 수 없는 문제같다.우선 가장 중요한 것 중 한가지는 A가 정해지면 |A-a| + |B-b| + |C-c| 가 최소값이 되기 위한 B와 C는자동으로 결정 된다는 것이다. 그 이유는우선 우리는 A가 이미 정해졌기 때문에 |A-a| + |B-b| + |C-c|를 최소로 만들기 위해서는 최대한B를 b와 같게 만들고 C를 c와 같게 만들어야 한다. 그런데 C는 A와 B의 곱으로 이루어 지기..
문제 링크 \(1\leq{N}\leq{30}\)\(0\leq{M}\leq{30}\)\(1\leq{K}\leq{8}\) 이 문제는 N개의 집이있을 때 집과 집을 잇는 M개의 양방향 도로를 설치 하는 문제이다.A번 집과 B번 집을 잇는 도로를 설치하기 위해서는 01); } ll& cache = dp[u][v][k][mask]; if(cache != -1) return cache; cache = 0; cache = (cache + go(u,v+1,k,mask)) % mod; int nextmask = mask^(1
문제 링크 \(2\leq{N}\leq{10^5}\)\(1\leq{K}\leq{200}\) 이 문제는 N개의 노드로 이루어진 트리가 주어진다. 각 노드에는 가중치가 있다.K가 주어지는데 최대 K번 가지를 칠 수 있다는 것이다. 어떤 노드 u를 가지친다는 말의 정의는노드 u를 루트로 하는 서브트리를 제거한다는 것이다. 최대 K번 가지를 쳐서 남아있는 트리의 모든 노드의가중치의 합을 최대로 하고싶을때 이 최대 가중치합을 구하는 문제이다. 우선 처음에 일반적인 트리dp 문제처럼 이렇게 풀어 보려고했었다.dp[u][v][k] : 현재 노드 u를 보고있고 v개의 자식을 이미 봐주었으며 앞으로 최대 k번 가지칠수있을 때 최대 가중치 합 이렇게 하면 부분문제의 수는 최대 N*K 개이다. 왜냐하면 (u,v) 의 쌍은 간..
문제 링크 이 문제는 N개의 물통이 있고 L리터의 물을 N개의 각 물통에 나눠서 채우려고 하는데,물통에는 상한과 하한이 있어서 각 물통에 채울 수 있는 물의 양은 이 상한과 하한 사이의 양이어야만 한다. 이 때 N개의 물통에 채운 물의 양 중에서 가장 많은 양과 가장 적은 양의 차이가 최소가 되도록 하고싶다.이 떄의 차이를 구하는 문제이다. 단, 들어오는 입력들은 항상 L리터를 상, 하한에 맞춰 분배할 수 있는 방법이적어도 하나는 있다고 가정한다. 일단 이 문제는 두가지의 풀이가 있다.첫번째 풀이는 라인 스위핑(+그리디)이다. 내가 대회 때 푼 방법이 이 라인 스위핑인데대회가 끝나고 보니 나 말고는 라인스위핑으로 푼사람을 찾을 수가 없었다.좋은건지 안좋은건지.. 사실 처음에 다른 풀이 방법을 떠올렸다가 ..
문제 링크 격자의 사이즈 N,M 이 주어진다. 각 판은 '.' 또는 '1'~'9' 의 숫자이다. 그리고 n,m 이 주어지는데 n,m이란 어떠한 격자칸에서부터 시작하는 연속된 칸에 있는 수들의 합이 홀수가되어야 한다는 제약 조건에 대한 변수이다. 칸에서 아래로 n칸의 합은 홀수여야하고,오른쪽으로 m칸의 합도 홀수여야한다는 것이다. 물론 열 인덱스가 M-m+1 인 칸 까지만 적용되며행 인덱스가 N-n+1 인 칸까지만 적용된다. 이 때 '.' 인 칸에 적절한 '1'~'9'의 수를 넣어주어 위에서 말한 조건을 만족하도록 하는 방법의 수를 구하는 문제이다.일단 각 수가 홀수인지 짝수인지만 중요하기 때문에 현재 적혀있는 수가 실제로 몇이던 상관없고 짝수인지 홀수인지만중요하기 때문에 먼저 짝수는 0, 홀수는 1이라고..
문제링크 모든 자연수를 \(1+2+4+.....+2^{k-1}+r\) 로 분해할 수가 있는데M개의 수를 이 방식대로 분해하여 분해된 요소들을 모두 모아 정렬한 결과인 sequence를 A라고 해보자. \(1\leq{N}\leq{10^5}\)\(1\leq{a_i}\leq{10^{12}}\) sequence의 크기 N과 N개의 elements 로 이루어진 A의 원소들 ai 가 입력으로 들어온다. 이 A를 다시 분해하기 전의 원래의 수로 복원하려고하는데 복원하는 방법은 여러가지가 있을 것이다.복원의 결과로 나온 수가 K개일 때 K가 될 수 있는 수는 여러가지가있을 것이다. 이 때 이 가능한 K들을오름차순으로 모두 출력하는게 문제의 질문이다. 우선 k+1 개의 수를 \(1+2+4+.....+2^{k-1}\) 의..
\(1\leq{N}\leq{50}\)\(0\leq{K}\lt{2^N-1}\)괄호 문자열(correct parenthese sequence)의 정의는 이미 잘 알려져 있다.그리고 어떤 문자열 S가 '(' 와 ')' 로만 이루어져있는데 괄호 문자열이 아니라면 이것을 괄호ㄴㄴ문자열이라고 정의한다.N과 K가 주어진다. 길이가 N인 괄호ㄴㄴ문자열들을 사전순으로 정렬했을 때 K번째인 문자열을 찾는 문제이다.인덱스는 0부터 시작한다는 것에 주의하자. 우선 괄호 문자열의 개수를 구하는 방법을 알아보자.dp[i][j] : 이미 i개의 문자가 정해졌고 짝이 지어지지않은 열린 괄호의 수가 현재 j 개일 때 괄호 문자열의 수dp[i][j] = dp[i-1][j] + dp[i-1][j+1]왜냐하면 각각의 위치에서는 괄호를 열거..