PS/오늘의 PS 27

오늘의 PS (26) - 231226-240101

써야지 써야지 하다가 밀려서 그냥 1주일동안 한 것을 정리한다. USACO 2023 December Contest (12/26~29) Bronze 1. Candy Cane Feast *G3 쭉 순회하며 사탕을 먹이는 정상적인 \(O(N)\) 과정을 거치면 가장 앞 사탕은 적어도 길이가 2배가 됨을 알 수 있다. 따라서 이러한 과정은 최대 \(logX\)번 일어나고, 그 이상부터는 반드시 첫 사탕 선에서 막힌다. 2. Cowntact Tracing 2 *G3 우선 시키는 대로 1 덩어리들로 묶어준 후, 가장 작은 덩어리에 맞춰주자. 이 때 양 쪽 끝에 붙은 덩어리에 유의해야 한다. 3. Farmer John Actually Farms *G2 순서를 strict하게 잘 정해주어야 하므로 정렬된 결과에서 인접..

PS/오늘의 PS 2024.01.03

오늘의 PS (26) - 231225

학기가 끝났다. 2학기는 ICPC 말고는 별로 기억에 남는 게 없어서 따로 후기를 쓰지는 않을 것 같다. (레이트로 냈지만) 마지막 과제 듀가 24일이여서 오늘부터 본격적으로 PS 재활에 들어갔다. 12월 25일이 무슨 날이라고 하던데 잘 모르겠다. 먼저 최근에 안친 오픈컨 문제들 중 재밌어 보이는 몇 개를 골라 풀었다. 31003 - 언젠가 정렬이 될 수 있으면 좋겠네. (2023년 12월 월향 E) *G1 DAG 만들고 위상정렬 갈겼다. 정해는 아닌 것 같다. 31006 - 역삼각형 (2023년 12월 월향 J) *P3 세그 스위핑 갈겼다. 6개 만들어서 좀 귀찮았지만 펜윅이라 다행이었다. 30998 - 최고의 크리스마스트리 (2023 미적확통컵 PE) *P3 리루팅 DP 갈겼다. 식 정리가 좀 귀찮..

PS/오늘의 PS 2023.12.26

오늘의 PS (25) - 230719 (제7회 천하제일 코딩대회 Open Contest)

적당한 시간대에 오픈컨이 있길래 가서 쳤다. 처음엔 사람들 닉네임이 무서워서 쫄았는데, 문제들이 어렵지 않아서 결과가 나름 괜찮게 나왔다. 따라서 후기를 써 보려 한다. 카테고리는 적절한 곳이 없어서 거의 1년 만에 오늘의 PS를 부활시켰다. 다음 글이 언제가 될진 잘 모르겠다.. 셋: https://www.acmicpc.net/category/detail/3626 A. 10! (0:01, +) *B4 구현해주면 된다. 0분대 솔브도 가능했을 것 같은데 똑똑한 방법을 찾지 못하고 계산기로 10!/6을 계산하느라 조금 늦었다. B. 고양이 카페 (0:06, +1) *S3 비슷한 문제를 굉장히 많이 봐서 바로 짰다. 제일 작은 원소부터 가능한 원소와 매칭시켜 주면 된다. upper를 lower로 잘못 써서 ..

PS/오늘의 PS 2023.07.20

오늘의 PS (24) - 221015

하루에 대회 3개를 쳤기 때문에 묶어서 정리하려고 한다. BOJ - 초콜릿컵 A. 초콜릿 피라미드 (0:12, +) 차분히 식정리를 해주면 된다. B. 초콜릿과 나이트 게임 (0:32, +) \(XY=0\)인 경우, \(X=Y\)인 경우, 그 외의 경우로 나뉜다. 앞 두 케이스는 7번, 뒤 케이스는 15번만에 게임을 끝낼 수 있다. 구현이 좀 귀찮은데, 난 그냥 cout을 29개 썼다. C. 예쁜 초콜릿과 숫자놀이 (1:51, +3) 제한이 애매하게 커서 완탐도 안될 것 같고(사실 된다), \(O(N^2 MOD)\) DP는 생각이 나지 않아 그냥 \(O(N^3 MOD)\) DP에 비트셋을 박았다. 왠지는 모르겠지만 실행시간 1등이다. 비트셋 최고 D. 초콜릿 나눠 팔기 (2:09, +) 케이스를 나누면 ..

PS/오늘의 PS 2022.10.19

오늘의 PS (23) - 220822~220905

