Codeforces Round #601 (Div.2)
A. Changing Volume
abs(a-b)를 5로 최대한 채우고, 나머지를 2로 최대한 채우고, 마지막을 1로 채우는 그리디.
source : https://codeforces.com/contest/1255/submission/65352313
B. Fridge Lockers
구데기문제. 원래 조건이 2<=n<=1000, 1<=m<=2000 이었는데 m>n 일때 정해에서 잘못된 답을 내놓는 것이 대회중에 발견되어서 중간에 급하게 1<=m<=n 으로 조건이 바뀌었다. 정해(였던것)를 설명하자면, 한 냉장고를 private하게 만들기 위해서는 최소 두 개 이상의 다른 냉장고와의 체인 연결이 필요하니 전체를 하나의 사이클로 만들어주고 부족한 간선의 개수만큼 제일 cost가 작은 간선을 붙여주는 것이었다.
하지만 https://codeforces.com/blog/entry/71562 과같은 반례가 있었고, 결국 n==m일때만 가능, 그 외에는 전부 불가능한 구데기문제가 되어버렸다. 조건 바뀌기 전까지 이딴걸 대체 어떻게 2천명이나 풀었지?하고 멘붕하다가 바뀌고 나서 간신히 풀었다. 풀고나니 15분남아서 C 짜다가 대회종료. 구데기같은 내 실력을 다시한번 확인하는 대회가 되었다.
source : https://codeforces.com/contest/1255/submission/65382454 O(N2)
잘 생각해보면 어떤 한 냉장고에서 두 체인을 연결했다는 것은 ai가 각각 두 번씩 사용되었다는 것을 뜻하니 전체 코스트는 당연히 (ai들의 전체 합)*2가 되는것을 관찰한다면 더 간단하게 풀 수도 있다.
-ploffer11님의 풀이
source : https://codeforces.com/contest/1255/submission/65394140 O(NlogN)
-- 여기까지 대회중 solved
C. League of Leesins
이런 문제는 문제만 읽어서는 어쩌라는건지 사실 감이 잘 안온다. 예제를 살펴보자.
주어지는 숫자는 4 3 2 / 2 3 5 / 4 1 2 이고 얘네를 가지고 1 4 2 3 5를 만들어야한다.
반대로 답을 가지고 3개씩 잘라본다고 생각하면 1 4 2 / 4 2 3 / 2 3 5 가 되는데 잘 살펴보면 첫번째숫자와 마지막숫자는 딱 한번씩, 두번째숫자와 끝에서 두번째 숫자는 두번씩, 그 외에는 세번씩 나오는 것을 관찰할 수 있다. 따라서 첫번째와 두번째 숫자만 찾아주고 그 뒤부터는 ans[i] = (ans[i-1]과 ans[i-2]가 포함된 수열에서 ans[i-1]과 ans[i-2]를 제외한 나머지숫자) 로 전부 채워줄 수 있다. constructive algorithms 태그 달려있는 문제들이 다들 그렇지만 관찰이 어렵다기보단 구현이 귀찮은 문제.
source : https://codeforces.com/contest/1255/submission/65412911
D. Feeding Chicken
2차원배열이 아니라 1차원배열이라고 생각해보자.
전체 R의 개수를 cnt개라 한다면 배열의 맨 앞에서부터 보면서 지금까지 배정한 R의 개수가 cnt/K 개일때마다 끊고 다음 닭으로 넘겨주면 된다. 물론 cnt%K로 남는 값도 각각 하나씩 나누어서 붙여주는 처리도 해야한다.
2차원배열에서도 똑같이 생각해서 ㄹ자 모양으로 순회하면서 분배해주면 된다. 업솔빙하면서 대체 이게 왜 D에 있지라는 생각이 많이 들었다. B에 있어야하는거 아닌가 싶을정도의 난이도
source : https://codeforces.com/contest/1255/submission/65412898
E1. Send Boxes to Alice (Easy Version)
전체 1의 개수의 합을 M개라고 하자. 이 때 우리가 1들을 적당히 합쳐서 한 숫자가 여러개 나오도록 통일한다고 생각하면 만들 수 있는 수는 M의 약수들 뿐이다. 그럼 이 약수들을 하나씩 보면서 현재 i번째 1을 보고있다고하면 [i번째 1, i+k-1번째 1] 을 가운데로 모아주는데 이동이 몇번이 필요한지만 세주면 된다. 사실 구현을 잘못해서 5번정도 틀렸는데, 모으는 위치는 각 위치들의 합의 평균이 아니라 i+k/2번째 1이 있는 위치로 놓고 계산해주면 된다.
source : https://codeforces.com/contest/1255/submission/65422647
E2. Send Boxes to Alice (Hard Version)
이딴걸어케풉니까
F. Point Ordering
주어지는 점들이 볼록다각형을 이루고있고, 어떤 세 점도 한 직선 위에 있지 않음이 보장된다는 것을 생각하고 문제를 보자.
우리가 할 수 있는 것은 두 가지 쿼리이다. 세 점으로 이루어진 삼각형의 넓이는 몇인가, 두 벡터가 cw인가 ccw인가.
먼저 임의의 두 점(1번, 2번)을 잡고 나머지 점들에 대해서 ccw판정을 해보자.
판정을 하고나면 점들을 cw, ccw 두 집합으로 분리할 수 있는데 이 때 한쪽 집합에 대해서만 먼저 생각을 해보면 아래와 같은 그림과같은 형태가 된다.
이 때, 2->5->4->3->1 구간을 보면 높이가 계속 증가하다가 감소하는걸 알 수 있는데, 이 때 각 점의 높이는 1 2 3 / 1 2 4 / 1 2 5 가 이루는 삼각형의 크기를 각각 비교함으로써 구할 수 있다. 이는 세 삼각형이 각각 밑변이 같고 높이만 다른 삼각형이기 때문이다. 그 다음 1 4와 다른 점들에 대해서 ccw를 구해주면 이 점이 4보다 cw방향에 잇는지 ccw방향에 있는지 나눠줄 수 있고, 2->4로 가는 구간에서는 삼각형의 크기가 오름차순, 4->1로 가는 방향에서는 삼각형의 크기가 내림차순이라는 관찰을 했다면 크기순 혹은 크기역순으로 정렬을 해서 순서대로 출력해주면된다. 반대구간에 대해서도 마찬가지.
정리하면
임의의 두 점을 잡고 나머지 점들에 대해서 ccw판정, 삼각형 크기 판정 (쿼리 2n번)
양쪽 집합에 대해서 각각 삼각형의 크기가 가장 큰 점 확인
해당 점에 대해서 나머지 점들이 ccw인지 cw인지 판정 (쿼리 n번)
총 3n번의 쿼리 안에 판정할 수 있다.
source : https://codeforces.com/contest/1255/submission/65417321