Codeforces Round #510 (Div. 2) D. Petya and Array 좌압과 세그먼트 트리

문제는 바꿔 말하면, 구간 $[l, r)$의 부분합이 $t$ 미만의 부분합이 되는, $l,r$의 수를 요구하고 싶다. 즉, $a_0$에서 있는 $a_i$까지의 합을 index로, 출현 횟수를 값으로 하는 세그먼트 트리 $st$를 가집니다. $[5,-1,3,4,-1]$이면 누적 합은 $[5,4,7,11,10]$이므로 좌압을 위한 테이블 $[4,5 ,7,10,11]$를 가지고 $1,0,2,4,3...

codeforces파이썬좌표 압축경기 프로그래밍세그먼트 트리

Codeforces Round #715 Div. 2C The Sports Festival: 구간 DP전형

구간 DP의 초전형. 이하, 0-indexed. 입력을 정렬하여 어디서나 시작하고 최적으로 좌우로 계속 유지하면 좋다는 것을 알 수 있습니다. {2000})$의 주문이 된다. 우선, 입력을 소트하여 n개의 요소를 $a_0, a_1, ..., a_{n-1}$로 한다. 특정 구간 $[l, r)$의 최상의 비용을 $dp[l, r)$로 나타낸다. 이때 원하는 결과는 $dp[0, n)$이다. 단, 제...

C++codeforces구간 DP파이썬경기 프로그래밍

Codeforces Round#704 C. Maximum width

우선 s에서 t를 만들 수 있는 가장 짧은 장소를 찾는다. 예를 들어, 위 그림에서 abc는 (0-index로) 0,1,2 문자입니다. 이것은, t의 0문자째로부터 차례로 s를 탐색하면 알 수 있다. 예를 들어, s=axxbxxxc이고 t=abc라면 $[0,3,7]$가 된다. 여기서 먼저 거리의 max를 구해 둔다. 그런데, 다음에, t의 뒤의 문자에 해당하는 문자로부터, 가능한 한 뒤에 그...

codeforces파이썬경기 프로그래밍

