codejam 2018 R1B R1C practice

2020 R1 A 시작 전에 연습

 

2018 R1B

 

https://codingcompetitions.withgoogle.com/codejam/round/0000000000007764/0000000000036601

Code Jam - Google’s Coding Competitions

풀다가 large data set을 못 풀어낼 것 같아서, 해답을 봤다. 좀 더 과감하게 중요한 부분만 직관적으로 생각할 걸 그랬다. 

 

https://codingcompetitions.withgoogle.com/codejam/round/0000000000007764/000000000003675b

Code Jam - Google’s Coding Competitions

문제를 이해하기가 너무 어려워서 포기

 

analysis와 https://www.youtube.com/watch?v=BFr6bGLq3r4 해설을 봤더니, 문제를 이해했으면 비교적 풀기 쉬었을 것 같다.

 

https://codingcompetitions.withgoogle.com/codejam/round/0000000000007764/000000000003675c

Code Jam - Google’s Coding Competitions

이것도 영어 이해하기 헷갈리게 왜 lead가 귀하다고.. 엄한 데 시간이 든다.

생각한 방법을 구현하다가 Test set 3를 풀려면 구현이 너무 복잡할 것 같아서 해답을 봤다.

analysis를 봤더니, 생각한 방법이 Test set 2만 풀 수 있는 방법이었나보다. 차례로 잘 소비하면 3도 풀 수 있을 것 같은데...

Test set 3용으로는 완전 색다른 풀이 방법이 있었다.

 

https://www.youtube.com/watch?v=c2yuORofkAw 31분쯤을 보니, 이 분도 조금은 비슷하게 생각하신 듯

듣고 보니, Test set 3용 풀이가 생각보다 simple하게 구현할 수 있고, 실행 시간도 적게 걸리네.

 

 

 

R1C

 

https://codingcompetitions.withgoogle.com/codejam/round/0000000000007765/000000000003e064

Code Jam - Google’s Coding Competitions

각 위치의 글자가 어느 단어에 속하는지 기록하고, 글자를 이어갈 때마다 속하는 set의 교집합을 구해서 교집합이 null이면 해답이 나오도록 풀려고 했다.

각 2개 sub단어에 대해서만 만족한다면 긴 단어에서도 만족하게 될테니, 글자를 이어갈 필요가 없겠는데, 그렇지 않은 경우도 있겠다 싶었다.

divide and conquer가 실행속도를 더 빠르게 할지 생각하고 있었다.

 

해답은 썰렁했다.. 왜 점수가 저만큼 높은지 모르겠네.

 

https://codingcompetitions.withgoogle.com/codejam/round/0000000000007765/000000000003e068

Code Jam - Google’s Coding Competitions

는 문제를 잘 이해를 못했다. 어려운 것 같지는 않다. skip.

 

online algorithms

https://www.youtube.com/watch?v=IyWOjd-oZ4o&list=PLjbPFHE4z0zcsmzMPOg-J16SIDS3t0ylw

bipartite matching이랑도 관련이 있다길래 찾아봤는데, 무슨 관련이 있는지 잘 모르겠다.

 

https://www.youtube.com/watch?v=dorq_YA6plQ&list=PLEGCF-WLh2RJh2yDxlJJjnKswWdoO8gAc&index=2&t=0s

lesson 2부터는 녹음이 잘 돼있어서 소리가 크게 잘 나온다.

 

https://www.youtube.com/watch?v=0CdxkgAjsDA

https://www.youtube.com/watch?v=GhjwOiJ4SqU 

https://www.youtube.com/watch?v=HWHjQdNC-7Y

 

 

 

https://codingcompetitions.withgoogle.com/codejam/round/0000000000007765/000000000003e0a8

Code Jam - Google’s Coding Competitions

DP까지는 생각했는데, test set 1 밖에 풀 수가 없다.

test set 2에서는 max(W)를 무한정 늘어나지 않게 하는 trick이 있었다.

 

DP를 연습삼아 풀어보는 것도 좋겠다.