Codeforces Round 909 (Div. 3)

Codeforces Round 909 (Div. 3)

이번 라운드는 여러모로 아쉬운 게 많은 대회였다... 못 푼 문제들이 다 뭔가 아쉽게 놓친 듯한 느낌이 들어서였다.

못 한 만큼 더 열심히 공부해야겠다.

 

---

 

 

B - 250 Thousand Tons of TNT

00:08 AC

 

$N$이 $K$로 나누어떨어지는 모든 경우에 대해 확인해보면 된다. 누적 합을 곁들이면 어떤 $K$에 대해 $O(\frac{N}{K})$의 시간이 걸린다.

 

 

A - Game with Integers

00:02 WA   00:09 AC

 

$N$이 3의 배수이면, 반드시 선공이 진다. 선공이 3의 배수에 +1 혹은 -1을 해도 후공이 다시 3의 배수로 만들어버리면 선공은 영원히 3의 배수를 만들지 못하기 때문이다.

반대로 $N$이 3의 배수가 아니면, 선공은 반드시 3의 배수를 만들 수 있다.

 

첫 코드를 제출하고 당연히 맞았겠지 싶어서 넘어가고 B의 풀이를 떠올렸을 때, 뒤로가기를 눌러보니 빨간색이 A를 뒤덮은 것을 보았다.

뭐지 싶어서 코드를 봤는데 3의 배수 판별을 N%3이 아니라 N&3을 하고 있었다.. 뭔 짓을 했던걸까.

 

 

C - Yarik and Array

00:15 AC

 

연속합 dp인데, 홀짝 제약만 추가해주면 된다.

$dp[i]$를 구할 때, $a_{i-1}$와 $a_i$의 parity가 같다면 $dp[i] = max(dp[i-1] + a_i, a_i)$이고, 다르면 $dp[i] = a_i$이다.

대회 중에는 "연속"이라는 언급이 없었던 걸로 기억하는데, 연속이 아니면 주어진 테케들이 성립이 안되길래 연속합으로 풀었다.

 

 

D - Yarik and Musical Notes

00:33 AC

 

가능한 $(a_i, a_j)$ 쌍이 거의 없다는 것을 파악하면 된다.

$(1, 2)$, $(2, 1)$을 제외하면, $a_i = a_j$인 경우만 성립한다.

따라서, map으로 각 수가 나온 횟수를 저장하면서 답을 구할 수 있다.

 

 

F - Alex's whims

00:48 AC

 

트리를 일자로 구성해놓고, 쿼리 $d$가 주어질 때마다 $1$번 정점과 $N$번 정점의 거리가 $d$가 되도록 적절히 옮겨주면 된다.

 

(E를 계속 보다가, 풀이가 도저히 생각나지 않아서 F로 도망쳤다.)

 

 

E - Queue Sort

01:10 WA   01:16 WA   02:07 WA   02:09 WA

 

처음에는, 같은 수가 연속되지 않으면서 존재하면 무조건 안 되는 줄 알았다. (WA)

같은 수들 사이에 그보다 더 작은 수만 존재하면 가능하다는 걸 확인하고, 구간 최댓값을 이용해 더 큰 값이 있는지 추가로 확인해줬다. (WA)

2 3 4 3 2 1인 경우에는, 위의 조건에 위배되어도 Queue Sort가 가능하다는 것을 알았다.

최종적으로, 다음과 같은 결론을 내고 제출했다. (WA)

$($구간 $A) a ($구간 $B) a ($구간 $C)$ 와 같이 어떤 수 $a$가 중복되어 나오는 경우에 대해, 

$\max {B} > a$이고 $\min {C} \ge a$이면, 불가능하다.

 

아직도 뭐가 잘못됐는지 모르겠다.

 

 

G - Unusual Entertainment

 

ETT + lazyseg로 비빌 수 있을까 했는데, 애초에 순열이 주어지기 때문에 불가능하다고 생각하고 포기했다.

ETT를 쓰는 것 까지는 확실히 맞는 것 같다.

그렇다고 가정하고, 순열을 대응시켰을 때의 각 점의 ETT.first를 나열한 배열을 새로 만들자.

그러면 문제는 특정 구간에서 $L$보다 크고, $R$보다 작거나 같은 수의 개수를 구하는 문제로 치환된다.

비슷한 문제를 백준에서 머지 소트 트리로 푼 적이 있는 것 같은데, 찍먹하고 넘어가서 자세히 기억이 나질 않아서 포기했다.

혹시 mo's인가..? 했는데, 나는 mo's를 언제 써야하는지만 대강 알고 구현할 줄 모른다.

그래서 남은 시간을 그나마 가능성있는 E에 몰빵하기로 했다.

---

Rating

+162

1244 $\rightarrow$ 1406

 

1900점까지 올리는 것을 목표로 잡으려고 한다. 퍼포먼스를 보면 아직 한참 부족하지만, 계속 하다보면 언젠간 늘 거라고 생각하고 해야겠다.