2020 ICPC 지역예선 후기

일단 같은 학회원 pkpete님과 bbk0723님과 대회에 참여하였다.

 

우리는 프린트가 되지않는 환경이었기에.. 본인의 실수로 예약을 잘못함

모두 같은 문제를 동시에 A~L까지 훑어보고 논의 후 쉬우면 바로 한명 코딩으로 진행하였다

 

A Ball Alignment

 

정렬에 대한 문제였다. 오름차순으로 정렬을 해야하는데 오른쪽 끝 아니면 왼쪽 끝으로만 이동 할 수 있고, 

횟수 몇 번이 최소이냐를 구하는 문제였는데 

 

어려웠다 왼쪽으로 보내는 조건과 오른쪽으로 보내는 조건을 계속해서 찾으려 했지만 보이지 않았고, 알 수 있었던 건

최대 N-1번이면 정렬이 된다는 사실 하나? 

그렇게 쉬운 문제를 넘긴다는 불안함을 가지고 B로 패스

 

B Bit String

 

이 문제를 보는 중에는 사실 A를 내가 계속 보고 있었기 때문에 문제가 정확히 어떤식으로 흘러갔는지는 기억은 못한다

근데 문제를 봄과 동시에 어렵다 못 풀겠다라는 생각이 들어서 바로 패스로 진행했던 것 같다 

 

아 이때가 한 30분 지났을 때여서 우리는 스코어보드를 확인 하였고, I가 올 초록인걸 확인하고 이제부터 많이 푼 문제 순으로 풀자라고 하고 넘어갔다.

 

I Project Teams

 

문제를 보자마자 그 정렬한뒤에 맨 앞 맨 뒤 합하는게 차이를 가장 적게 만드는 것이라고 얘기가 나와서 확인을 한 후에 뚝딱해서 바로 통과

 

다음 문제인 E로 패스

 

1solve

 

E Cycle Game

 

사실 프린트를 해서 본 것도 아니고 문제전체로 본 것도 아니기 때문에 우리는 문제들이 한글화되어 있는거를 이 문제부터 알았다.. 이게 다 내 부주의라는게 현실

 

아무튼 이 문제는 사이클확인하는 문제인데 유니온 파인드 얘기가 나왔고, 확인 후에 또 구현을 뚝뚝하였다.

 

2solve

F로 패스

 

F Escaping 

 

경도 문제이다 경찰과 도둑 ㅋㅋㅋ 

거리와 대칭 그리고 대각방향 도둑과 경찰과 위치관계 두 명일때 세명일때 여러명일때 

계속해서 얘기를 해보았지만 어떤 알맞은 답을 찾지를 못했다. 

 

아마도 우리가 손 댄 문제중에 가장 많은 얘기가 오간 문제가 아닐까 생각한다. 

 

슬프지만 K로 패스

 

K Road Reconstruction

 

bfs라는 얘기가 나왔고, 좀 생각을 해본다음에 구현을 시작했다. 

dp[][]로 해당 위치에서의 가장 낮은 코스트를 저장하도록 하였고, 그 코스트는 계속해서 갱신되는 것으로 더 높거나 같으면 들리지 않는 것으로 짜보았다 

 

하지만 기대와 달리 TLE 그래서 pq로 cost가 가장 최소일 때로 짰고, 

 

3solve

근데 오늘 보니깐 다익스트라면 훨씬 간단하게 풀렸을 것 같기는 하다. 

다익스트라를 푼지 좀 되서 더 늦게 구현했을지도 모르겠지만 

 

L로 패스

 

L Sliding Coins

 

사실 F랑 K사이쯤에? 봤던 것 같기도 한데 그때는 브루트포스라는 얘기가 나와서 일단 스킵하고 다른 문제를 보고왔었다. 

근데 대충 O(N)으로 뚝딱 가능한 것 같아서 팀원들과 얘기 후에 구현을 시작하였다. 

 

어떤 방법이었냐면 

 

a[],b[] 두 OXXOXOX이런 것이 있으면 

a[]에서 제외되는 두 idx를 빼고 다른 배열에 저장후

b[]와 하나하나 비교, 최초로 다른게 나오는 index에서 스탑후 

뺐던 첫 인덱스를 그 사이에 넣은 다른 배열을 생성

다시 b[]와 비교, 최초로 다른게 나오는 index에서 스탑후 

다시 두번째 인덱스 넣고 다른 배열 생성 

만약 비교시에 b[]와 다른 게 나오지 않으면 가장 뒤에 넣으면 된다.

 

그 뒤에 b[]와 전체 비교하고 다르면 NO

같으면 YES출력으로 하였지만 

 

WA

 

 

사실 어제잘때도 생각해보고 오면서도 생각해봤는데 어디에서 반례가 있었길래 틀린건지 모르겠다

 

이문제도 종료 1,2분 전에 구현이 완료되어서 같은 알고리즘으로는 반례체크도 못했고, 아쉽다 

 

------------------------------------------------------------------------------------------------------------------

아니 .. 10/12 15:00 지금 다시 해봤는데 논리에는 문제가 논리에는 문제가 없는거(Proof by AC)였고,, 내가 구현을 개똥같이해서 index 실수한것같다 너무 급하게 짜서 그런실수를 하다니 너무 아쉽,,,,,,,,,,,,,,,,,,,,,, 좀 분하다 

------------------

그 경도 계속 보다가 반례체크를 해봤는데 L번 반례가 존재한다. 아마도 백준 테스트케이스 구성이 좀 부족했던 듯? 

3
xox
xxo
1 2

이 경우 (순서를 고려해줘야하는 경우) 

 

순서를 구성하고 나서 O(N)으로 구현이 가능한 것같으니깐 한번 짜봐야겠다. 

----------------------------

그 저 코드로 왜 짰는지를 생각해보니깐 생각보다 반례가 쉽게 나왔고, (알고있어서 그런걸수도 있겠지만)

보완도 쉽게 할 수 있었다.

 

 

아무튼 그래도 진짜 열심히 풀었다 

열심히 푼게 다는 아니지만 그래도 마지막에 L을 구현까지 하고 제출까지 해서 틀린걸 봐서 더 기분좋게 끝맺음이 가능했던 것 같다 

 

내년에는 진짜로 실력을 갈고닦아서 나가자 

열심히해보자