제 2회 유틸컵 후기

처참하다

6시간 눈물의 똥꼬쇼

 

전체적으로 정말 퀄리티 높은 대회였다. 머릿속으로 아이디어를 떠올려도 그것을 코딩으로 구현해내는 능력이 부족하다고 느낀 요즘이였는데, 긴 시간동안 엄청난 양의 구현을 해야하는 좋은 문제들을 풀어 볼 수 있어서 12시간이 아쉽지 않은 경험이였다. 이정도면 검수진 분들도 굉장히 고생하셨을텐데.. 양질의 대회를 열어주신 utilforever님과 검수진 분들에게 감사의 인사를 전합니다..!

 

 

☕🔤🟰번 ac

b가 null인 경우만 조심하면 된다.

 

🅰️✖️🅱️번 ac

뒷 자리 부터 곱해가며 문자열 형태로 합치고, 원래 곱과 비교하면 된다.

 

🏁✂️번 ac

문제에서 하란대로 잘 채우면 끝. 조건이 빡빡하진 않아서 대충 부족하지 않을 정도로만 채워주고 판 크기에 맞게 출력하면 된다.

 

🔁♾️번 ac

처음에는 모든 쌍을 전부 검토해도 tle를 안받을 줄 알고 빠르게 구현했는데, tle를 받아버렸다.

원하는 만큼 한 배열의 두 원소를 바꿀 수 있다는건 결국 배열의 모든 원소는 위치가 어디로든 갈 수 있다는 뜻이다.

따라서 a,b를 정렬하고 비교해도 충분하다.

 

🤔🤡번 ac

이해하는데 좀 고전했다. 턴은 주사위를 굴리는 매 순간이고, 주사위 눈이 1이 나와서 새로운 게임을 시작할 때

매 턴 흘러가는 시간, 점수, 주사위를 굴렸을때 얻는 기본 점수 모두 초기화된다.

...라고 알고 풀었는데, 알고보니 전체 시간도 초기화되는거였다. 지문을 깊게 생각해보면 게임이 새로 시작된 시점에서 240초가 초과되면 종료라고 했으니, 주사위 눈이 1이 나와서 새로운 게임을 시작할 때에도 시간은 초기화 되는게 맞다.

 

🟥🟩🟦번 ac

누적합으로 O(N^3)에 풀었다. 사실 처음에는 이게 정해가 아닌거 같아 tle를 받을까 걱정스러웠다. 그런데 제한 시간이 1.5초 인걸 보고, 이건 일부러 500^3 = 125,000,000에 맞춰서 시간을 1.5초로 정한거구나! 하고 O(N^3) 코드를 제출했고 ac를 받았다.

 

🏭🔴번 wa

17번 제출해서 결국 실패한 문제다. 이 문제만 맞췄다면 7솔로 뱃지/배경 올클리어 인데, 정말.. 너무 아까웠다.

나머지는 비교적 구현이 쉽지만, 가장 문제는 결합하는 쿼리이다. 각 층마다 통과되는지 아닌지 여부만 가지고 a,b를 결합하려고 하면 반드시 반례가 생길 수 밖에 없다. 그렇다고 모든 층을 각각 비교해도, a위에 b를 놓고 결합했을때는 나올 수 없는

Rr------:RrRrRr--  +  --AuAuAu:------Au -> RrAuAuAu:RrRrRrAu 이런 모양이 나오기도 한다.

필자는 각 층의 조각마다 블록의 유무를 1,0으로 나타내고 1층부터 4층까지를 각각 기준으로 하여 결합했을 때 가능한 모양중 결합된 층이 최소인 모양을 골랐다. 이렇게 되면 4층까지 모두 결합되기 위해선 반드시 1층에서 부터 결합을 시작했을때에도 4층까지 온전하게 결합이 완료되어야 하기 때문에 자체 교차검증이 되어서 항상 올바른 결합을 해낸다.

근데 wa를 받았다!@@@

처음에는 런타임에러가 떠서 도대체 어디서 틀린건가 싶어 try문을 여러번 걸어가며 몸으로 박치기했고, 겨우 찾아 해결하고 나니 받는 wa는 너무나 슬펐다.

이 문제를 도전하면서 문자열에 대한 깊이있는 이해를 더 많이 하게 되었다. 하지만 6000Byte가 넘어가는 코드에서 틀린부분 찾기하는건 너무 힘들다.. 6시간을 갈고 끝내 실패했으니 허탈감도 더욱이다.

 

😾📚번 tle

🏭🔴번 풀다가 잠시 포기하고 도전했던 문제. 결과적으로 더 갈렸는데, 미친듯이 구현하고 예제를 한번에 통과하면서 매우 들뜬 마음으로 대회 종료 3분을 남기고 제출했고, 그대로 tle를 받고 벙쪘다. 아마도 정렬을 내장함수로만 사용해서 비효율적이게 동작하지 않았나 싶지만, 3분만에 뭘 할 수 있지는 않았다.

 

🔁2️⃣번 pac

4점은 거저주는 문제이고, 꽤나 고민을 오래했었다.

우선 배열 a에서 두 원소의 위치를 바꿔서 k점을 얻을 수 있으면, 배열 b에서도 마찬가지로 두 원소의 위치를 바꿔서 k점을 얻을 수 있다.

따라서 배열 a에서만 움직이는걸로 생각해도 충분하다.

어떤 상황에서도 2점을 얻을 수 있는 경우 그렇게 하는게 최선이다.

그렇지 않은 경우, 사이클을 찾아야한다.

k=1일때는 그냥 2점을 얻을 수 없으면 1점, 1점을 얻을 수 없으면 행동하지 않는걸로 하면 최선의 결과가 나온다.

k=2일때도 역시 2점을 얻을 수 있으면 얻는게 최선이지만, 그렇지 않다면 어떤 1점을 얻어야 할지 고민이 된다.

a = 1 2 3 9 7

b = 3 1 2 5 9

이경우 만약 a의 4,5번째 원소를 선택해서 1점을 얻으면 이후 2번째 행동에서도 1점을 얻고, 최종적으로 원래보다 2점을 더 얻을 것이다.

하지만 a의 1,2번째 원소를 선택해서 1점을 얻으면 이후 2번째 행동에서 a의 2,3번째 원소를 선택해서 2점을 얻고, 원래보다 3점을 더 얻을 수 있다.

그렇기 때문에 원소가 1점을 얻을 수 있는 index들을 간선으로 해서 방향그래프를 그리면 사이클을 판별 할 수 있고, 사이클의 길이가 2라면 2점을 얻는 행동, 사이클의 길이가 3이라면 1점을 얻고 이후 2번째 행동에서 2점을 얻어 총 3점을 얻는 행동이다.

여기까지 생각하고 스코어보드를 보니, 아직 아무도 이 문제를 ac하지 못했어서 이렇게 쉽게 풀릴리가 없다는 생각을 좀 했다.

문제 자체도 뒤에 있었던 터라 빠르게 포기하고 다시 앞 문제로 넘어갔다.

+ 3/7

태그가 역대급이다.

 

🌙⛏️번 ???

배경 조건이 수정되었는데, 대회 중에 700점 이상을 받거나 🌙⛏️번 문제를 푸는것이였다.

대회가 아니여도 이 문제를 풀면 해당하는 배경을 준다고 한다.

상시 조건으로 문제 하나만 풀면 대회 700점과 똑같은 배경이라니, 혹할만 하다고 생각했다.

 

미래의 루비1 문제를 관측한 것 같다..