suapc 2021 후기

결론부터 말하자면 7등 장려상을 받았다.

남들이 다 푸는 문제만 맞추고 적당히 J번 뇌절하다가 죽은 대회였던거 같다.

 

likelon,jkroll87(이하 박건)으로 팀을 짜서 나갔다.

아마 내가 올해부터는 다른 팀에서 할거 같기에(아직 팀원은 못 구했지만서도..) 이 팀으로 진행하는 마지막 대회였다.

팀 연습은 한두번했나? 어쨌든 거의 못한 상태로 대회에 들어갔다.

코로나땜에 랩실이 폐쇄된 관계로, 10시반에 만나서 신촌 스터디룸을 잡으러 갔다.

 

적당히 잡고 12시에 시작한다!

 

우리팀의 문제 풀이 전략은 이렇다. 사실 supac는 컴퓨터가 3대라 전략이 다들 비슷비슷 할 거 같지만, 내가 앞에 4문제,

건이가 중반 4문제, likelon이 후반 4문제를 잡는다.

 

그리고 풀이가 보이면 바로 풀고, 할만한 거면 바로 푼다.

결과는 만족스럽지 않지만, 사실 현재 실력에서 이론치로 낼 수 있는 거의 최상의 퍼포먼스가 아니었을까 한다.

더 노력하자.

www.acmicpc.net/category/detail/2446

2021 신촌지역 대학생 프로그래밍 대회 동아리 연합 겨울 대회 (SUAPC 2021 Winter)

 

Time Line

(AC만 적겠다)

 

 

I. 팰린드롬 척화비(2min) 

likelon이 퍼솔했다. 그냥 저냥 코포 A번 적합한 문제이다. 사실 더 빨리 풀 수 있었는데 형이 혹시나 하는 마음에 우리한테 풀이 체크하다가 조금 느려졌다.

 

B. 떡국(9min + 1try)

내가 풀었다. 난 멍청이다. 진짜.... 그냥 이것도 코포A번 같은 문제이다. 나는 근데 처음한번을 바보 같이 lis인줄 알고 코드가져와서 박아넣었다가 틀렸다. 다른 팀들이 쉽게 쉽게 맞추는 모습을 스코어보드상에서 보고, 쉬운 문제인 줄 알고 생각의 틀을 전환해서 AC.

 

L. 습격받은 도시(31min)

likelon이 풀었다. 일명 크레이지 아케이드 문제. 쨌든 AC!

 

H. 카카오톡(39min)

jkroll87이 풀었다. 문제도 모른다. 쨌든 AC!

 

K. 합성인수분해(42min+3try)

쉽다. 진짜 쉬운 문제다. 한가지 알아야 할 점은 내가 초급 마지막 강의에서 소인수분해를 강의했다는 점이다!

3try한 이유. 두 번 그냥 틀리고, 아 소인수가 3개이하여도 합성인수 분해가 가능할수 있구나! 
를 깨닫고 바꾸다, 코딩오류로 한번 더 틀렸다. 반성하자. 구현실력,경험 부족이다.

 

K까지 풀고 서로 남은 문제들을 공유하고,

건이와 나는  스코어보드 상에서 많이 시도되던 F번을 잡고 likelon은 무언가 풀만한 문제들을 찾으러 갔다.

하.. F번 못풀었으면 나는 진짜 너무 슬펐을 것이다.

 

우리는 꽤 많은 아이디어를 떠올렸는데, 처음에 jkroll87이 mst가 아닐까?하는 아이디어를 떠올렸다.

난 천재인줄 알았다.

 

근데 생각해보니까 간선 갯수가 너무 많아진다. 아니다.

 

두번째로 내가 Ad-hoc한 규칙에 의하여, cost가 2이상인 간선들은 이을 필요 자체가 없을 것 같다고 추측했다.

따라서 비트마스킹을 적절히 활용해서, 그 정점이 사용되었는지 checked배열을 통해서 나타내고, 적절히 bfs하면, 모든 경로를 추출함과 동시에 답을 풀수 있겠다는 O(n*2^n)인 풀이를 떠올렸다.

미친 실수였다..

진짜 시간을 너무 날렸다.

우선 이건 안된다.

시간복잡도가 틀렸다. 정확히는 O(n*n*2^n)이 된다.

왜냐하면, 어떤 정수를 이진수로 출력하는데, n번의 계산이 필요함을 내가 관과했다.

 

이때, 멘붕이 왔다.

당연히 맞는 풀이라고 생각을 하고, 어딘가 맹점을 고쳐왔는데 근본이 틀린걸 알아버린 것이다.

 

하지만 상위의 팀들이 점점 F를 풀고 있었고...

다시 처음으로 돌아갔다.

그리고 이런 생각을 더해봤다.

 

출력은 잘되니까, 위에서 추측했던 Ad-hoc한 성질은 들어맞는 것 같다.

즉 어떤 경로로 가든 답은 존재한다.(적절히 뒤집기만 하면)

또, 이진수 표현에 n번 출력이 필요하고 2^n개가 필요하니까

O(1)에 다음 값을 찾아야하는 그리디하면서도 수학적인 루틴을 찾는 문제구나.

 

근데, 힘들었는지 몰라도  O(1)방법이 안 떠올랐다.

 likelon과 jkroll87은 C풀이가 떠올라서 풀러갔다.

 

C. 반짝반짝(199min+1try)

기댓값 dp다! 풀이는 모른다. dp라는것만 어깨너머로 들었다. 무한의 F구현중!

 

F. 성싶당(250+4try)

대전인인데 못풀뻔

Gray code를 생각해냈다. 찾아낸게 아니라 생각해냈다. 이렇게 가면 되겠지라고 루틴을 결국 떠올렸다.

아 well known 이었구나! ㅜㅜ 어쨌든 풀어냈다. likelon이 떠올리고, 내가 지옥의 비트마스킹 구현을 조졌다.

풀리는데 내 힘도 풀리더라.

 

j번 50분동안 풀었다.

근데 놀랍게도 거의 풀었다!

비슷한 코포 문제가 최근에 나온거 같아서 그게 떠올라서 투포인터가 떠올랐고.

codeforces.com/contest/1486/problem/D (이 문제다)

 

최대 최소 관리에 세그를 써야지! 하고

투포인터 +세그 지옥의 구현을 내가 했다! ㅎㅎ

5분남기고 1try후 장렬히 전사..

 

kmp할때마다 배열길이 2배늘리는 그 테크닉.

그 테크닉 써야지 라고 우리끼리 말 해놓고 안늘리고 구현했다!

나중에 보니 구현해야 했더라.

 

F에서 안말렸다면, 안말렸다면... J무조건 풀었을거 같다.

 

재밌었다.

아쉬운건 뒤로하고 ps는 그냥 재밌다. 

이 감정을 계속해서 간직하고 싶다.