2023 SCPC 예선

2023-08-03 11:11:06 +0000

2023 SCPC 예선을 쳤다.
1번은 간단한 문제라 바로 맞췄고, 2번은 고민 좀 하다가 왼쪽->오른쪽과 오른쪽->왼쪽을 나눠서 세주었다.
그다음에 4번을 잡았다. kmp를 써서 어떻게 하면 될 줄 알았는데, 어림도 없었고 제출 10번을 다 쓰고 만다.
그냥 3번을 잡았고, 1000이하일땐 시뮬레이션을 돌려서 직접 답을 구하고(40점), 그 이상이면 해싱을 통해 겹치는 부분을 구하여(100점) 부분점수를 긁었다.

총점 300점으로, 작년의 100점에 비하면 엄청난 발전이다.
일반적으로 이 점수면 1차예선은 그냥 통과인데 어째서인지 만점도 떨어지더라… 오류인가보다.

2023 APC Div.1

2023-05-27 14:04:54 +0000

오늘 APC출전해서 문제를 풀면서, 떠올렸거나 그렇지 못한 아이디어를 적는다.

먼저 Div.1 기준 D(오픈 F) 정말 재밌게(시간은 엄청 썼다) 푼 문제다. 난 직접 격자 사이즈를 늘려가면서 몇 개가 있어야 할 지 생각했는데, \(\left \lceil \frac{a*b+1}{2} \right \rceil\)를 보고 깨달었어야 했다… 절반 이상의 이름을 배치하려면 반드시 연결되는 경우가 생긴다. 짝수의 경우와 홀수의 경우를 나눠 규칙을 찾으면 된다.
1x2나 2x1의 규칙은 정말 빠르게 찾아냈는데 1x3, 3x1의 경우를 생각하는 데 시간을 잡아먹었다. 재밌는 아이디어 문제였다.

그리고 Div.1 기준 E(오픈 G) 2차원 DP인걸 알아냈고, [문제 인덱스][난이도 범위]로 두고 \(N^2K\)짜리 DP를 짰다.
엥? 왜 시간초과지? -> FASTIO, GCC Optimal, MOD연산 횟수 줄이기로 미친듯이 커팅했다. 97%까지 쭉 올라가다가 시간초과… 결국 못풀었고, 나중에 들어보니 \(N^2K\)가 뚫리는게 의도된 풀이가 아니여서 마지막에 \(N^2K\)를 막는 테스트케이스를 추가했다더라… DP가 또 날 미치게하는구나

그 외에도 다익스트라 후 DP, 트리DP 등 많은 DP문제가 있었고 더 많은 DP공부를 해야겠다고 생각했다. 끝.

알고리즘 첫글

2022-08-06 10:10:39 +0000

나는 그렇게 많이 아는것도 없지만, 혼자 공부한 내용을 적는 용도로 이 게시판을 팠다.
솔직히 글 그렇게 많이 안 쓸것 같다…