랜덤디펜스 4일차

https://master.d66dlzauezpcp.amplifyapp.com/pentagon03

랜덤디펜스를 더 돌렸다. 요번에는 어려운 문제들이 대거 등장했다.

 

 

---

8160

Trains

플2

PASSED,  UPSOLVED

 

거의 보자 말자 해싱 풀이가 나왔는데, 돌발적인 다른 이슈랑 Hasher struct를 어디서 가져와서 쓰려다가 말려서 실패했다. Rolling Hash를 구현했는데 WA를 받길래 포기하고 Dot Product를 쓴 koosaga님 구현을 가져왔다.

RabinKarp(Polynomial Hash)는 이제 문자열을 Shift한다던지, reverse한다던지, 다항식 자체의 성질을 사용하는게 아니라

단순히 Array를 저장하고 각 위치를 swap하는 정도의 단순한 연산만 있는 경우 Dot Product를 활용한 Hash가 굉장히 쉽고 간단해보인다. 특히 이런 문제의 경우 일반화하려고 시간을 날리는 경우가 참 많다. 

코포에서도 Hash가 정해인 문제가 조금씩 나오고 있는데 Rabin Karp 라이브러리도 아직 TODO다..

Dot Product를 이용한 Hasher

 

---

17194

Balancing Inversions

플2

PASSED, UPSOLVED

 

유사코가 문제는 참 좋다.. 오랫동안 생각했는데 실마리들이 연결이 안돼서 에디토리얼을 봤다.

핵심은 이제
(1) Center에서 swap을 할 때 Inversion의 Difference가 불변량이다. (n - # of 1's)

(2) 계속 같은 방향으로Center  swap 하는것이 최적이다. (0,1) swap 하고, (1,0) swap 하는 경우 낭비임.

(3) Center Swap을 x번 한 경우, x+1번 하기 위해서 투 포인터로 쉽게 구해줄 수 있다. 그리고 각 케이스에서 두 inversion의 차이만을 이용해서, inversion이 더 큰쪽에서 줄여줄 수 있다. 

에디토리얼 구현이 좀 이상한데, 더 간단하게 할 수 있다.

 

---

14412

Ronald

플5

29분

 

난이도 치고 되게 오래 걸렸다. 정점을 누르는걸 '전구 스위치'라고 생각하면 두 번 이상 누르는건 redundant하다.

i, j를 잇는 간선에 대해 OR 식을 세워줄 수 있으므로 2-sat으로 풀린다. 

다만 이제 스위치 문제처럼 정점 1의 스위치 여부가 결정되면 2-coloring 문제로 환원되므로 간선타고 가면서 그리디하게 색칠해줄 수 있다. 이분 그래프 . . .

 

---

4718

Not One Bit More

플4

54분

 

이것도 시간을 간신히 맞췄다. 재귀적으로 생각해보면 각 X에 대해서 켜져야 할 비트의 수를 알 수 있고, 이를 세는 것은

K이하의 수중 cnt만큼의 비트 수가 켜진 수의 개수로 dp를 돌리면 된다.

dp(flag, idx, cnt): 현재 K의 idx번째 비트를 큰 순으로 보고 있으며 flag는 K[idx]보다 커도 되는지 여부, cnt는 켜야 하는 비트의 개수. 

digit dp 유형 중 bitmask를 적용한 유형 중 하나다. 많이 풀어봤으면 쉽고, 안 풀어봤으면 잘 생각을 못하는 유형.

 

---

30976

사랑의 큐피드

플4

12분

 

6분만에 풀었다. 누르는걸 까먹음. 너무나 직관적인 이분매칭이다. 같은 플4라는게 믿기지 않을 정도.

 

---

28687

재우의 Pass를 사수하라!

플5

62분

 

오늘 랜디는 여기까지다. 다시는 하기 싫은 구현이다. PASS 하려다가 꾹 참고 했다. 틀릴 여지가 많다.