지난 포스트에서 글을 자주 쓰겠다고 했는데, 바쁘다고 미루다 보니 또 2주동안 글을 쓰지 않았다. 그동안 있던 SCPC 본선과 SUAPC는 별도의 글을 올릴 예정이다. 2주동안 있었던 코포랑 앳코더는 다 언레라 진지하게 치지 않아서 여기 올리기엔 좀 그런 것 같아 백준에서 푼 문제들만 정리해보려 한다. 2021 홍익대학교 프로그래밍 경진대회 23320 홍익 절대평가 그냥 구현. 문제가 친절해서 실수도 필요 없고 정렬도 필요 없다. 23321 홍익 댄스파티 그냥 구현. 귀엽긴 한데 무슨 말인지 알아보기가 좀 힘들었다. 23322 초콜릿 뺏어 먹기 코포식 그리디 문제이다. 풀이는 자명하게 찾을 수 있다. 23323 황소 다마고치 역시 코포식 그리디 문제이다. 어느 경우가 최적인지는 잘 생각해보면 알 수 있고..

PS/오늘의 PS 2022.09.06

오늘의 PS (22) - 220815~21

블로그를 너무 방치해 둔 것 같아 오늘의 PS 글을 하루에 하나는 아니더라도, 일주일에 하나 정도는 써보려고 한다. UCPC가 끝난 이후부터는 개인 PS 공부를 정말 거의 하지 않아서 쓸 내용이 없었지만, 그래도 이번주부터는 뭐라도 해보려고 한다. SCPC 대비도 해야 하고.. 이번주에는 백준에서 셋 2개정도를 풀고, 코포 1번과 앳코더 2번을 쳤다. 코포는 2번이 더 있었으나 노느라 치지 못했고, 앳코더는 두 번 모두 쳤다. BOJ 화요일에는 동아리 연습용 셋으로 던져 놓은 2021 IUPC 를 풀었다. 마지막 문제 빼고는 모두 화요일에 풀었고, 마지막 문제는 귀찮아서 미루다가 오늘 풀었다. 23080 스키테일 암호 브론즈 문제이다. 잘 구현해주면 된다. 23081 오델로 실버 구현 문제인데, 제한이 ..

PS/오늘의 PS 2022.08.22

오늘의 PS (20) - 220708

13:00~15:30 모비스 본선 16:30~18:30? 천코대 오픈콘 23:35~01:35 에듀코포 를 쳤다. 모비스 대회에 대한 후기는 생략하도록 하겠다. 제6회 천하제일 코딩대회 본선 Open Contest 2시간 늦게 참여하기도 했고 중간에 자리를 몇 번 비워서 진지한 마음으로 치지는 않았다. 아마 종료때까지라도 했으면 F는 풀었을 것 같다. A. Gravity Hackenbush 지문 낚시 문제이다. 각 플레이어가 초록색 간선을 최대한 많이 쓰는 것이 최적이므로 이를 토대로 비교해주면 된다. C. Merge the Tree and Sequence Split the SSHS 문제와 세팅이 비슷하다. 간선을 묶는 것은 그때와 같이 하면 되고, 남은 부분은 간선을 묶는 것에 비하면 크게 어렵지 않다...

PS/오늘의 PS 2022.07.09

오늘의 PS (19) - 220630

오늘은 (핸들에서 알 수 있듯이) 생일이었다. 생일이라고 뭔가 거창한 걸 하진 않았고, 그냥 오후에 잠깐 외출 후 돌아와서 지인들과 셋 하나를 돌았다. 셋은 다음과 같다: https://www.acmicpc.net/category/detail/2355 2020 Sogang Programming Contest (Master) www.acmicpc.net 순서를 섞었기 때문에 실제 대회 번호와는 차이가 있다. 우선은 내가 푼 순서대로 정리할 예정이다. 20300 - 서강근육맨 (실제 대회 B, 위 스코어보드에서는 C) A, B가 바로 풀 문제는 아닌 것 같아 C를 잡았다. 짝수일 때는 정렬해준 후 맨 앞과 맨 뒤를 차례대로 매칭해주면 되는데, 홀수일 때는 잘 생각이 나지 않는다. 친절하게도, 제곱 풀이가 가..

PS/오늘의 PS 2022.07.01

오늘의 PS (18) - 220629

어제는 노느라 문제를 풀지 못했다. 오늘은 플레 랜덤 문제를 몇 개 풀었다. 20670 - 미스테리 싸인 볼록다각형 이분탐색 문제를 연습하고 싶어 풀었다. 다각형을 위 아래로 나누는 방법과 각도로 나누는 방법 두 가지가 있는 것 같다. 이거 말고 접선 긋는 문제도 있는데, 한번 연습해 볼 계획이다. 18373 - N!!!...! mod P K가 크면 답이 0이 될 것이라고 추측할 수 있다. 그러면 경우의 수가 몇개 남지 않는데, 이를 열심히 짜주면 시간 초과를 받는다. (12!~=5e8)!을 구하는 게 1초 안에 돌아가지 않는 것 같다. 도저히 모르겠어서 열심히 풀이를 찾았는데, FFT를 쓰는 어려운 풀이와 윌슨 정리라는 걸 쓰는 풀이가 있었다. 티어를 봐선 FFT는 절대 아닌 것 같아서 윌슨 정리를 공..

PS/오늘의 PS 2022.06.30