[Codeforces] 1660C. Get an Even Strings [Codeforces Round #780 (Div. 3)]

대회에서는 1시간 가량 고민했지만 풀지 못했다. 문자열이 주어지면 짝수로 짝지어지는 문자열로 만들기 위해 최소 몇개의 문자를 지워야 하는지 구하는 문제이다. Input 첫 번째 case인 aabbdabdccc는 aabbddcc로 만들면 된다. 연속으로 짝수개가 생기게 하면 되는 것이다. 두 번째 case인 zyx는 다 지우면 된다. 그럼 입력받은 문자열 앞에서부터 확인하며 배열에 그 문자열이...

codeforcescodeforces

[Codeforces] 1660A. Vasya and Coins [Codeforces Round #780 (Div. 3)]

대회의 첫 번째 문제이다. 제출까지 5분 정도 걸렸다. 1원짜리 동전과 2원짜리 동전의 개수가 주어질 때 잔돈을 낼 수 없는 가장 작은 자연수를 출력하라는 문제이다. 1원짜리가 없다면 무조건 답은 1원이 된다. 2원이 100000개가 있어도 1원이 답이다. 1원짜리가 하나 이상 있다면 답은 1원짜리에 2원짜리 개수 * 2 + 1을 한 수가 답이다. 따라서 1원짜리가 하나 이상 있으면 총 액수...

codeforcescodeforces

Codeforces-Round-624-Div3

필요한 지식 구현 접근 a<b 인 경우 a-b가 홀수인경우는 1을 출력하고 짝수인 경우는 2를 출력한다. a>b 인경우 b-a가 홀수인경우 2를 짝수인경우 1을 출력한다. a==b 인경우 0을 출력한다. 코드(C++) 필요한 지식 구현 버블 소트 접근 버블 소트를 진행 하되, P배열에 있는 원소를 확인 후, 현재 자리를 swap할 수 있다면 swap하고 아니라면 "NO"를 출력하게 한다. 코...

algorithmcodeforcesalgorithm

Codeforces Round #686 (Div. 3)

1 ~ n을 한 번씩 사용하고 i번 위치에 i의 값이 들어가지 않도록 배열을 만드는 문제이다. 2부터 n까지 차례대로 출력 후 맨 마지막에 1을 출력하면 문제를 해결할 수 있다. n명의 사람이 각자 하나의 값을 가진다. 유일한 값을 가진 사람들 중 최소 값을 가진 사람이 게임에 이긴다고 할 때 게임을 이기는 사람을 찾는 문제이다. 사람들이 가지고 있는 숫자를 센 후 만약 유일한 값을 가진 사...

알고리즘codeforcesDiv3Div3

Educational Codeforces Round #96 (Div.2)

n이 1, 2, 4로 구성된 아파트인 경우 방의 개수가 맞지 않으므로 -1을 출력해야 한다. 즉, 위의 수열 중 1, 2, 4를 제외하고 모두 표현할 수 있으므로 다음의 경우를 생각할 수 있다. n이 3으로 나누어 떨어지는 경우, 방 3개짜리로 구성된 아파트이므로 (n/3,0,0)을 출력하면 된다. n을 3으로 나누어 나머지 1이 남는 경우, 방 7개 하나와 나머지 방 3개짜리 이므로, n을...

pscodeforcesdiv2codeforces

CodeForces#275--DIV 2--B(BinarySearch)(!!)

B. Friends and Presents standard input standard output You want to present cnt1 numbers to the first friend and cnt2 numbers to the second friend. Moreover, you want all presented numbers to be distinct, that also means ...

codeforces

Codeforces 559B Equivalent Strings 아이디어

제목 대의: 제목에서 제시한 정의에 따라 두 개의 열이 같은지 아닌지를 판단하는 거예요. 대략적인 사고방식: ....오랜만에 보정하러 왔는데... 그때 이 문제 시합 때 정의에 따라 Hash로 판단해서 TLE 했는데... 그래, 정해는 아니잖아. 이 문제의 정확한 방법은 매번 열을 반으로 나누어 사전 순서에 따라 정렬하는 것이다. 이렇게 해서 거슬러 올라간 후에 두 열이 문제의 정의에 따라 ...

codeforcesstringsequivalent559B

[Wunder Fund Round 2016(Div 1 + Div 2 combined) B] [폭력 욕심] Guess the Permutation 전체 배열 a[i] [j]=min(p[i],p

time limit per test memory limit per test input standard input standard output Bob has a permutation of integers from 1 to n. Denote this permutation as p. For all pairs of distinct integers i, j between 1 and n, he wrot...

codeforces탐욕스럽다폭력.라이브러리 - CF

[IndiaHacks 2016 - Online Edition(Div 1 + Div 2) ErrichtoA] [물문제] Bear and Three Balls에 수치 차이 1의 세 개가 있는지.

Limak wants to give one ball to each of his three friends. No two friends can get balls of the same size. No two friends can get balls of sizes that differ by more than 2. For example, Limak can choose balls with sizes 4...

수제codeforces라이브러리 - CF

[문제] CF883I: Photo Processing

원제 전송문은 우선 순서의 최대치를 가장 작게 배열하고 2점을 사용한 다음에 dp로 dpi dp 를 검증한다i dpi는 현재 i i i 임을 나타내며 마지막 그룹이 i i i 로 끝날 수 있는지 d p i ∣ = d p j - 1 (j < i, a i - a j < = m i d) dpi|=dp_{jj-1}(jpi∣=dpj는 1(jj)(i, j)(i, j)(i>j)(i, j)(i>j)(i>j...

문제풀이codeforces이분dp

Educational Codeforces Round 8

계수 모형을 보면 dp를 쓸 줄 안다.우선 문제를 1~x 범위 내에서 요구를 충족시키는 수가 얼마나 되는지로 바꾸어 보자.그리고 디자인 상태 dp(i, j, k), i는 앞의 i자리를 고찰했고 j는 현재 m에 대한 여수를 나타냈다. k는 접두사보다 작거나 접두사(우리가 구한 것은 1~x이기 때문에 이런 방식으로 x를 초과하는 것을 피한다).상태 이동 코드.마지막으로 b와 a의 결과를 나누어 ...

codeforces

Codeforces149D(카운트 구간 dp)

제목: 일련의 규칙을 제시하는 괄호 (괄호는 일치하는 것) 예를 들어 (() ()) 이 괄호의 정확한 일치는 첫 번째와 마지막, 두 번째와 세 번째, 네 번째와 다섯 번째이다. 지금 괄호를 염색하려면 이런 조건을 제시해야 한다. 1. 괄호는 염색하지 않고 파란색으로 염색하고 빨간색으로 염색할 수 있다. 2. 일치하는 괄호는 동시에 염색할 수 없지만 그 중 하나는 반드시 염색해야 한다. 3. ...

dpcodeforces

codeforces B. Cow Program(기억형 검색)

codeforces 283B n개의 수를 주고 홀수 번의 조작 x, y는 모두 a[x]를 더하고 짝수 번의 조작 y는 a[x]를 더하고 x는 a[x]를 빼고 범위를 벗어나면 끝난다.끝날 때의 y값을 묻습니다. 끝낼 수 없으면 출력-1 기록 상태 dp[x][2]는 홀수 번 또는 짝수 번 x점에 도착했을 때 걷고 나면 얻을 수 있는 권한값이다. 직접 검색, 검색한 상태를 직접 되돌려줍니다....

dp수색하다codeforces기억화 검색

상태 압축 dp

codeforces 543C n개의 길이가 m인 문자열을 보여 줍니다. 모든 문자열은 다른 문자열과 구별되어야 합니다. 우리는 어떤 문자열을 수정하는 한 사람에게 고정된 비용이 있습니다. 요구에 맞는 문자열로 수정하는 데 최소한의 비용이 있는지 물어봅니다. 우리는 dp[i][state]를 정의하여 이전 i 문자열이state 상태에 도달했을 때의 최소 비용을 나타낸다 요구에 부합되지 않는 문자...

dpcodeforces상태 압축

Codeforces Round #316 (Div. 2) E

E Pig and Palindromes n*m의 격자입니다. 격자마다 문자가 있습니다. 왼쪽 상단에서 오른쪽 하단까지 (아래로 또는 오른쪽으로만) 가야 합니다. 지나가는 문자를 연결해서 회문열로 만들어야 합니다. 몇 가지 방안이 있는지 물어보십시오. dp.pp(i, j, k)는 기점에서 i행 j열까지의 칸을 표시하고 대칭적인 칸이 k행(열로 계산할 수 있음)의 방안수를 나타낸다. 마지막 답은...

codeforces

Codeforces 156C (DP)

[TOC] @ (K ACMer) by 문제 해결 팩토리 제목: 소문자로 구성된 서열을 드리겠습니다. 서열에는 인접한 문자가 ASCII 코드 이전 작업을 지원합니다. (즉, ASCII 코드에 x를 더하면 다른 문자는 x를 줄입니다.)이 서열은 몇 가지 다른 다른 서열로 바꿀 수 있느냐고 물었다. 분석: 전형적인 종류 계수 문제는 DP를 사용해야 한다고 생각하기 쉽다.하지만 직접 생각하기는 쉽지...

codeforces

codeforces 366C C. Dima and Salad(dp)

codeforces 366C n개의 아이템을 주고 두 개의 속성이 있습니다. 마지막 첫 번째 속성의 총계가 두 번째 속성의 k배냐고 물었을 때 첫 번째 속성이 가장 크면 얼마입니까? 우리는 물품을 변형시켰다. 무게는 a[i]-b[i]*k이고 수익은 a이다. 그러면 우리는 무게를 플러스로 한 번 배낭을 만들고 품질을 마이너스로 절대치를 취하여 배낭을 한 번 만들고 무게가 같은 배낭의 수익의 합...

dpcodeforces

[문제풀이] CF1107 E: Vasya and Binary String

본제 전송문령 dpi, j, kdp{i,j,k}dpi,j,k는 구간 [i,j],j[i,j],j[i,j],j의 오른쪽에서 kk개를 함께 삭제할 수 있음 d p i , j , k = m a x ( d p i , j − 1 , 0 + a k + 1 ) dp_{i,j,k}=max(dp_{i,j-1,0}+a_{k+1}) dpi,j,k =max(dpi,j−1,0 +ak+1 ) d p i , j , t ...

문제풀이codeforcesDP