#683 div2 11/15

codeforces.com/contest/1447

Dashboard - Codeforces Round #683 (Div. 2, by Meet IT) - Codeforces

음 2시간 반이어서 엄청 당황스러웠다 빨리 자고 싶었는데

 

A 

 

문제 해석이 전혀 안되었다. ㅋㅋㅋ 거의 예시보고 이해했다. 

n이 주어지고, 1, 2, 3, 4, ... n으로 이루어진 수열에서 

횟수는 알아서, i번째의 덧셈은 i index 를 제외하고 더해서 모두 같은 수가 되도록 만드는 문제였다.

 

그냥 1은 1덧셈을 제외시키고 2는 2 덧셈을 제외 시키는 식으로 n번을 시행하면 된다.

 

10분솔브

 

B

 

수가 n*m행렬로 주어지고, 그 인접한 수들의 부호를 바꿀 수 있다.

횟수는 제한이 없고, 이 행렬의 합의 최대를 구하는 문제이다. 

 

해보니깐 음수 부호를 원하는곳으로 이동시킬 수 있었다. 따라서 음수부호의 갯수가 짝/홀에 대한 문제였다

 

짝이면 모두 양으로 바꾸기 가능, 홀이면 절댓값 가장 작은 수를 빼기로 두고 푸는 문제

 

20분 솔브

 

C

 

사실 이 문제때문에 김이 확 빠졌다. 

 

수들의 합을 W이하, W/2 이상으로 만들 수 있는지에 대한 문제

 

만약에 이 전까지 수들의 합이 W/2미만이라면 W/2를 초과하는 수를 더해야만 W를 초과할 수 있다.

따라서 합이 W이하라면 계속해서 더해도 상관이 없다. 

만약 W/2이상인게 나오면 그냥 그대로 수를 출력. 

 

index 저장은 queue에 하면 가능하다. 

 

가우스 기호가 내림말고 올림이 있는 줄 몰랐다. 그냥 생긴게 좀 이상하다 생각만 했지 .. 

그래서 계속해서 틀렸다. 질문하니깐 엄청 친절하길래 고맙긴 했지만 ..... 

 

다들 pretest2에서 틀리던데 나와 같은 이유로 틀린게 아닐까 생각한다. 

 

 1시간 12분 솔브

 

D

 

LCS 스터디에서 이런 문제가 존재한다는 사실만 알았지 알고리즘은 처음 접해보았다.

그냥 dp개념의 최장부분수열문제인데 C에서 그렇게 삽질을 하고 내가 모르는 개념에 대해서 문제를 풀려니 당연히 집중이 안 되었던 것 같다.

 

그래도 개념을 찾아서 보니깐 꽤 간단하게 풀 수 있다는 생각을 하고 구현한게 한 종료 10분전 

 

근데 lcs만 구했고, 문제에서 요구하는 값을 구하기 위해서 내가 어떻게 해야할지 좀 생각하니깐 끝났다. 

 

div2에서 3솔브는 처음이지만 문제가 쉬웠다고 생각하고, 또 집중이 너무 흐트러져서 만족스러운 라운드는 아니었다. 

 

-----------------------------------------------------------------------

 

D를 업솔빙 했는데 

 

lcs개념자체를 어느정도 이해하고 있는지가 중요했던 것 같은 느낌이다.

 

a: abba 

b: babab에서 

 

if(a[i] != b[j])lcs[i][j] = max({lcs[i][j], lcs[i-1][j]-1, lcs[i][j-1]-1});

else lcs[i][j] = lcs[i-1][j-1]+2;

 

그리고 ans에 항상 max(ans, lcs[i][j])를 해줘서 가장 큰 값을 출력하면 된다.

 

위에 식을 대충 설명하자면 

 

먼저 lcs를 구한다. 원래대로라면 위, 왼쪽중 최대의 값을 그대로 가져오겠지만 이 경우에는 구하려는 값이 

lcs*4 - 부분 문자열 크기(a+b)의 값이므로 

 

부분 문자열이 하나 증가하면 당연히 값도 하나 감소하게 된다. 

 

만약에 같을 경우에는 대각방향에서 그냥 2를 더하면 된다. 

 

표를 작성해보면 

 

x 0 a b b a 

0 0 0 0 0 0

b 0 0 2 2 1

a 0 2 1 1 4

b 0 1 4 3 3

a 0 2 3 3 5

b 0 1 4 3 4

 

이렇게 된다. 문제에서 요구하는 사항이 무엇이고, 요구하는 사항에서 말하는게 무엇인지 구체적으로 표현하면 수학적으로 구하기도 더 쉬워질 것 같다. 

 

이 경우에서는 

 

4*lcs - 부분 문자열이 최대가 만드는 것을 

 

=> lcs는 고정이니깐 부분 문자열이 최소가 되어야 하고, (lcs와 부분문자열의 길이가 독립적이라고 보기는 어렵다)

 

4*lcs - 부분문자열의 값은

 

부분 문자열이 하나 증가하면서 lcs는 그대로라면 (문자열이 다른 경우) 값은 하나 줄어든다.

 

lcs이 증가한다면 (문자열이 같은 경우) 이 경우에는 부분 문자열이 두 개 추가된 것이다. 

 

왜냐하면 설명을 잘 못 하겠는데 그냥 그렇다 

표를 참고하면 될 것 같다. 

 

x 0 a b b a

0 0 0 0 0 0

b 0 0 2 2 1

a 0 2 1 1 4

b 0 1 4 3 3

a 0 2 3 3 5

b 0 1 4 3 4

 

사고능력을 기르자 어차피 개념은 좀만 보면 알 수 있다. 사실 lcs를 몰랐어도 실력만 있으면 인터넷 보고 

충분히 풀 수 있는 문제였다. 홧팅