Problem Solving (59) 썸네일형 리스트형 (임시) 2020 ICPC Seoul Regional 후기 * 페이스북에 올린 것을 급하게 그대로 올립니다. 14일날 있었던 Seoul Regional과, 그리고 리저널을 치기 위해서 노력했던 시간들에 대해 짧은 후기글을 올립니다. (긴 후기는 나중에 블로그에 올라올 것 같습니다.) 두서가 좀 없어도 이해해 주세요. 저희 팀은 결성된 지 상당히 오래 된 팀입니다. 올해 1월에 만들어졌고, 그때부터 팀연습을 몇 번 했던 것 보면 태생이 빡겜을 하기 위해 만들어진 팀이었던 것 같습니다. 저 또한 재수하려고 마음을 먹었다가 이 팀 구성이면 Semi-World Final에는 무조건 진출하겠다고 생각이 들어서 재수를 포기하고 PS를 계속 했습니다. 결과적으로 좋은 성적을 냈으니 옳은 선택이었다고 생각합니다. 사실 저희 팀이 객관적으로 잘하는 팀이다 말하기는 아직도 힘들다.. Random Problem Solving 1 Intro 정말 PS를 하고 싶었기 때문에, 몇 문제를 풀었다. 잘 푼 문제도 있고 그렇지 못한 문제도 있지만, 어쨌던 간에 풀었던 문제들의 기록을 간단하게나마 남길까 한다. 20045 Trading System 먼저 다음과 같은 값을 찾는다. 구간합이 $x$ 이상인 구간의 개수가 $k$ 이상인 가장 큰 $x$ 이 값을 찾아야 하는 이유는, 이 값을 찾는다면 실제 수열은 $x+1$ 이상인 구간합을 모두 set을 이용해서 찾아 준 다음 나머지를 $x$로 채우는 방식으로 역추적해낼 수 있기 때문이다. 따라서 이 값을 찾는 것이 답을 구하는 것과 동치이고, 이 정도 문제를 해결할 수준이라면 이 과정은 매우 쉬우므로 설명은 생략할 것이다. 이 값은 $x$에 대한 Parametric Search로 찾아줄 수 있다.. [BOJ] 17524 Dryer 문제 링크 : www.acmicpc.net/problem/17524 문제 풀이 가장 먼저 해야 하는 관찰은 다음과 같다. $t_i$가 같은 옷이 2개 있다면 어차피 $w_i$가 큰 쪽이 더 오래 걸릴 것이기 때문에, 같이 넣고 말려도 무방하다. 따라서 의미 있는 옷은 각 $t_i$에 대해서 유일하므로, $1\le N\le61$과 사실상 같다. 그 다음으로 해야 하는 관찰들은 다음과 같다. 어떤 옷들의 집합을 같은 건조기에 넣고 돌린다면, 그 건조기의 온도는 반드시 옷 중 $t_i$의 최솟값과 같아야 한다. 이는 매우 자명하다. 어떤 건조기가 이미 $x$초 동안 돌아간다면, $x$초 이하를 소모하는 다른 옷을 끼워 넣어도 상관없다. $k=3$일때만 해결하면 그 아래는 쉽게 해결할 수 있으므로 이 경우에 대.. [SCPC] 2020 1차 예선 풀이 Intro대충 4시간 정도 때려 박아서 1~4번에서 만점을 받았고, 5번은 문제만 읽었습니다. 예전 SCPC 기출에 비해서는 확실히 난이도가 균일해진 것 같습니다(https://newdeal123.tistory.com/61 참조 요망). 제가 예상하는 Solved.ac 티어 난이도는 다음과 같습니다.다이어트 (Silver 3)카드 게임 (Platinum 3)사다리 게임 (Platinum 3)범위 안의 숫자 (Platinum 2)우범 지역 (Diamond 2~3?)1. 다이어트다음과 같이 생각해봅시다. 일단 자명히 두 식단에서 칼로리가 낮은 순으로 K개만 먹어야 한다는 것을 알 수 있습니다. 이때 식단 A의 가장 큰 칼로리를 가지는 식사는 B의 어떤 식사랑 매칭시켜야 할까요? 당연히 B의 가장 작은 칼로리.. [ICPC] Latin America Regional 2017 일부 문제 풀이 A. Arranging Tiles BOJ 15052번: https://www.acmicpc.net/problem/15052 이 문제의 핵심은, 어떤 2개의 다각형을 얼마나 가까이 붙일 수 있는 지 빠르게 계산하는 것입니다. 다각형을 배열하는 순서를 정하고, 그 다각형들에 대해 한 다각형의 x좌표 최댓값이 바로 다음 다각형의 x좌표 최솟값과 같게 배치했다고 합시다. 그렇다면 이 때의 해는 모든 다각형의 x축 길이 합에서, 모든 인접한 다각형 쌍에 대해서 다각형을 얼마나 가까이 이동시킬 수 있는지의 합을 뺀 것이 됩니다. 따라서 우리는 다각형 쌍이 주어졌을 때 이를 서로 붙일 수 있는 최대 길이를 미리 계산해 둔 뒤 가능한 모든 배열에 대해 해 중 최소를 찾아주면 됩니다. 붙일 수 있는 최대 길이를 모두 전.. [BOJ] 15404 Divide and Conquer 문제 요약 $N$개의 정점이 있고, 이 정점을 잇는 스패닝 트리가 2개 있다. 이 두 스패닝 트리의 합집합으로 구성되는 그래프에 대해(간선은 구별된다), $K$개의 간선을 제거하면 그래프를 연결 그래프가 아니도록 할 수 있다. 이 때 $K$의 최솟값을 구하고, 그 경우의 수를 $10^9 + 7$로 나눈 나머지를 출력하면 된다. 문제 풀이 가장 먼저 해야 하는 관찰은 다음과 같다. $K=2$이거나, $K=3$. 증명은 다음과 같다. 임의의 정점에 연결된 모든 간선을 제거하면 그 정점은 다른 정점과 연결되어 있지 않기에, 그래프는 연결 그래프가 아니다. 따라서 $K$는 모든 정점의 degree 중 최솟값보다 클 수 없다. 간선 하나는 정확히 두 개의 정점의 degree를 1만큼 증가시키므로, 모든 정점의 d.. 2020 숭고한 Marathon 참가 후기 Intro 원래는 Advanced Division에 참가하려고 했었는데, 팀노트를 만들기 귀찮았고 무엇보다 자신이 작성해둔 코드라도 인터넷 검색에 걸리면 표절이라는 룰이 있었기 때문에 굳이 참가할 이유를 못 찾았습니다. ALPS는 Contest나 Marathon에서 한 문제 이상 해결하면 회비를 면제해주기도 했고, thak00는 이기고 싶었기 때문에 정확히 thak00보다 한문제 더 풀려고 노력했습니다. 여담으로 이번에 domjudge를 처음 써 봤는데 CMS에 비해 매우 별로였습니다. CMS가 최고다! 마지막 두 문제 빼고는 전부 해결했습니다. M은 디버깅 코드를 안 빼고 제출한 관계로 대회 중에는 WA로 기록되어 있습니다. 각 문제를 해결하면서 느낀 점과 셋 구성, 디스크립션에 대해 잡설을 풀어보려고.. [BOJ] 16910 mex와 쿼리 [문제 링크](https://www.acmicpc.net/problem/16910) 문제 요약 다음과 같은 세 쿼리를 처리해야 합니다. [l,r]에 속하는 모든 자연수를 배열 A에 추가한다. 이미 있는 수는 무시된다. [l,r]에 속하는 모든 자연수를 배열 A에서 제거한다. 없는 수는 무시된다. [l,r]에 속하는 모든 자연수에 대해 있으면 제거, 없으면 추가한다. 각 쿼리를 수행 한 뒤에 이 배열에 없는 수 중 가장 작은 자연수를 찾으면 됩니다. 문제 풀이 일단 문제에서 요구하는 좌표가 크니 좌표 압축을 시도하고 생각합시다. 그 이후 Lazy Propagation 달려 있는 세그로 연산을 처리해주며 특정 구간에 존재하는 수의 개수를 세 주면 됩니다. Lazy 연산 중에 1번 쿼리와 2번 쿼리는 서로 상.. 이전 1 2 3 4 5 ··· 8 다음
