leo020630의 블로그

2일차 랜덤 디펜스이다. 2038 - 골롱 수열 지문이 이해가 되지 않아 약간 헤멨다. 수열의 특징을 파악한 후 최댓값이 크지 않을 것이라고 추측하면 맞을 수 있다. 20930 - 우주 정거장 KOI 개구리 점프의 2차원 버전이다. 그 문제에서 하는 것을 2번 해주면 된다. 13174 - 괄호 23799 - 리브 매칭 열심히 생각하다 집중도 잘 안 되고 문제도 어려워서 포기했다. 20188 - 등산 마니아 문제에서 요구하는 것을 잘 나누어 수식으로 표현하면 DFS 한 번으로 정답을 구할 수 있다. 분명 G2~D4 범위에서 돌렸는데, 어제 오늘 10문제 중 P4~P1이 단 하나도 나오지 않아 연습이 잘 되지 않았다. 내일부터는 범위를 P4~D5로 바꿀 예정이다.

종강을 했다. 시험기간에는 문제가 그렇게 풀고 싶었는데, 종강하자마자 의욕이 확 식길래 랜덤 디펜스를 시작하기로 했다. 범위는 G2~D4이며, 하루에 5문제씩 뽑아서 진행할 예정이다. https://www.acmicpc.net/group/14908에서 진행 중이니 제가 뭘 푸는지 구경하고 싶거나 같이 문제를 풀고 싶으신 분들은 언제든 환영입니다ㅎㅎ 오늘은 첫날이라 시간을 기록하지 않았는데, 다음부터는 시간도 잴 예정이다. 15678 - 연세워터파크 웰노운이라 짜서 맞았다. 최근 \(k\)개 항의 최대 또는 최소를 관리해야 하는 DP는 세그 또는 PQ 또는 덱을 사용해서 해결할 수 있음이 널리 알려져 있다. 2136 - 개미 이것도 웰노운이라 신나게 짜긴 했는데, 생각해보니 번호를 구하는 방법을 몰라서 시..

6월 5일에 solved.ac 시즌이 갱신된다는 공지가 있었다. 이를 확인했을 때 내 티어가 D4였는데, 4는 예로부터 불길한 숫자였기 때문에 D3으로 올리려고 문제를 좀 풀었다. P2~D3 범위에서 골랐는데, 랜덤으로 뽑은 것도 있고 풀이를 대충 알고 있어서 짠 것도 있고 그냥 재밌어보여서 푼 것들도 있다. 일당 하나씩은 해당 범위의 문제들을 풀었기 때문에 날짜별로 정리해보려고 한다. 5/16 - 15879 Edge Coloring 5/13 팀 연습에서 Cycle Basis가 들어가는 문제를 풀었는데, 이 문제도 비슷한 원리를 이용하는 문제라는 것이 생각나서 풀었다. 풀이는 Cycle Basis를 안다면 쉽게 찾을 수 있는 것 같다. 5/17 - 1739 도로 정비하기 랜덤으로 걸린 문제이다. 각 도로..

