본문 바로가기

일기

(50)
BOJ 25015번 - 아이싱 25015번: 아이싱 C++17, C++14, C++20, C++14 (Clang), C++17 (Clang), C++20 (Clang) www.acmicpc.net notorious coincidence 문제집에서 찾은 문제이다. 19862번과 동일한 문제인데 아쉽게도 19862번은 작성 일자 기준으로 레이팅을 주지 않는다. 하지만 루비 문제 치고 풀이가 간결하다기에 아래 블로그에서 풀이를 공부하고 풀어 보았다. https://dsstar.tistory.com/49 https://justicehui.github.io/ps/2020/09/16/BOJ19862/ 그런데 코드가 전혀 이해되지 않았다. 심지어 두 번째 블로그는 코드에 사소한 오류가 있는데 복붙 방지용인 듯 하다. 몇 시간 동안 생각해보아도 이..
BOJ 2156번 - 포도주 시식 2156번: 포도주 시식 효주는 포도주 시식회에 갔다. 그 곳에 갔더니, 테이블 위에 다양한 포도주가 들어있는 포도주 잔이 일렬로 놓여 있었다. 효주는 포도주 시식을 하려고 하는데, 여기에는 다음과 같은 두 가지 규 www.acmicpc.net 정말 기초적인 dp 문제인데 반례를 한참 동안 못 찾아서 반성할 겸 포스팅한다. 다음과 같은 배열 A를 정의하자. A[i] = i번째 포도주의 양 다음과 같이 점화식을 세우면 WA를 받는다. dp[i] = max(dp[i - 2], dp[i - 3] + A[i - 1]) + A[i]; 사실 이 점화식은 2579번과 동일한 점화식이다. 2579번에서는 i번째 계단을 밟기 전에 (i - 1)번째 또는 (i - 2)번째 계단을 반드시 밟아야 한다는 조건이 있다. 하지만..
BOJ 26101번 - 링크와 스타트 2 26101번: 링크와 스타트 2 첫째 줄에 N(4 ≤ N ≤ 400)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100 www.acmicpc.net 귀찮기 때문에 구체적인 풀이는 작성하지 않을 것이고 힌트만 몇 개 남긴다. HINT 1 더보기 knapsack dp와 bitset 태그가 붙어 있음에 주목하자. HINT 2 더보기 먼저 26607번을 풀어 보자. 잘 모르겠다면 에디토리얼을 참고하자. HINT 3 더보기 26607번을 bitset으로 풀어 보자. HINT 4 더보기 그 다음에는 21844번을 풀어 보자. 잘 모르겠다면 에디토리얼을 참고하자. HINT..
2020 ACM-ICPC Seoul Regional Asia Regional - Seoul 2020 www.acmicpc.net 서론 실제로 참가하였던 대회이기도 하고 풀어볼 만한 문제도 많아 보여서 최대한 업솔빙하였다. B - Commemorative Dice 단순 구현 C - Dessert Café 임의의 두 아파트 단지를 잇는 경로 사이에 존재하는 candidate site는 good place이다. 임의의 아파트 단지에서 dfs를 돌리면 모든 good place를 찾을 수 있다. 간선의 가중치는 필요하지 않다. E - Imprecise Computer 각 round의 결과에 대하여 D[i]의 값은 다음과 같이 결정된다. if (i - 1) vs i의 결과가 동일 if i vs (i + 1)의 결과가 동일 D[i] = 0 else D[i] = 1 e..
2023년 1월 13일 일기 겨울 숲의 초대 이후로 거의 한 달 동안 대회 참가와 업솔빙만 반복하면서 지냈다. 이제 모든 업솔빙이 끝나서 조금 여유가 생겼는데 그 대신 글이 많이 밀렸다. 작성 예정인 글 목록은 다음과 같다. Good Bye, BOJ 2022! (G번 H번) 나는코더다 2022 송년대회 Open Contest Hello 2023 제1회 보라매컵 예선 Open Contest 2020 ACM-ICPC Seoul Regional 보드게임컵 (참가 예정) Hello, BOJ 2023! (참가 예정) 막상 적어보니 많지는 않다. 아무튼 연말에 어려운 대회가 쏟아져 나와서 업솔빙이 정말 오래 걸렸다. 특히 나는코더다 업솔빙이 힘들었는데 덕분에 cht와 dnc opt는 잘 배웠다. 내일은 보드게임컵에 참가하고 서울로 일찍 올라간..
BOJ 19089번 - 파일 합치기 4 19089번: 파일 합치기 4 프로그램은 표준 입력에서 입력 데이터를 받는다. 프로그램의 입력은 T개의 테스트 데이터로 이루어져 있는데, T는 입력의 맨 첫 줄에 주어진다.각 테스트 데이터는 두 개의 행으로 주어지는데, www.acmicpc.net Garsia-Wachs algorithm 또는 Hu-Tucker algorithm으로 풀이할 수 있다. 나는 Garsia-Wachs algorithm으로 풀이하였다. 원본 논문보다는 이 논문을 보는 것을 권장한다. 알고리즘 자체는 간단한데 다음 두 단계를 N - 1번 반복하면 된다. (i) Locate the rightmost R.M. pair of entries. Let that be p_i-1, p_i. (ii) Next locate the first en..
Good Bye, BOJ 2021! Good Bye, BOJ 2021! www.acmicpc.net 서론 2022년 대회 예비소집 문제로 출제되었다. A - 2021은 무엇이 특별할까? 전처리 B - 예쁜 케이크 a * b = N and (a + b) % 3 = 0인 a와 b가 존재하는지 확인해야 한다. case work를 해보자. (i) a % 3 == 0 and b % 3 == 0 a와 b 모두 3의 배수이므로 N % 9 == 0이어야 한다. (ii) a % 3 == 1 and b % 3 == 2 a와 b는 각각 (3k_a + 1)과 (3k_b + 2)로 표현할 수 있다. 이때 a와 b의 곱은 (3 * (3 * k_a * k_b + 2 * k_a + k_b) + 2)이다. 따라서 N % 3 == 2이어야 한다. (iii) a % 3 =..
제1회 곰곰컵 제1회 곰곰컵 www.acmicpc.net 서론 그냥 어쩌다 보니 풀었다. A - 치킨댄스를 추는 곰곰이를 본 임스 단순 수학 B - 인사성 밝은 곰곰이 set C - 곰곰이의 식단 관리 수학 D - 결전의 금요일 dp E - Yes or yes dfs F - 숲속에서 새 구경하기 처음에는 Segment Tree로 풀었는데 더 쉬운 풀이가 존재한다. 답이 t라는 것은 새 3마리 중 적어도 1마리가 시점 t에 등장하였다는 것을 의미한다. 따라서 새 3마리에 대하여 lcm(Av, Bv, Cv) 미만의 시점 중 주기의 시작점만 고려하면 된다. bfs를 이용한 더 빠른 풀이가 존재하지만 설명은 생략한다. G - 합주단 곰곰 두 단원이 식사를 할 확률은 1 / K이다. 따라서 답은 N * (N - 1) / 2 /..