1월 29일 PS 일기

설날 오후에 집에서 셋 하나 돌았다.

Petro camp Summer 2023 Day 4 (https://qoj.ac/contest/1356)

나는 혼자서 돌았고, flappybird랑 ibm2006이 2인팀으로 같이 돌았다.

 

0:00

A번을 잡고 풀다가 I번 솔브가 몇개 나와서 I번 잡고 풀었다.

풀이

최대는 당연히 n이고, 최소는 가운데에 특수문자 박고 3칸씩 띄어서 특수문자 박는 것이다.

0:07에 AC를 받았다.

 

바로 A번을 보는데, 처음에 봤을 때 구상하던 풀이로 풀어서 0:15에 AC를 받았다.

 풀이

각 b에 대해서 b 왼쪽이면서 가장 가까운 p, 그 p 왼쪽이면서 가장 가까운 s를 찾는다.

같은 방법으로 오른쪽으로 s, u를 찾는다.

s, p, s, u와 b의 거리합의 최소를 구한다.

B번은 A번보다도 쉽게 풀렸다. 풀이 발상하고 구현까지 6분 걸려서 0:21에 AC를 받았다.

풀이

2023년 1월 1일이 일요일인 것에서 1970년 1월 1일이 목요일인걸 계산한다.

달력의 마지막 일의 인덱스를 구해서 그 인덱스 기반으로 각 년의 각 달마다 몇 줄이 필요한지 전처리한다.

0:21

K를 보다가 플로우로 풀릴까 하는 생각을 했었는데 n <= 50000이라 안 될것 같아서 던졌다.  (정풀은 플로우 + 발상 잘하기였다고 한다)

D랑 E는 구현 + 많조분인것 같아서 뒤로 미뤘고, J를 보니까 풀이 발상이 돼서 구현해서 맞았다.

풀이

임의의 두 plus끼리는 연결되어 있으므로 plus를 최대 2번 이용한다.

plus를 0번 이용하는 경우, 1번 이용하는 경우, 2번 이용하는 경우에 대해서 브루트포스로 최단거리를 구해준다.

경로 출력하는건 최단거리 구하는 과정에서 경로를 구해놓고 그걸 출력했다.

1:15

D번을 잡았다. 남은 문제중에 그나마 솔브수 많은게 D여서 이걸 먼저 밀고 다른걸 밀자는 마인드였다.

체스판 모양 격자를 45도 틀어서 깨진 체스판에 룩들을 배치하는 문제로 바꿔서 풀려고 했는데, n과 m의 대소관계랑 기우성에 따라 경우의 수가 크게 늘어났다. 심지어 n > 2m인 경우랑 아닌 경우랑도 해 구하는 방법이 달랐다.

1시간 정도 지나서야 괜찮은 발상을 하고 짜서 맞았다.

풀이

체스판을 흑/백으로 분리하고, n < m이 되도록 한다.

n이 홀수이면, 흑/백 각각에 대해서 1번째 열과 m번째 열에 모두 비숍을 넣고, 서로 공격하지 않는 선에서 가운데 행에 비숍을 최대한 많이 넣는다.

n이 짝수이면, 밝은 칸에 대해서만 구하고 선대칭한다. 밝은 칸에 대해서 구하는 아이디어는 위와 같고 구현이 살짝 다르다.

n > 2m인 경우에 풀이가 달라짐을 발상하고 어떻게 달라지는지까지 알아내야 정풀이 나와서 발상하는 데 시간이 많이 걸렸다.

2:27

그다음으로 솔브가 많은 G를 잡았다.

처음에 정점을 추가/제거하는 것을 tree 형태로 변형해서 푸는 것을 생각해 봤지만 반례들을 모두 커버하기가 힘들어서 버렸다.

30분 정도 걸려서 다음 발상을 했다.

i번 간선이 현재 3번 쿼리가 주어졌을 때 답의 후보군에 들면 b[i] = 1, 아니면 0이라고 하자.

초기에 b[i]는 모두 0이다.

i번 간선이 3번 쿼리에서 지워졌으면 c[i] = 0, 아니면 1이라고 하자.

초기에 c[i]는 모두 1이다.

3번 쿼리가 주어졌을 때, b & c = d라고 하고, d[i] = 1인 i가 존재하면 i를 출력하고 c[i] = 0으로 한다.

i번 정점에 대해서 j번 간선의 한 끝이 i번 정점이면 a[i][j] = 1, 아니면 0이라고 하자.

+ v , - v를 시행할 때에는 b = b ^ a[v]를 적용하면 된다.

 

이 발상의 유일한 문제점은 시복이 O(QM)이라는 건데, a, b, c, d가 모두 비트들만을 저장하므로 비트질로 뚫릴 것 같다는 생각이 들었다. 하지만 a 배열이 NM비트를 사용하므로 MLE가 나게 된다.

여기서 더 진전을 못해서 다음으로 솔브가 많은 L번을 잡았다.

바로 풀이가 나왔고, 타당한 것 같아서 짰더니 맞았다. 왜 G나 K보다 당시 솔브수가 적었는지 이해가 안 갔다.

풀이

카드를 뒤집는 단계에서는 A 중 하나를 뒤집고, B 중 하나를 뒤집고, ..., Y 중 하나를 뒤집는다.

뒤집힌 카드들이 25개 있는데 그 중 24개를 뒤집으면 나머지 하나는 알 수 있다.

이제 그 카드들의 위치를 저장하고 안 뒤집힌 카드들을 하나씩 오픈하면서 매칭을 시켜준다.

이렇게 하면 12번의 miss로 매칭이 가능함이 보장되는 것 같다. 문제에서 13.5번 이하로 풀라고 했는데, 내 풀이가 의도된 풀이고 제한은 블러핑인걸까? 잘 모르겠다

3:24

L을 풀고 다시 G로 돌아와서, 내 발상이 안 먹히는 경우를 해결했다. 그대로 짰더니 (3틀 이후) AC를 받았다.

풀이

위 발상의 연장선상이다.

a 배열의 대부분은 값이 0이다.

이제 a[i]를 64비트씩 끊어서 (실제 구현에선 60비트씩 끊었다.) long long int 1600개짜리 배열로 바꾼다. 그 다음에 a[i][j] != 0인 j와 a[i][j]의 값들만 vector에 저장한다.  pair<int,long long> 최대 2M개를 저장하므로 터지지 않는다. 저장하는 과정에서는 map을 사용해서 마찬가지로 2M개의 long long만 저장하면 되도록 했다.

이제 위 발상에서 했던 걸 해주면 O(QM/64)로 문제가 풀린다.

원래 64비트씩 끊었는데 WA를 받아서 안전하게 60비트씩 끊었는데, 알고보니 다른 곳에서 틀렸어서 그거 고치니까 맞았다.

3:59

남은 문제중에 솔브수가 그나마 많은게 E, K, M이었다.

K는 발상을 못하겠어서 던졌고, M은 문자열인데 KMP느낌이 나서 던졌다.

E는 그리디하게 남은 정답 후보중에 아무거나 출력하는 걸 6번 반복하는 방식으로 시도해 봤는데, 처음 시도에서 WA를 받아서 포기했다. (나중에 풀이 들어보니까 디시전 트리를 박으면 풀린다고 한다.) 이제 더 이상 풀 문제가 없고 시간도 25분밖에 안 남아서 GG치고 나왔다.

5:00

끝나고 flappybird + ibm2006 팀 (BIG SHOT)과 풀이를 공유했다.

나는 E K를 못풀었지만 G L을 풀었고, 빅샷팀은 G L을 못풀었지만 E K를 풀어서 합집합하면 9솔이었다. TMI로 같은 7솔에 페널티가 동타였다.

E G K L 풀이 공유하고 해산했다. GG

일단 셋을 잘못 고른 것 같았다. 내가 푼 모든 문제가 발상 난이도에 비해 상당한 구현량을 요구했다. 컨디션이 안좋거나 구현에서 한번 말리면 끝도 없이 말리기 쉬운데, 난 운이 좋았어서 괜찮게(7솔) 한 것 같다.

다만 K번에서 플로우인 것 같다는 생각은 했지만 시간복잡도가 안 맞아서 아예 던진게 좀 아쉽다. 물론 시간이 부족해서 짜지는 못했겠지만, 완전히 던지기 전에 모델링이라도 해봤으면 하는 생각이 든다. 실제 대회에서 내가 K같은 문제를 잡으면 모델링까지 해서 팀원한테 알려주고 팀웜이 또 고능한 발상을 해서 풀기를 바래야겠다.

다음에는 팀원 구해서 합을 맞춰보는 연습도 해야겠다.