hyperion1019 님의 블로그

원본 글 링크 : https://www.editorialhub.site/blog/2/post/116 EditorialHub www.editorialhub.site(에디토리얼 허브에도 같은 글을 작성했습니다) 주어진 수열에는 변화가 일어나지 않기 때문에 각 쿼리를 오프라인으로 처리한다고 생각할 수 있겠다. 쿼리들을 L의 오름차순으로 정렬을 시켜보자.L을 1번 위치에 고정시켰을 때, 배열을 정렬시키기 위해 각 원소에 가해야 하는 연산의 양을 A[i]라고 한다면, O(N)의 시간 안에 해당 배열을 모두 채울 수 있을 것이다.1번 위치에서 L을 한 칸 오른쪽으로 이동시켰을 때, A[i]에 나타나는 변화를 잘 관찰해보면, A[2]=0이 되고 오른쪽 원소들은 정확히 그만큼 2가 덜 곱해져도 되는 것이므로 A[2]만..

sjh1224와 둘이서 NWERC 2020을 돌았다. 앞으로 리저널을 돌고 반성할 점 같은 걸 리뷰 쓰면서 좀 적어보려고 한다.  나는 이렇게 풀었고, 나머지를 sjh1224가 풀었다. [~00:09] sjh1224가 A부터 보고 내가 K부터 봤다. K는 그냥 브론즈 문자열 문제라서 딱히 적을 건 없는 것 같다.[~00:17] 스코어보드를 보니 H가 많이 풀렸길래 H를 잡았다. 수열을 정리하고 floor(N/2)부터 앞 뒤로 왔다갔다 하면서 출력해주면 끝.[~00:45] sjh1224가 C랑 D를 바로 풀어주었고, 그동안 A를 고민했다. A는 10^9 이하의 수가 주어지고, 1~N까지의 덩어리들의 점수가 각각 주어졌을 때, 해당 수를 가장 점수가 적게끔 크기가 N 이하의 수들로 나누는 문제이다. 이때 크..

한동안 배보다 배꼽이 크다는 느낌이 들어 문제 풀이를 기록하지 않았다. 여기에 풀이를 적어놓으면 문제 풀기 싫을 때 틈틈이 내가 풀이를 보고 아이디어를 점검하지 않을까라는 생각으로 블로그를 시작했는데 나에 대한 지나친 기대였다. 그래도 아예 안 쓰다 보니 너무 휘발성이 강한 것 같아서 다시 좀 써보려고 한다. 최근 혼자 연습할 때는 팀연습 때 돈 ICPC 셋을 업솔빙하거나 JOI를 밀고 있다. JOI 문제들이 주제가 한정적이긴 하지만 퀄리티가 엄청나게 좋은 것 같다. 그래서 오늘은 저번주에 밀었던 JOI 2019/2020를 리뷰해보려고 한다. 5번은 에디토리얼을 깠고, 까고도 풀이를 이해하느라 정말 고생했다. 너무 어려웠는데 기여창을 보니 다들 쉽게 푸신 거 같아 좀 시무룩해졌다. 1. Just Long..

