#723 div2 5/28

https://codeforces.com/contest/1526

Dashboard - Codeforces Round #723 (Div. 2) - Codeforces

A. Mean Inequality

 

2*n개의 수열이 존재하고, 이 수들의 사이값이 양쪽 두 값 합의 절반이 되지 않도록 재배열 하는 문제. 

따라서 양쪽이 모두 그 중간값보다 크게 되면 절대 양쪽 두 값 합의 절반이 될 수 없으므로 배열을 크기순으로 다시하면 된다. 

 

B. I Hate 1111

 

먼저 그냥 1000 + 111 이 1111이라고 생각을 했고, 왜 그런지 몰라도 배수처럼 생각을 하였다. 그러나 배수 약수 관계가 아니었고 그렇게 틀리면 틀리는게 당연했다. 그래서 그냥 수열로서 어떤식으로 11로 111을 만들 수 있는지 digit으로 구분해서 생각을 해보았으나 전혀 생각이 되지 않았다. 

이 문제는 다른 1으로 이루어진 수들은 11과 111의 배수이다. 따라서 11과 111 두 가지 수로만 만들 수 있는지 아닌지를 체크하면 된다. 여기서 이제 수식이 들어간다.

우리한테 주어진 수 X = A*11 + B*111 이고, B = C*11 + D이므로 D는 11보다 작은 수이다. 

 

여기서 B대신 우변을 대입하면 

X = A*11 + (C*11+D)*111 이 되고, 

X = 11*(A+C*111) + 111*D가 된다.

따라서 111의 가짓수는 0개에서 10개까지가 되고, 이 경우들을 따져보면 된다.

 

C1. Potions (Easy Version)

 

DP문제 

점화식을 체크했지만 뭐가 문제인지 계속해서 WA가 나온다. 점화식은 다음과 같다.

dp[i][k] := i번째 포션까지 체크했을 때 이제까지 k개의 포션을 섭취했을 때의 남은 에너지의 최대

 

dp[i][k] = max(dp[i-1][k-1] + ai (if dp[i-1][k-1]+ai>=0) , dp[i-1][k])

 

O(n^2)으로 가능하다.

 

dp를 정말 못푼다. 뭐든지 그리디로 생각하려고 하고, 그렇기 때문에 점화식을 구할 생각을 잘 하지 못하는 것 같다. 특히 이 문제는 napsack같은 느낌이 솔솔 나는데 아직 머릿속에 그려지지 않는 것을 보면 많이 학습해서 적응이 되게끔 해야겠다는 생각이 든다.