Eau de Cologne

사전 지식 Lazy Segment Tree의 구현 Atcoder Library의 Lazy Segment Tree 설명: https://atcoder.github.io/ac-library/production/document_en/lazysegtree.html 레이지 세그먼트 트리는 타입 $S$와 $S \rightarrow S$로 가는 함수들의 부분집합 $F$가 존재해서, 각 원소가 $S$ 타입인 배열에서 다음 일을 할 수 있습니다. 배열의 연속된 구간과 $f \in F$가 주어지면, 연속된 구간의 각 원소를 $s_i$에서 $f(s_i)$로 바꿉니다. 배열의 연속된 구간$[s_l, \cdots, s_r]$이 주어지면, $s_l \circ \cdots \circ s_r$ 을 구합니다. 여기서 연산 $\circ..

D5~ 문제들을 작성합니다. https://www.acmicpc.net/problem/19297 19297번: Logistical Metropolis 첫 번째 줄에 두 정수 $N$, $M$($1 ≤ N ≤ 100\,000$, $N-1 ≤ M ≤ 300\,000$)이 공백 하나로 구분되어 주어진다. 다음 $M$개 줄의 각 줄에는 건설 가능한 워프 게이트의 정보를 나타내는 세 정수 $x$, $y$, $c$($www.acmicpc.net 풀이 더보기 처음에 Minimum Spanning Tree를 만듭니다. 이 이후에 무조건 사용되는 간선(여기서는 i번과 모두 연결된 간선)이$k$개 정해졌을 때, 이 계산을$\tilde{O}(k)$ 안에 하는 문제입니다. 각 정점마다 정점 차수만큼의 간선을 지정하고, 모..

P5~D5 정도 난이도 문제를 작성합니다. https://www.acmicpc.net/problem/23495 23495번: Longest Lyndon Prefix For each test case, output $n$ integers denoting $l_1, l_2, \dots, l_n$. www.acmicpc.net 풀이 더보기 문자열 $A$와 문자열 $B$의 비교는 뒤에 임의의 문자열 $S$를 붙인 문자열 $AS$와 $BS$의 비교와도 동일합니다. 그렇기 때문에 부분문자열의 suffix를 비교할 때, 전체의 suffix를 비교해도 됩니다. 전체의 suffix array를 구해서 문자열의 rank를 구합니다. 이 이후에는, 모든 rank가 자기 자신보다 큰 부분문자열의 최대 길이를 stack등을 이..

https://www.acmicpc.net/problem/7140 7140번: 데이터 만들기 1 오늘날 세상에는 많은 프로그래밍 대회가 있다. 대회에 사용할 좋은 프로그래밍 문제를 만드는 일은 매우 어렵다. 그 중 가장 어려운 일은 테스트 데이터를 만드는 일이다. 좋은 테스트 데이터 www.acmicpc.net 풀이 이후 작성 https://www.acmicpc.net/problem/16161 16161번: 가장 긴 증가하는 팰린드롬 부분수열 팰린드롬 수열이란 앞에서부터 읽을 때와 뒤에서부터 읽을 때 똑같은 수열을 말한다. 수열 {13, 25, 3, 25, 13}, {9, 5, 5, 9}는 팰린드롬이고, {1, 2, 3, 4, 5, 6, 7, 6}, {1, 2, 5, 4, 2}, {1, 1, 3, 2, ..

https://www.acmicpc.net/problem/18790 18790번: N의 배수 (1) 첫째 줄에, 조건을 만족하는 수 $N$개를 공백으로 구분하여 출력한다. 답을 만족하는 경우가 여럿 있는 경우, 그 중 임의의 하나를 출력하면 정답으로 인정된다. 출력하는 수들의 순서는 관계 없 www.acmicpc.net 풀이 이후 작성 https://www.acmicpc.net/problem/20943 20943번: 카카오톡 카카오톡은 주식회사 카카오가 2010년 3월 18일 서비스를 시작한 글로벌 모바일 인스턴트 메신저로, 2020년 기준 $4\,000$만 명의 사용자가 등록돼 있고 시장 점유율이 $96$%로 사실상 거의 모든 국민 www.acmicpc.net 풀이 이후 작성 https://www.ac..

https://www.acmicpc.net/problem/2829 2829번: 아름다운 행렬 첫째 줄에 행렬의 크기 N이 주어진다. (2 ≤ N ≤ 400) 다음 N개의 줄에는 행렬의 성분이 공백으로 구분되어 주어진다. 각 성분은 [-1000,1000] 범위 안에 들어있다. www.acmicpc.net 풀이 이후 작성 https://www.acmicpc.net/problem/25116 25116번: TOO EASY Cookie Run The first line contains three space-separated integers, $N$, $M$, and $K$. The second line contains $N$ space-separated integers $A_{0}, A_{1}, \cdots, A..