문제 요약수열이 주어진다. 해당 수열에 다음과 같은 연산을 할 수 있다.1. 수열에서 임의의 부분수열(subsequence)를 고른다2. 부분수열의 홀수 번째 원소에 +1, 짝수 번째 원소에 -1을 하거나, 홀수 번째 원소에 -1, 짝수 번째 원소에 +1을 한다.전체 수열의 모든 원소를 0으로 만들기 위한 연산의 필요 최소 횟수를 구하라. 풀이풀이가 매우 간단하지만 나름대로의 인사이트가 있는 거 같아서 가져와봤다.먼저 누적합 배열을 생각해보자. 주어진 연산은 이 누적합 배열의 부분수열에 1을 더하거나 빼는 것으로 바꿔서 생각할 수 있다. 원래 배열의 i번째 원소에 1을 더하고 j번째 원소에 1을 뺀다면(i풀이가 엄청 간단한데 떠올리기 쉽지 않은 것 같아서 가져와봤다.

문제 요약

너무 좋은 글이라 이대로 휘발되는 게 아까워 정리를 해보려 한다.1. DFS tree란?무향 연결 그래프에서 정점을 하나 루트로 잡고 해당 정점에서 방문하지 않은 정점들을 DFS order에 따라 방문했을 때, 지나는 간선들로 이루어지는 트리를 말한다.DFS tree는 따라서 다음의 두가지 간선으로 분류된다.(1) spanning edge : DFS 트리를 이루는 간선이다.(2) back edge : DFS 트리를 이루지 않는 간선, 즉 DFS를 했을 때 지나가지 않는 간선이다.back edge는 반드시 어떤 정점과 해당 정점의 ancestor를 잇는다는 특징을 갖는다. 만약 그렇지 않다면 해당 간선의 끝 점 중 하나가 방문되었을 때 나머지 하나가 방문되지 않았을 상태였을 것이고, 따라서 해당 간선을 지..

문제 요약알파벳의 첫 c개의 문자로만 이루어진 길이 N짜리 문자열이 주어진다(c=2라면 A와 B로만 이루어진 문자열, c는 18이하, N은 2^18이하). 각각의 단어의 case는 해당 단어가 어떤 글자로 끝났는지에 따라 결정된다. 각 단어의 길이가 최대 K개일 때, 주어진 문자열이 단어들을 띄어쓰기 없이 나열한 것이라면 해당 단어 집합에서 나올 수 있는 최소 case의 개수를 구하여라.풀이일단 딱 봐도 비트마스킹 DP라는 생각은 빠르게 든다. DP[i][state]=i번째 문자까지 봤을 때, state로 표시된 문자를 case로 삼을 수 있다면 1, 아니라면 0으로 놓고 풀면 O(N*2^c)안에 돌아가는 프로그램을 짤 수 있다.하지만 이건 너무 느리다. 2^36은 너무 큰 숫자이다. 여기서 최적화를 하..

문제 요약n개의 정점과 m개의 간선으로 이루어진 무향 연결 그래프가 주어진다.(n은 10000이하, m은 n-1 이상이고 셀프 루프나 중복 간선은 주어지지 않는다.) 각 그래프는 처음에 색이 칠해져 있지 않은 상태이고, 3개의 색으로 각 정점을 칠할 수 있다.엘리스와 밥이 n개의 라운드로 이루어진 게임을 하려고 한다. 각각의 라운드에서 엘리스는 두가지의 다른 색깔을 고르고, 밥은 그 중 하나의 색깔을 골라 아직 칠해지지 않은 정점 중 하나를 해당 색깔로 색칠한다. 게임이 끝나고 같은 색으로 칠해진 정점이 간선으로 연결되어 있으면 엘리스가 이기고, 그렇지 않으면 밥이 이긴다.그래프가 주어졌을 때, 엘리스 또는 밥을 선택하여 플레이해서 이기는 방법을 출력해라.풀이그렇게 어려운 문제는 아니지만, 인터랙티브 문..

문제 요약철수가 컴퓨터 게임을 한다. 철수의 레벨은 처음에 1이고 n마리의 몬스터와 싸워야 한다.(n은 200000 이하)각각의 몬스터는 다음과 같은 행동을 한다1. 철수의 레벨이 몬스터의 레벨보다 높다면 몬스터는 도망간다.2. 그렇지 않다면, 몬스터는 철수와 싸운다.매 k번째 전투가 끝날때마다 레벨업을 한다. 다음과 같은 q개의 쿼리를 처리해야 한다.i x : 만약 k가 x일 때, i번째 몬스터와 싸울 것인가?(q는 20만 이하, i와 x는 n 이하)풀이라이브 때는 머지소트트리로 접근했다가 무수한 TLE를 맞고...실패했다... 점수를 많이 떨군 가슴 아픈 셋이다.핵심은 K에 따라 i번째 몬스터와 싸울지가 단조적으로 결정된다는 것이다. 즉 어떤 a=K에서 i번째 몬스터와 싸운다면, 모든 K>=a에서는 ..

문제 요약N개의 도시와 도시 사이를 잇는 단방향 도로 M개가 주어진다(N은 5000 이하, M은 20만 이하). 각 도시에는 1~N까지 번호가 붙어 있으며, 도로는 항상 번호가 낮은 도시에서 높은 도시로 향한다.두 명의 친구 A와 B가 1번 도시에서 N번 도시로 이동을 하려고 한다. 이동을 하는 방식은 조금 특이한데, A와 B가 각각 현재 도시에서 이동할 수 있는 도로을 하나씩 고른다. 만약 이 도로가 일치한다면 해당 도로를 타고 다음 도시로 이동을 할 수 있지만, 고른 두 도로가 일치하지 않는다면 해당 도로들은 폭파되고, 다시 선택을 해야 한다.A는 언제나 최선의 선택을 하고, B는 랜덤으로 도로를 고를 때, A와 B가 N번 도시에 도착할 수 있을 확률을 구하시오.풀이일단 문제 세팅이 많이 당황스럽다...