Codeforces Round 938 (Div. 3)

(2/8)

 

B번을 한시간동안 풀어버려서 시간이 많이 부족했다. 좀더 열심히 해야겠다.

---

C

에디토리얼 보니까 생각자체는 맞았는데 풀진 못했다. 그대로 구현하고 제출했으면 맞았을거같은데 B에서 시간끌린게 너무 큰거같다.

 

문제

크라켄이 맨앞/맨뒤의 배를 순서대로 공격한다. 

공격 한번당 배의 내구도는 1씩 감소하게 되고, 내구도가 0이된 배는 침몰한다. 그렇다면 침몰하는 배의 개수는?

 

 

접근

공격 횟수 k가 10^15이기 때문에 완전탐색으로 접근하는 것은 불가능하다. 매우 큰 수 가 입력되기 때문에 수학적인 테크닉이 필요할 것이라고 예상되는 문제였다.

 

문제 자체는 이해하기 쉬웠고, 어떻게 반복문의 횟수를 줄이냐. 라는 생각으로 이 문제를 접근하게 되었다.

 

배가 침몰하면 앞/뒤로 다른 배가 공격을 받게 되고, 배의 개수는 최대 2*10^5개 이므로 배의 개수가 기준이 되어 문제를 풀어야 겠다고 생각했다.

 

그러므로 맨앞/맨뒤 두개의 배를 기준으로, 두개의 배의 내구도 중 작은 값을 구한다. (minDuration)

minDuration * 2가 크라켄이 얼마나 공격을 하는지에 대한 정보이므로

K(크라켄의 공격 횟수)가 minDuration*2보다 크다면

K -= minDuration * 2; 
arr[l] -= minDuration; // 첫번째 배
arr[r] -= minDuration; // 마지막 배

 

K가 minDuration * 2보다 작다면 

if(k%2 == 1){
	arr[l] -= k/2+1;
    arr[r] -= k/2;
}
else {
	arr[l] -= k/2;
    arr[r] -= k/2;
}

를 해주게 된다.

 

여기서 K가 홀수라면 무조건 첫번째 배를 한번 더 때리기 때문에 다음과 같이 계산이 된다.

 

이 과정을 반복해서 K가 0이 되거나, 맨 앞 배를 가리키는 l , 맨 뒤 배를 가리키는 r이  l > r이 된다면 더이상 공격을 할 수 없으므로 종료하면 된다.

 

l == r 인 경우(배가 한대 남았을 경우)만 따로 생각하여 비교해주면 된다.

---

D

길이가 N인 정수 배열, M인 정수 배열이 주어지고(N>M) M의 원소들을 나열해서 N의 subsequence에 맞는 원소의 개수가 K개 이상인 경우의 수를 구하여라.

 

길이가 N인 배열의 0 ~ M-1 인덱스 기준으로 길이가 M인 배열의 원소의 개수를 저장해 슬라이딩 윈도우로 체크하는 방식을 생각했지만

2N + M의 시간복잡도로 대략 3초정도 나와서 실패했다..

 

에디토리얼을 보니 아이디어 자체는 이게 맞았다.

다만 멀티셋을 사용해서 체크하는 방법은 생각하지 못했다. 값이 중복될 수 있기 때문에 멀티셋을 사용했다. 중복되지 않는다면 셋을 사용하면 될거같다.

 

---