Codeforces Round #598
A. Payment Without Change
요약 : q개의 케이스가 주어지고 각 케이스마다 n의 가치를 가진 동전 a개와 1의 가치를 가진 동전 b개가 주어진다. 이 때 이 동전들의 가치의 합을 정확히 S로 만들 수 있는가?
min(S/n,a)*n + b >= S 인 경우 가능하고 그 외의 경우 불가능하다. S를 넘지 않는 선에서 n동전으로 최대한 채우고 나머지를 1원 동전으로 채운다고 생각하면 된다.
곱하는 과정에서 int 범위를 넘을 수 있음에 주의하자.
source : https://codeforces.com/contest/1256/submission/64343898
B. Minimize the Permutation
요약 : [1,n]으로 구성된 임의의 순열이 주어진다. 이 순열의 [1,n) 위치에서 i와 i+1번째 원소의 위치를 서로 바꾸는 작업을 할 수 있는데, 각 위치마다 작업은 최대 1번씩만 할 수 있다. 이 때 만들 수 있는 사전순으로 가장 앞선 순열은 무엇인가?
지문이 이상한건지 내가 해석을 이상하게 한건지 n-1개의 operations가 있는데 ith operation에 i와 i+1의 위치를 바꿀수있다고 쓰여있어서 무조건 i가 증가하는 순서로 위치를 바꿔야하는건가 한참 생각하다가 예제를 보고 그런거 상관없이 그냥 대충 바꾸면 된다는걸 알았다.
사전순이라는 것이 맨 앞부터 비교했을 때 작은 값이 먼저 나온쪽이 뒤에 숫자는 어떻든간에 앞서기 때문에 이런 div3에서 lexicographically minimum 혹은 lexicographically maximum 하게 만들어라 라는 말이 나온다면 일단 가장 작은/가장 큰 숫자를 제일 앞으로 당겨올 생각을 하자.
이 문제는 가장 앞선 순열을 만드는 것이기 때문에 i번째 시행에서 숫자 i를 앞에 숫자가 자신보다 큰 동안 쭉 끌어오면 된다. 단, 한 위치에서는 1번까지만 시행할 수 있기 때문에 위치마다 시행했는지를 기록하는 배열을 하나 만들어주고 이미 시행된 적이 있다면 그냥 넘어가면 된다.
source : https://codeforces.com/contest/1256/submission/64217314
C. Platforms Jumping
요약 : 강의 넓이 n과 발판의 개수 m과 한 번에 뛸 수 있는 최대 길이 d가 주어진다. 다음 줄에는 i번째 발판의 길이 ci 가 주어진다. 발판을 적절히 밀거나 당긴다음 사람이 뛴다고 했을 때 0의 위치에 있는 사람이 n+1위치까지 갈 수 있는지 판단하고 이 때의 발판의 위치를 출력하라.
발판의 위치를 출력할 필요없이 그냥 갈 수 있는지 여부만 판단한다고 생각하면 너무 쉬운문제가 되어버린다. 그냥 무조건 d씩 뛴다고 생각하고 n/d개 만큼의 발판이 있는지만 확인하면 되니까.
근데 이 문제에서는 단순히 그렇게 할 경우 쓰이지 않는 발판이 있을 수 있기 때문에 출력할 때 답이 이상하게 나오는 경우가 생긴다(예제 2).
그래서 변수 몇 개를 정의하고 조건을 나눠서 생각해보았다.
cur : 사람이 있는 현재 위치
r : 남아있는 강의 길이
sum : 남아있는 발판의 길이의 합
r==sum 인경우 남은 발판을 그대로 다 깔아주면 된다.
r<sum 인 경우는 없으니 남은 경우는 항상 r>sum일텐데, 이 때 매 시행마다 d칸씩 뛴다고 생각해보면 처음으로 rnext<sumnext이 되는 rcur 지점이 생길 것이다. (rnext = rcur-d - i번째 발판의 길이 + 1)
딱 이 부분에서만 d칸을 뛰지않고 rnext가 sum과 같아지도록 뛰면 나머지부분은 자연스럽게 발판으로 전부 채워질 것이다.
모든 시행을 돌았을 때 cur + d가 N이하인경우 N+1위치에 도달할 수 없으며 그 외의 경우는 도달할수 있으니 답을 출력해주면 된다.
짜면서 삽질을 좀 해서 이 문제에서만 거의 50분 쯤은 쓴거같다. 테케도 부실해서 cur + d <= N이 아니라 cur + d < N 으로 마지막에 체크한 경우도 통과하는 바람에 시스텟때 터진 사람이 엄청나게 많았던듯. 하튼 C가 문제다. C하는 놈을 혼내줘야한다.
source : https://codeforces.com/contest/1256/submission/64245545
D. Binary String Minimizing
요약 : 0,1로만 이루어진 string이 있는데 인접한 두 수를 최대 k번 swap해서 사전순으로 가장 작은 string을 만들어라
또 lexicographically minimum이다. 숫자는 0과 1밖에 없으니 매 시행마다 제일 왼쪽에 있는 0을 최대한 앞으로 당겨주면 될 것이다. 단, 숫자의 개수가 106개이니 일일이 스왑하는 것이 아니라 i번째 0을 string의 i-1 인덱스의 위치로 옮긴다고 생각하고 swap을 해주자.
B랑 비슷한 수준의 난이도이고 C보다도 쉬웠던 문제.
source : https://codeforces.com/contest/1256/submission/64236050
E. Yet Another Division Into Teams
dp라는데.. 잘모르겠다.....보이지도않고.... 아는 사람이 추가해주세요.....
F. Equalizing Two Strings
요약 : 같은 길이를 가진 두 string s,t 가 주어진다. 이 때 한 string에서 원하는 길이만큼 골라 해당 구간을 뒤집을 수 있는데, 한쪽 string에서 len만큼의 길이를 뒤집었다면 다른쪽 string에서도 동일한 길이만큼 뒤집어주어야한다. 단, 뒤집는 길이만 같다면 뒤집는 위치는 상관이없다. 이 때 s와 t를 동일하게 만들어 줄 수 있는가?
사실 문제만 읽어서는 뭔소린지 감이 잘 오지않는다. 이럴 때는 예제를 읽어보자.
abcd
abdc
그냥 딱 봐도 안되게 생겼다. 위에서 cd를 뒤집으면 밑에서도 뭔가 2길이만큼을 뒤집어줘야하는데 같아지게 만들수가없다.
asdf
asdg
너무 당연히 안된다. 알파벳 구성부터가 다르니까
abcd
badc
위에서는 ab를, 밑에서는 dc를 뒤집어주면된다. 똑같은 2길이씩.
ababa
baaba
이게 왜 yes인지 몰라서 한참 헤맸다.
밑에서 aa를 고르고 위에서 ab를 고르면 baaba로 같아진다.
이 예제마다 관찰을 하나씩 할 수 있는데, asdf/asdg에서는 알파벳 구성개수가 다르면 무조건 불가능하다는 것을, ababa/baaba에서는 구성개수가 동일하고, 같은 알파벳이 2개이상 존재하면 무조건 가능하다는 것을 알 수 있다. (어떤식으로든 같은 알파벳 두 개를 붙여놓으면 얘네 둘은 뒤집어도 동일한 결과가 나오기 때문에 반대쪽에서 원하는대로 연속한위치 2개씩을 원하는 횟수만큼 swap할수 있기 때문)
abcd / abdc 와 abcd / badc 에서는 cd/dc , ab/ba + cd/dc 를 꼬인 상태라고 생각해보면 꼬인 횟수가 홀수이면 불가능, 짝수이면 가능인 것을 알 수 있다. 즉, inversion counting을 했을 때 카운팅결과가 홀수인가 짝수인가를 묻는 것이다.
따라서 절대 안되는경우(알파벳 구성이 다름)를 먼저 제외하고, 무조건 되는경우(같은 알파벳이 2개이상있음)를 처리해주고, 나머지 경우에 대해서 inversion counting 개수를 세주면된다.
문자열 길이가 최대 20만이지만 어차피 저 경우를 제끼고나면 최대케이스가 a~z까지 골고루 존재하는 26길이밖에되지않으므로 그냥 n2으로 구해줘도 상관이없다.
근데 나는 https://www.acmicpc.net/problem/7578 여기에 제출했던 mergesort 코드를 그대로 복사해와서 제출했다.
source : https://codeforces.com/contest/1256/submission/64253543
boj 7578 source : https://www.acmicpc.net/source/share/bad66a37f0e64ceda80e5bdde265e8d1