오늘의 PS (1) - 220327

앞으로 어떤 방식으로던 하루에 문제를 많이 푼 날에는 이렇게 정리글을 작성하려 한다. 사실 그냥 여러개의 CP 글을 따로 쓰기 귀찮아서 하나에 합치는 것 같기도 하다. 오늘은 백준 나코더 입부테스트 Open이랑 ABC를 쳤다.

 

2022 IamCoder Qualification Test Open 

고인물 분들이 그렇게 많이 참여한거 같지는 않다.

A. 카드 색칠 (00:20, 3 try)

적당한 난이도의 Constructive 문제다. 연속된 0의 구간을 잘 칠해주면 되는데, 난 잘 생각이 안나서 좀 더럽게 풀었다.

 

B. 개표 (00:31, 2 try)

조건은 간단한 수식으로 나타낼 수 있다. 그 과정에서 나는 각 후보의 득표수를 multiset으로 관리했는데, 어차피 받는 표가 양수기 때문에 그냥 변수 하나로 관리하면 된다고 한다.

 

C. Split the SSHS (01:19, 4 try)

B번과 C번 사이에 할일이 있어서 15분 정도를 비웠다. 깔끔하고 좋은, 앳코더에서 볼 수 있을 것 같이 생긴 문제다. 각 정점에 연결된 간선의 색을 잘 관리해주면 되는데, multiset으로 냈더니 TLE가 나서 map으로 바꿨더니 맞았다.

 

D. 센터가 돋보여야 해 (01:41, 3 try)

이제는 웰노운이 되어가는 금광 세그 응용문제다. 나는 각 노드마다 \(A_{b}-A_{a}\)의 최댓값, \(A_{b}-A_{c}\)의 최댓값, \(A_{i}\)의 최댓값과 최솟값, 마지막으로 \(A_{b}-A_{a}-A_{c}\)의 최댓값을 관리해주었다. 전이 식을 찾는 것은 아마 어렵지 않게 할 수 있을 것이다.

 

E. 용암 점프 (02:27, 5 try)

솔직히 아직도 잘 모르겠는 문제라 후기를 쓰는게 맞나 싶긴 하다. 문제를 보고 가장 먼저 캐치해야 하는 것은 \(N>22\)라면 무조건 정답이 NO라는 점이다. 이는 정점간 거리의 최대가 \(2 * 10^6\)으로 제한되어있기 때문이다. \(N\)이 충분히 작다는 것을 알았다면, \(N 2^N\) 풀이를 작성하고 싶은 것이 인간이지만 그럴 수 없다. 문제가 쿼리 형태이기 때문이다. \(N\)이 20정도인 케이스를 \(T=50000\)번 정도 처리해야 하니 \(2^N\)으로는 택도 없다. 따라서 정해는 \(400T\)정도에 돌아가는 DP인거로 보이는데.. 내 풀이는 이와는 조금 다르다. 우선, \(20!\)짜리 백트래킹을 가지치기로 조금 최적화한 코드를 내봤다. 그랬더니 마지막 섭태를 제외한 67점이 나오더라. 그래서 조금 더 가지치기를 해봤다. 여러 번 시도한 결과 100점에 도달할 수 있었는데, 핵심적인 역할을 하는 코드는 이것이다.

if( \(x*2^{n-d-1}>ar[n]-ar[1]\) ) return; 

즉, 이 상태로 계속 갔을 때 마지막 길이가 정점간 길이의 최댓값을 넘어서면 가망이 없다고 판단하는 것이다. 이 코드가 왜 잘 돌아가는지 구체적으로는 잘 모르겠지만, 내가 대강 생각해 본 바로는 다음과 같다.

1) 정점들이 모여있는 경우 (정점간 거리가 작은 경우)

이 경우 위 코드는 큰 효용성을 가지지 않지만, 1->2->4->8.. 로 증가하는 과정에서 빠르게 가지치기가 된다.

2) 정점들이 흩어져있는 경우 (정점간 거리가 큰 경우)

이 경우 탐색 중간에 큰 거리의 간선을 택할 확률이 높고, 위 코드가 이와 같은 경우를 빠르게 걸러준다.

일단 AC를 받긴 했는데, 나중에 데추주가 될지는 잘 모르겠다. (+데추주가 되어 TLE를 받았다. 정해에 쓰이는 성질 한 가지를 가져와서 추가 커팅을 진행해 다시 맞았다.) 대충 보니까 나머지는 다 정해와 비슷한 방법으로 풀었더라.

여기까지 풀고 1등 그룹이 500점이길래 F를 잠깐 봤는데 뭔소린지 잘 모르겠어서 그냥 500점으로 만족했다.

Atcoder Beginner Contest 245 

블루에 갔다.

A. Good Morning (00:01, +) *25

단순 시간 비교 문제이다. 지문이 좀 어렵게 써져있긴 했다.

 

B. Mex (00:02, +) *40

단순 Mex 연산 구현 문제이다. 제한이 널널해 대충 짜도 됐다.

 

C. Choose Element (00:04, +) *403

대충 2N짜리 bool형 DP 배열로 구현하면 된다.

 

D. Polynomial Division (00:11, +) *815

뭔가 FFT스러운 식이 적혀 있는데, 제한이 매우 널널해 그냥 하라는대로 구현하면 된다. 이게 무슨 생수학이라고 하시는 분들이 있던데 뭔가 싶었다.

 

F. Endless walk (00:40, +3) *1451

E를 좀 잡다가 넘어왔는데, 그냥 딱봐도 SCC길래 바로 긁어왔다. 근데 SCC를 오랜만에 볼 뿐더러 바꿔줘야 할 부분이 좀 있어서 구현에 시간이 좀 걸렸다. 어떻게 AC를 받았지만, 정해는 SCC고 뭐고 없더라. 뭔가 위상정렬스러운 BFS 코드가 있던데, 완벽히 이해는 못했다... 조만간 SCC에 대해 확실히 이해하고 넘어가야 할 것 같다.

 

E. Wrapping Chocolate (01:04, 1 try) *1571

내가 못하는 유형의 그리디다. 대충 뒤에서 보면서 최적인거부터 써주면 되겠다 싶었는데 어떻게 구현할지 잘 모르겠어서 F를 먼저 풀었다. 생각해보니까 너비에 대한 기준은 투포인터처럼 그때그때 만족시키는 박스만 뽑아오면 될 것 같았고, 너비를 만족시켰으면 그것들 중에 가장 높이가 작은거를 사용하면 되므로 대충 pair를 뒤집어서 set에 넣어주면 되었다. 

 

G. Foreign Friends (X) *2270

멀티소스 다익스트라라는건 보고 바로 알았는데, 그 이상으로 발전시키지 못했다. 풀이를 보니 간선에 대한 거리를 구할 때 이 간선이 어디서부터 왔는지를 같이 저장해주면 된다고 한다. 좀 신기했다.

 

내일(사실상 오늘)은 숭고한 오픈콘이랑 코포가 있다. 체감상 그냥 PS보다는 대회 참여가 더 부담스럽고 체력 소모도 빠른거 같다. 내일 코포 세터도 블루던데 이러다 코포에서 망하는건 아닌지..좀 걱정된다. 여담으로 동아리 부원분들이 코포랑 앳코더에 나름 관심을 가져주는 것 같아서 기분이 좋았다.