(2020년 9월 15일에 작성한 글입니다.)
Dashboard - Educational Codeforces Round 95 (Rated for Div. 2) - Codeforces
codeforces.com
이렇게 긴장감 없는 코포는 처음이었어.
A번 예제 output이 잘못 나와있어서
이해하려고 노력하다가 B로 넘어갔었는데
A번 문제 때문에 unrated 되었고
그래서 그냥 적당히 풀었다.
A.
ans = ((y + 1) * k - 1 + (x - 2)) / (x - 1) + k
(x - 2)를 더한 건 올림을 위함이다.
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T;
ll x, y, k;
ll ans;
cin >> T;
while (T--) {
cin >> x >> y >> k;
ans = ((y + 1) * k - 1 + x - 2) / (x - 1) + k;
cout << ans << '\n';
}
return 0;
}
B.
문제 잘못 읽어서 제출 한 번을 낭비했다...
unlocked된 수들을 내림차순으로 bubble sort 하면 됨.
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T;
int N;
int i, j;
cin >> T;
while (T--) {
cin >> N;
vector<int> arr(N);
vector<int> locked(N);
for (i = 0; i < N; i++) {
cin >> arr[i];
}
for (i = 0; i < N; i++) {
cin >> locked[i];
}
for (i = 0; i < N; i++) {
if (locked[i]) {
continue;
}
for (j = i + 1; j < N; j++) {
if (locked[j]) {
continue;
}
if (arr[i] < arr[j]) {
swap(arr[i], arr[j]);
}
}
}
for (i = 0; i < N; i++) {
cout << arr[i] << ' ';
}
cout << '\n';
}
return 0;
}
C.
구현으로 풀었다.
ㅋㅋㅋㅋㅋㅋㅋㅋ
진짜 어이 없다. 이걸 구현으로 풀다니.
dp문제인데, dp인것 같다는 느낌은 받았었는데
점화식을 모르겠어서 그냥 구현했다.
친구 차례에 1이 있으면 그걸 먹을 수 밖에 없음.
만약 그 다음 것이 1이면, 나한테 넘기고,
만약 0이면...
여기서부터가 좀 웃긴데
그 뒤로 0이 몇개인지 센 다음에
0이 홀수개면 friend가 하나 먹고
짝수개면 넘어가는 방식으로 했다.
0이 홀수개면, friend가 하나 먹어야
그 뒤로 한 개씩 돌아가면서 먹을 때
맨 마지막 0이 friend한테 가고, 1이 나한테 온다.
근데 이때 zero 개수를 셀 때,
0이 시작될 때 마다 zero를 셌더니 시간초과가 났고
그래서 0을 뺄 때마다 zero--를 해줬더니 wa가 떠서
이유를 확인해보니까
친구가 처음 0을 만날 때 zero--를 안해줬고,
또, zero 개수를 세기 시작하는 걸 zero == 0일때로 했는데,
zero의 초기 설정이 zero = 0이기 때문에
만약 맨 처음이 0이라면 zero는 -1이 되고
그러면 if(zero == 0)을 통과 안 해서 zero 개수 구하는 게 실행이 안 된다.
그래서 if(zero <= 0)으로 바꿨더니 맞았다.
코드를, 가장 효율적으로, 깔끔하게 짜려고 괜히 고집 부리다가
가끔 이런 실수가 나오는 거 같다.
여기서도... 그냥 처음부터 if(zero <= 0)했으면 한 번에 맞았을 걸 말이야...
int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
int T;
int N;
int cnt;
bool me;
int zero;
int i, j;
cin >> T;
while (T--) {
cin >> N;
vector<int> arr(N);
for (i = 0; i < N; i++) {
cin >> arr[i];
}
cnt = 0;
me = false;
zero = 0;
for (i = 0; i < N;) {
if (!me) {
if (arr[i++] == 1) {
cnt++;
}
else {
zero--;
}
if (i < N && arr[i] == 0) {
if (zero <= 0) {
for (j = i + 1; j < N && arr[j] == 0; j++);
zero = j - i;
}
if (zero % 2 == 1) {
i++;
zero--;
}
}
}
else {
if (arr[i++] == 0) {
zero--;
}
if (i < N && arr[i] == 1) {
i++;
}
}
me = !me;
}
cout << cnt << '\n';
}
return 0;
}
근데 문제는! 이렇게 풀면 안 된다는거
ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ
효규가 dp로 풀었다고 했는데
dp[1][0] = arr[0];
dp[1][1] = arr[0] + arr[1];
dp[0][1] = dp[1][0];
for (int i = 2; i < n; i++) {
dp[i][0] = min(dp[i - 1][1], dp[i - 2][1]);
dp[i][1] = min(dp[i - 1][0] + arr[i], dp[i - 2][0] + arr[i] + arr[i - 1]);
}dp[x][0]는 x번째를 내가 가져갔을 때의 최솟값,
dp[x][1]는 x번째를 친구가 가져갔을 때의 최솟값.
근데 내가 처음에 궁금했던 건
이렇게 하면, 연속으로 최대 두 개만 뽑을 수 있다는 부분은 어떻게 체크되는거지?
였는데
점화식을 보면 바로 전 거랑, 2개 전 거를 상대방이 뽑았을 경우를 이용해서 min 값을 구하니까
이 풀이가 맞다.