ABC와 코포 Div. 1이 있어서 둘다 쳤다. AtCoder Beginner Contest 250 A. Adjacent Squares (0:01, +) *25 if문을 4개 써주면 된다. B. Enlarged Checker Board (0:04, +) *109 그냥 별 찍기다. C. Adjacent Swaps (0:07, +) *517 값을 담은 배열과 역추적 배열을 만들어서 잘 바꿔주면 된다. D. 250-like number (0:16, +) *797 우선 에라토스테네스의 체로 \(10^6\) 이하의 소수를 모두 구해준 후, 각 소수에 대해 이분탐색으로 만족하는 더 작은 소수의 개수를 구해주면 된다. E. Prefix Equality (0:23, +) *1421 \(C_i\)를 \(A_i\)가 \(..

카테고리 제목이 '오늘의 PS'인데 제목에는 당당히 7일치를 박아놓았다. 하지만 저 기간 중 문제를 풀었다고 할 날은 5월 1일과 7일 이틀뿐이었기 때문에, 한 글에 정리해보려 한다. 5월 1일 - 2022 DGIST 현풍전산배 알고리즘 대회 Open Contest 타임라인은 정확히 기억이 나지 않아 문제별 후기만 간단히 정리하도록 하겠다. A. 에어컨 전형적인 구현 문제이다. A번 치고는 까다로운 구석이 여럿 있었던 것 같다. 출력 형식 때문에 printf를 오랜만에 사용해 볼 수 있었다. B. 비즈마켓 코포 Div.2에서 볼 수 있을 것 같이 생겼다. 두 배열을 하나는 오름차순, 하나는 내림차순으로 정렬한 뒤 잘 구해주면 됐던 것 같다. C. D. 사각형 게임 (Small, Large) 오픈콘이라 두..

앳코더와 코드포스 글로벌 라운드가 있었다. AtCoder Beginner Contest 249 A. Jogging (0:05, +) *103 지문이 이상하게 쓰여 있어서 좀 헤멨다. 문제 자체도 평소 ABC A보다 어려웠다. B. Perfect String (0:07, +) *47 하라는대로 하면 된다. C. Just K (0:11, +) *528 이것도 지문이 조금 불친절하긴 했는데, 하라는 대로 완전탐색을 돌려주면 맞는다. D. Index Trio (0:30, +2) *983 인덱스가 같을 수도 있어서 식을 좀 생각해서 써주어야 한다. 예제가 앳코더답지 않게 불친절해서 많이들 틀리는 것으로 보였다. E. RLE (1:00, +) *1970 \(DP[i][j]\)를 i번째 글자까지 쓰고, 압축 길이가 ..

카테고리 제목이 PS인데 너무 CP만 다룬 것 같아서 최근에 푼 백준 문제들 중 인상깊었던 것들을 정리해서 쓰려고 한다. 세미나를 준비하면서 백준에 있는 행렬 DP 문제는 거의 몽땅 푼 것 같다.. 이번에 정리할 문제들도 모두 여기에 속하는 것들이다. 2086 - 피보나치 수의 합, 11440 - 피보나치 수의 제곱의 합, 11778 - 피보나치 수와 최대공약수 모종의 정리들을 알거나 규칙을 찾으면 평범한 피보나치 수 문제로 환원할 수 있다. 2086은 규칙을 찾아서 풀었고, 뒤의 두 개는 적당히 검색해서 풀었다. 17401 - 일하는 세포 보자마자 풀이는 보이는데, 구현이 좀 귀찮은 문제이다. 신경써야 할 점은 1. 같은 행렬을 거듭제곱하는 문제들과는 다르게 교환법칙이 통하지 않는다. 2. 주어진 행렬..

이번 주말은 유독 칠 대회가 많았다. 총 앳코더 2개, 코포 2개, 구글 코드잼 1A 라운드가 있었는데, 코드잼은 자느라 못쳤고, 앳코더는 (실력적으로) 못 쳤기 때문에 특별히 잘 친 2개의 코드포스 라운드를 정리해보도록 하겠다. Codeforces Round #781 (Div. 2) A. GCD vs LCM (0:00, +) 보자마자 답이 보여서 짜서 냈다. 덕분에 코포하면서 처음으로 500점을 먹을 수 있었다. ㅎㅎ B. Array Cloning Technique (0:05, +) 가장 많이 등장하는 수의 개수를 센 후, 적당히 2배씩 하면서 횟수를 구해주면 된다. C. Tree Infection (0:33, +3) 킹받는 그리디 문제이다. 우선 노드를 Sibling 단위로 묶으면 트리와 관계 없는 ..

앞으로 어떤 방식으로던 하루에 문제를 많이 푼 날에는 이렇게 정리글을 작성하려 한다. 사실 그냥 여러개의 CP 글을 따로 쓰기 귀찮아서 하나에 합치는 것 같기도 하다. 오늘은 백준 나코더 입부테스트 Open이랑 ABC를 쳤다. 2022 IamCoder Qualification Test Open A. 카드 색칠 (00:20, 3 try) 적당한 난이도의 Constructive 문제다. 연속된 0의 구간을 잘 칠해주면 되는데, 난 잘 생각이 안나서 좀 더럽게 풀었다. B. 개표 (00:31, 2 try) 조건은 간단한 수식으로 나타낼 수 있다. 그 과정에서 나는 각 후보의 득표수를 multiset으로 관리했는데, 어차피 받는 표가 양수기 때문에 그냥 변수 하나로 관리하면 된다고 한다. C. Split the..