ONTAK 2016

[2017.01.25 : 처음 작성]

[2017.03.03 : las / pod 문제 번역 실수가 있었습니다. 죄송합니다..]

[2017.03.13 : klo 문제 번역 실수가 있었습니다. 죄송합니다.. 이 글은 이제 마감합니다.]

https://sio2.mimuw.edu.pl/c/wiekuisty_ontak2016/

Problems

폴란드어 문제만 번역합니다. Day1 ~ Day4는 영어로 문제가 나오니까 그걸로 읽으시면 됩니다.

Day 5

Kłódka (klo)

0 이상 K 미만의 정수 배열 a[0] ... a[n-1] 이 있다. 0 이상 n-2 이하의 정수 x에 대해, 당신은 다음 두 연산을 할 수 있다.

 * inc(x) : a[x]와 a[x+1] 에, v <- (v + 1) mod k를 대입

 * dec(x) : a[x]와 a[x+1] 에, v <- (v + k - 1) mod k를 대입

(참고 : 원문에서는 두꺼운 손가락으로 자물쇠를 조작한다고 서술되어 있다.) 

정수 배열 a[0] ... a[n-1]을 b[0] ... b[n-1]으로 만들어야 한다. 당신은 inc와 dec를 합해서 "m/2"번 쓸 수 있다. "m/2"번 쓴 이후에도 a[i] != b[i]인 원소가 존재한다면 이러한 원소들은 수작업으로 바꿀 예정이다. 수작업으로 바꿔야 하는 원소의 개수를 최소화하여라.

Input

첫번째 줄에 배열의 크기 n, m, k가 주어진다. (1 <= n <= 1000, 1 <= m <= 100000, 1 <= k <= 100)

두번째 줄에 배열 a[0] ... a[n-1]이 주어진다.

세번째 줄에 배열 b[0] ... b[n-1]이 주어진다.

Output

최소값을 출력하라.

Limits and Subtasks

메모리 제한은 64MB이다.

1. m <= 500 (24점)

2. n <= 100 (24점)

3. nk <= 5000 (26점)

4. 추가 제약 조건 없음 (26점)

Example

입력

5 10 8

0 0 0 0 0

1 3 2 7 1

출력

1

설명

10번의 연산으로 1 3 2 7 7을 만들 수 있다. 마지막 수만 바꾸면 된다. 이것이 최적이다. 

Nowy Manhattan (man) 

두 점 (x1, y1)과 (x2, y2)이 주어졌을 때, 두 점간의 맨하탄 거리는 |x1-x2| + |y1-y2| 로 정의된다. 초기에 빈 점들의 집합 S가 있을 때, 다음 두 질의를 Q번 처리 해야 한다.

 * 1. 점 (x, y)를 집합 S에 삽입하라.

 * 2. 집합 S에 있는 점 중, 현재 점 (x, y)와 맨하탄 거리가 가장 짧은 점과의 거리를 출력하라.

Input

첫번째 줄에 질의의 수 Q가 주어진다. (1 <= Q <= 200000)

이후 Q개의 줄에 질의가 주어진다. 질의는 "a x y" (a = {1, 2}, 1 <= x, y <= 200000) 과 같은 형태의 세 정수가 주어지는데, 만약 a = 1이면 집합 S에 점 (x, y)를 삽입해야 하고, a = 2이면 집합 S에 있는 점 중 현재 점 (x, y)와 거리가 가장 짧은 점과의 거리를 출력해야 한다.

첫번째 질의는 항상 a = 1이다.

Output

a = 2인 질의가 주어질 때마다 순서대로 답을 새 줄로 구분하여 출력한다.

Limits and Subtasks

메모리 제한은 512MB이다.

1. Q <= 2000 (15점)

2. a = 2인 쿼리가 들어온 이후부터는 a = 1인 쿼리가 들어오지 않는다. (25점)

3. 추가 제약 조건 없음 (60점) 

Example

입력

6

1 4 2

2 3 3

2 1 5

1 10 8

2 4 3

2 1 1

출력

2

6

1

4

Słowa (slo) 

N개의 알파벳 소문자로 이루어진 문자열이 주어진다. 당신은 이제 임의의 길이의 알파벳 소문자로 이루어진 문자열인 "템플릿 문자열"을 만들 것이다. 템플릿 문자열은 문자열에서 1개 혹은 2개의 문자가 "Special" 하다고 지정되어 있다. 

좋은 템플릿 문자열은, N개의 문자열 중, 템플릿 문자열과 길이가 같으며, 템플릿 문자열과 정확히 일치하지는 않지만, Special한 글자를 제외한 모든 글자가 템플릿 문자열과 일치하는 문자열의 개수를 최대화하는 문자열을 뜻한다. 가장 좋은 템플릿 문자열과 일치하는 문자열의 개수는 몇개인가?

Input

첫번째 줄에 문자열의 수 N이 주어진다. (1 <= N)

이후 N개의 줄에 각각의 문자열의 길이 Li와, 문자열 Si가 주어진다. 

입력으로 주어지는 문자열은 모두 서로 다르다. 모든 문자열의 길이의 합은 200000을 넘지 않는다.

Output

가장 좋은 템플릿 문자열과 일치하는 문자열의 개수를 출력한다.

Limits and Subtasks

메모리 제한은 128MB이다.

1. 모든 문자열의 길이의 합은 2000을 넘지 않는다. (25점)

2. 추가 제약 조건 없음 (75점) 

Example

입력

8 

6 kamera 

4 kula 

4 kura 

4 tura 

6 kurant 

6 kaseta 

6 kareta 

6 kaleta

출력

4

(설명 : ka[a]e[a]a 를 생각해면 kamera kaseta kareta kaleta와 동일합니다)

Day 6

Największy wspólny dzielnik (gcd)

길이 n의 수열과, p개의 질의가 들어온다. 각각의 질의로 들어온 정수 d에 대해서, gcd(a_p, a_p+1, ...., a_q) = d 인 쌍 (p, q)의 개수를 출력하라. 질의를 온라인으로 처리하여야 한다.

Input

첫번째 줄에 정수의 수 n이 주어진다. (1 <= n <= 300000)

두번째 줄에 n개의 정수 a_i (1 <= a_i <= 10^18) 이 주어진다.

세번째 줄에 질의의 수 p가 주어진다. (1 <= p <= 300000)

이후 p개의 줄에 정수 c_i가 주어진다. c_i를, i-1번째 질의의 답인 ans_{i-1}과 xor 시킨 것이 d_i 이다. ans_0 = 0이라 하자.

Output

p개의 줄에 쌍의 개수 ans_{i}를 새 줄로 구분해서 출력한다.

Limits and Subtasks

메모리 제한은 512MB이다.

1. N, Q <= 120, d_i <= 40000 (11점)

2. N, Q <= 100000, d_i <= 100000 (1점)

3. s = 1, d_1 = 1 (25점)

5. 추가 제약 조건 없음 (53점) 

Example

입력

6

4 2 6 3 15 5

2

5

1

출력

2

4

Symulator Obrońcy Piłkarskiego 2016 (obr)

평면 상에 n개의 점이 주어진다. 이 중 어떠한 세 점도 한 직선 상에 존재하지 않는다. 당신은 임의의 직선을 골라서, 직선과의 거리가 D 이하인 점들을 모두 색칠할 수 있다. k개 이상의 점을 색칠할 수 있는 직선이 존재하는 최소 D를 출력하라.

Input

첫번째 줄에 점의 수 n과 k가 주어진다. (3 <= k <= n <= 2500)

이후 n개의 줄에 점의 위치인 정수 x_i, y_i (|x_i|, |y_i| <= 10^6) 이 주어진다. 

Output

최소 D를 출력하라. 절대 or 상대 오차 범위가 10^-9 안에 들어와야 한다.

Limits and Subtasks

메모리 제한은 256MB이다.

1. N <= 12 (10점)

2. N <= 80 (22점)

3. N <= 250 (22점)

4. N <= 1000, K <= 30 (26점)

5. 추가 제약 조건 없음 (30점) 

Example

입력

4 3

0 0

1 0

1 1

0 1

출력

0.353553390593

입력

4 4

0 0

1 0

1 1

0 1

출력

0.500000000000

Przesyłka (prz)

Weighted Directed Graph가 주어진다. (멀티 간선과 자가 루프는 없다). 이 중 K개의 정점에 술집이 있다. 

Q개의 쿼리로 시작점과 끝점이 주어지면, 시작점에서 끝점으로 가는 경로 중, 술집을 S번 이상 방문하는 경로를 출력해야 한다. 갔던 술집을 다시 갈 수는 있지만, 바로 다음 번에 가는 것은 안된다. (즉 처음에 3번 술집에 들렀다면 다음에 들리는 것은 3번 술집이면 안되고, 그 다음에 들리는 것은 3번 술집이어도 됨.) 이러한 경로 중, 최단 경로의 길이를 출력하라.

Input

첫번째 줄에 N, M, K, S, Q가 주어진다. (1 <= N, M, Q <= 100000, 1 <= K, S <= 100)

두번째 줄에 K개의 서로 다른 1 이상 N 이하의 정수가 주어진다. 술집이 있는 정점의 번호이다. 정점은 1번부터 N번까지 번호가 매겨져 있다.

이후 M개의 줄에 간선의 정보가 S_i, E_i, C_i 로 주어진다. S_i에서 E_i로 가는 가중치 C_i의 간선을 뜻한다. (1 <= S_i, E_i <= N, 1 <= C_i <= 100000)

이후 Q개의 줄에 각 쿼리의 시작점과 끝점이 주어진다. 

Output

각각의 쿼리마다 최단 경로의 길이를 새 줄로 구분하여 출력하라. 경로가 없으면 -1을 출력하라.

Limits and Subtasks

메모리 제한은 256MB이다.

1. Q <= 1 (10점)

2. N, M <= 100 (20점)

3. N, M <= 1000 (20점)

4. 추가 제약 조건 없음 (50점) 

Example

입력

4 6 2 4 6 

1 2 

1 2 50 

2 1 100 

2 3 90 

3 2 10 

3 4 20 

4 1 40 

1 2 

2 3 

3 4 

2 1 

3 2 

4 3

출력

200 

390 

370

250 

260 

330

Day 7

Las (las)

Undirected Forest가 주어진다. 몇개의 간선을 추가해서 이를 트리로 만들고 싶다. 간선을 추가하는 여러가지 방법 중, 각각의 정점 쌍의 거리의 합 (=sigma(i < j) dist(i, j)) 을 최소화하고 싶다. 

Input

첫번째 줄에 정점의 수 n, 간선의 수 m이 주어진다. (0 <= m < n <= 200000)

이후 m개의 줄에 간선의 시작점과 끝점 s e가 주어진다. (1 <= s, e <= n)

Output

가능한 거리 합의 최솟값을 구하여라.

Limits and Subtasks

메모리 제한은 128MB이다.

1. N <= 15 (15점)

2. M <= 3000 (25점)

3. 추가 제약 조건 없음 (60점) 

Example

입력

4 2

1 2

3 4

출력

10

Moda na sukces (mod)

1 이상 N 이하의 자연수를 정의역과 치역으로 하는 일대일 대응 함수를 순열이라 한다. 

크기 N의 순열 A와 B가 주어진다. 모든 i = [1, N] 인 자연수에 대해 A^k(i) = B^k(i) 인 최소 k > 0을 찾아라. 수가 너무 커질 수 있으니, 10^9 + 7로 나눈 나머지를 출력하라.

Input

첫번째 줄에 n이 주어진다. (1 <= n <= 1000000)

두번째 줄에 A(i)가 1 ~ n 순서대로 주어진다. 

세번째 줄에 B(i)가 1 ~ n 순서대로 주어진다. 

Output

모든 i = [1, N] 인 자연수에 대해 A^k(i) = B^k(i) 인 최소 k > 0을 찾아라. 수가 너무 커질 수 있으니, 10^9 + 7로 나눈 나머지를 출력하라.

Limits and Subtasks

메모리 제한은 256MB이다.

1. n <= 20 (10점)

2. n <= 100 (15점)

3. n <= 600 (15점)

4. n <= 5000 (20점)

5. n <= 100000 (20점)

6. 추가 제약 조건 없음 (20점) 

Example

입력

4 

2 3 4 1

3 2 4 1

출력

12

Podciąg (pod)

A와 B가 게임을 하고 있다. B는 처음에 자신의 문자열의 원소 중 몇개를 지워서, 부분 수열을 만든다. (부분 수열은 연속하지 않아도 되며, 부분 수열은 하나 이상의 원소를 지워야 한다.) 이렇게 만든 부분 수열이 A의 부분 수열이라면 A가 이기고, 아니라면 B가 이긴다.

A와 B는 길이 n / k의 문자열을 가지고 있다. A는 항상 이긴다는 조건 하에 자신의 문자열의 맨 뒤 원소 몇개를 제거할 예정이다. (즉 prefix를 가지고 게임을 할 예정이다.) A가 이김을 보장해주는 가장 짧은 prefix의 길이를 출력하라. 전체 문자열을 가져도 A가 진다면 -1을 출력하라.

Input

첫번째 줄에 n, k가 주어진다. (1 <= k <= n <= 500000)

두번째 줄에 A가 가지는 길이 n의 문자열이 주어진다.

세번째 줄에 B가 가지는 길이 k의 문자열이 주어진다.

Output

A가 이김을 보장해주는 가장 짧은 prefix의 길이를 출력하라. 전체 문자열을 가져도 A가 진다면 -1을 출력하라.

Limits and Subtasks

메모리 제한은 256MB이다.

1. n, k <= 3000 (20점)

2. n <= 30000, k <= 3000 (30점)

3. 추가 제약 조건 없음 (50점) 

Example

입력

7 4

bababab

abba

출력

5

Solutions

dan

왜 냈는지 모르겠다. 각각의 숫자에 적당한 랜덤 값을 부여한 후, 트리의 path 중 path 값의 합이 1 ~ K까지의 랜덤 값의 합과 같다면 원하는 경로라고 친다. 트리 분할정복을 통해서 이를 O(nlg^2n)에 하면 된다.

dum

적당한 전개를 통해서 ai의 합, i * ai의 합, i^2 * ai의 합으로 모든 식을 표현할 수 있으며 이를 binary indexed tree로 관리하면 된다.

mer

1번 정점을 "루트" 로 잡고, 1번 정점에 해당하는 상대적인 cost를 기록해두자. 변수 하나를 가지고 다니는데, 이는 2 <= i < j <= N 중, cost(j) - cost(i) != adj(i, j) (i와 j를 거래하는 데 드는 비용)을 만족하는 쌍의 개수이다. 이것이 0이 되면 NO일 것이다. 

들어오는 쿼리가 1번 정점과 연관되어 있지 않다면, 새롭게 들어온 쿼리가 현재 cost와 모순인지 간단하게 체크할 수 있다. std::map을 사용하면 O(lgn)이다. 1번 정점과 연관되어 있다면, 현재 cost를 바꾼 후, 나머지 n-2개를 다 일일히 돌면서 모순의 개수가 얼마나 바뀌었는지 확인한다. 이는 O(nlgn)이다. 이렇게 하면 total time complexity가 O(qnlgn)이 되고, 느리다. 

하지만, 굳이 1번 정점을 "루트"로 잡을 필요가 없다. 오프라인인 고로, 모든 쿼리를 저장한 후, 쿼리에서 가장 등장 빈도가 작은 원소를 루트로 잡자. 비둘기 집의 원리에 의해서 이러한 원소는 많아야 O(q/n)번 등장한다. 고로 O(qlgn) + O(q/n)O(nlgn) = O(qlgn) 시간에 문제가 해결된다.

blu

그냥 apio2012 guard랑 똑같은 문제다. 몇가지 예외 처리가 필요가 없어서 편하기는 하다.

coo

어떠한 음식에 대해서 <<>> 의 관계가 성립하는 경우가 전혀 없다는 문제의 조건이 있다. 고로 (<<??) = (<<<<) + (<<<>) (<<><) 이고, 이는 (<<<?) + (<<?<) - (<<<<) 이기도 하다. 결국, (<<<<) = (<<<?) + (<<?<) - (<<??) 이 되어서, k = 4인 경우를 k = 3인 경우와 k = 2인 경우로 reduction할 수 있다. 

k = 2인 경우는 잘 알려진 inversion counting 문제로 설명은 생략한다. BIT나 분할정복으로 O(nlgn)에 해결 가능하다. 

k = 3일 때는 BIT와 분할정복을 "같이" 이용해서 O(nlg^2n)에 문제를 해결할 수 있다. 쌍을 (a_i, b_i, c_i) 로 표현한 후, a_i 순으로 정렬해서 문제를 풀자. 분할 정복에서 구간을 합쳐주는 과정을 생각할 때, a_i < a_j 조건은 자명히 만족하고, b_i < b_j 이며 c_i < c_j인 조건을 만족해야 한다. 이는, 현재 구간에 있는 원소를 b_i 순으로 정렬한 후, c_i를 index로 한 BIT를 관리해줌으로써 해결할 수 있다. 합치는 데 O(nlgn)이 든 고로 총 O(nlg^2n)에 문제가 해결된다.

tre

Balanced BST에서, inorder 순으로 인접한 두 원소들은 부모 - 자식 관계를 이루고 있다. 새로 삽입할 원소는 그보다 작은 가장 인접한 원소의 자식이 되거나, 그보다 큰 가장 인접한 원소의 자식이 되거나, 둘 중 하나의 경우를 만족할 것인데, 한쪽은 이미 해당 방향의 자식을 갖고 있는 상황이기에, 둘 중 자식인 곳으로 가서 붙어야 할 것이다. 원소의 깊이는 쉽게 관리할 수 있기 때문에, 인접한 두 노드를 찾기만 했다면 어디 붙어야 할 지는 쉽게 알 수 있다. 

문제는 인접한 수 (즉, 현재 BST에 있으면서 그 수보다 작은 최대의 수 / 그 수보다 큰 최소의 수) 를 효율적으로 찾는 것이다. lower_bound, upper_bound의 정의와 맞닿아 있기 때문에 std::set을 통해서 O(nlgn)에 쉽게 찾을 수 있고, 이게 정해라고 생각했지만 이 루틴을 충분히 효율적으로 하지 않으면 TLE가 난다... 

다행이도 수가 크지 않기 때문에 이러한 수들을 O(n)에 찾을 수 있다. 그 수를 저장하지 말고, 각각의 수에 대해서, 이 수가 들어온 시간을 배열에 저장하자. (inverse permutation을 저장한다고 볼 수도 있겠음) 해당 배열을 순서대로 돌면서, 스택을 사용해서 원하는 값들을 전체 O(n)에 구할 수 있다. 이 부분에 대해서는 자세한 설명은 생략한다. 결론적으로 O(n)에 모든 문제가 해결된다.

bar

재밌는 문제다. 

답을 T라고 고정하고, T번의 연산 이후 답이 되는지를 빠르게 판별하는 접근법을 써보자. T번의 연산 이후 답이 됐다면 T 초과의 연산도 당연히 다 답이 되므로, 답에 대해 binary search를 쓸 수가 있기 때문이다. 

T번의 연산 이후 답이 되는지는 놀랍게도 O(nlgn)에 판별할 수 있다. 

가장 중요한 관찰은, F와 B를 굳이 순서대로 실행할 필요가 없이, 처음에 F만 실행하고, 나중에 B만 실행하는 식으로 연산을 시도해도, 최종 결과가 똑같다는 점이다. 처음에는 이 사실을 찍었는데 맞아서 (...) 증명을 시도했다. 인접한 BF를 FB로 항상 바꿀 수 있다는 사실을 증명하려고 했는데 (이 사실이 증명되면 버블 정렬의 요령으로 FFFBBB... 꼴을 만들 수 있다) 대충 그래프를 그려보면 직관적으로 납득은 가는데 엄밀한지는 잘 모르겠다. 

이제, 여러 개의 연속된 F를 한꺼번에 처리할 수 있는 방법을 고안해야 한다. 그걸 고안할 수 있으면 B는 똑같이 하면 되니까.. 신기하게도 이 과정을 O(nlgn)에 할 수 있는데, F가 k1개 있다고 하면, a_1에 올 수 있는 원소의 후보가 a_1 ~ a_{k1+1}, a_2 에 올 수 있는 원소의 후보가 a_1 ~ a_{k1+2} 위치에 있음을 알면 된다. 이 점을 알았을 때, a_1에 [1, k1+1] 구간의 최솟값을 넣고, a_2에 a_1에 넣은 걸 제외한 [1, k+2] 구간의 최솟값을 넣고... 를 반복하면 답을 찾을 수 있고, 이는 우선순위 큐를 사용해서 O(nlgn)에 할 수 있다. 고로 판별을 O(nlgn)에 할 수 있다. binary search가 들어가니 여기까지의 시간 복잡도가 O(nlg^2n)이다. 

한편, B를 처리할 때는 굳이 우선순위 큐를 사용하지 않고도 O(n)에 할 수 있다는 것도 주목해야 한다. B가 k2개 있다고 하면, 앞의 논리에 의해서, 위치 i에 있는 원소 a_i는 [1, i + k2] 구간까지 움직일 수 있다. 고로, 한 원소라도 a_i > i + k2일 경우, 정렬이 불가능하고, 모든 원소가 그렇지 않을 경우에는, 앞 방법에 의해서 정렬이 가능하다. 고로 B의 처리는 조금 더 간단해졌다. 여전히 시간 복잡도는 바뀌지 않지만.. 

대망의 O(nlgn)은 binary search를 제거함으로써 만들어 낼 수 있다. B를 따로 처리할 필요가 없이, F를 처리하는 과정 중에서 판별이 가능하게 앞에서 알고리즘을 수정했다. 현재 답의 크기를 T라고 하자. 처음에는 T = 0부터 시작해서 우선순위 큐를 관리한다. 만약에 불가능한 상황이 닥쳤을 경우, T+1번째 원소가 'B'라면 k2를 증가시키고, 아니라면 k1을 증가시킨다. 이렇게 해서, a_i <= i + k2를 만족할 때까지 T를 늘려주는 식으로 처리를 하면, 이진 탐색이 필요없어진다. 모든 원소를 처리한 후의 T의 값이 답이 된다.

gem

일단 모든 보석의 비용이 0 초과라고 가정하자. 안 그러면 꼬인다... 이거는 그냥 단순히 입력을 받을 때 보석이 아니라 돈을 버는 거라고 저장해 놓으면 된다. 이를 통해 O(nlgn)에 그리디한 방법으로 문제를 해결할 수 있다. 그 방법은 다음과 같다. 

* 처음에 보석을 가격 (같을 경우 등장 시간이 늦는) 순으로 정렬한다. 해당 보석을 산다고 했을 때 0 미만의 돈을 가지는 시점이 있는지 체크하고, 만약 그런 시점이 있으면 보석을 사지 않는다. 아니면 보석을 산다. 

이 방법은 Segment Tree에 Lazy Propagation을 넣으면 O(nlgn)에 구현할 수 있고 그에 대한 자세한 설명은 생략한다. 

정당성은 다음과 같이 증명할 수 있다. 보석을 애초에 살 수 없는 상황이면, 고민할 필요가 없다. 아닐 경우 보석을 살 수 있는데, 현재 보고 있는 보석을 S라 하고, S를 사지 않음으로써 살 수 있는 보석 중, 그 우선 순위가 가장 높은 보석을 T라고 하자. 

현재는, S나 T중 하나를 샀기 때문에, 가지고 있는 보석의 개수가 같다. 이제, T를 사는 경우보다 S를 사는 경우가 항상 더 많은 보석을 가지게 함을 증명한다. 

* Case 1. T가 S보다 위치가 앞에 있다. (위치라 함은 쿼리에서 등장하는 시간) 위치가 T보다 뒤인 모든 보석들은 더욱 더 사기가 힘들어 지며, T보다 앞인 보석들은 그 전과 차이가 없다. 

* Case 2. T가 S보다 위치가 뒤에 있다. 위치가 T보다 뒤인 보석들은 더욱 더 사기가 힘들어 진다. 위치가 S보다 앞이고, T보다 뒤인 보석들을 생각해 보자. 이러한 보석들은 T보다 우선 순위가 낮다. 한편, T는 S와 함께 양립할 수 없는 (그렇다면 0 미만으로 내려가는) 보석이다. 그 사이에 있는 보석들은 S 이상의 가격을 가지니, T와 양립할 수 없다. 고로, S보다 앞이고 T보다 뒤인 보석들은 그 전에도, 지금도 전혀 구매할 수 없다. S보다 앞에 있는 보석들은 차이가 없다. 

첫번째 보석에 대해서 이 논리가 성립하는 고로, 모든 보석에 대해서 귀납적으로 같은 논리를 적용할 수 있고, 고로 전술한 알고리즘은 정당하다.

각각의 기차 노선에 대해서 다음에 타게 될 기차 노선은 유일하게 결정된다. 이를 처음에 O(NlgN) 정도로 결정해 놓으면, 각각의 쿼리당 간단한 O(N) 시뮬레이션으로 문제를 해결할 수 있다. 

이를 최적화 하는 건 sparse table로 잘 알려진 동적 계획법을 사용하면 되는데, 2^0번 더 갔을 때의 기차 노선, 2^1번 더 갔을 때의 기차 노선... 을 결정해 주는 방식으로 2^K번째 다음 기차 노선을 전처리해주면, 각각의 쿼리마다 O(lgN)에 응답이 가능하다. 고로, 전체 문제가 O((N + Q)lgN)에 풀린다.

cri

사람이 풀 수 없다고 생각한다... 

k = 2일 때는, 패턴이 두 가지가 있다. 

* 가장 가벼운 사람이 돌아오고, 한 명이 가장 가벼운 사람과 떠남 

* 가장 가벼운 사람이 돌아오고, 무게 순으로 인접한 두 명이 떠나고, 두 번째로 가벼운 사람이 돌아오고, 돌아온 두 명이 떠남 

일단 패턴 2에서 무게 순으로 인접한 두 명이 떠나야 한다는 것은 어느 정도 자명하다. 그렇지 않다면 그 사람을 더 무거운 사람으로 대체해서 좋은 결과를 낼 수 있기 때문이다. 

하지만 여전히 저 두가지 패턴 만이 충분하다는 것은 확실치 않을 것이다. 이거는 강한필하고 증명을 해봤는데 오래 걸렸고 할 것도 상당히 많다. 고로 설명은 생략한다. 관심이 있으면 http://oi.edu.pl/static/attachment/20110811/oi11.pdf 75p - 81p를 참고. 

아무튼 저 사실을 받아들이면 (...) 가장 무거운 사람부터 패턴 1로 떠났는지 2로 떠났는지를 픽스해주는 방식으로 O(n)에 동적 계획법으로 풀 수 있다.

이제 k = 3일 때의 n^2 풀이를 설명한다. n^2 부분은 jcvb 풀이를 받아 적는 것에 가깝다. jcvb에 의하면 k = 3일 때 패턴이 네 가지가 있다. 왜 이걸로 충분한지는 나도 모른다. 화이팅! 

* 가장 가벼운 사람이 돌아오고, 무게 순으로 인접한 두 명이 가장 가벼운 사람과 떠남 

* 가장 가벼운 사람이 돌아오고, 무게 순으로 인접한 세 명이 떠나고, 두 번째로 가벼운 사람이 돌아오고, 돌아온 두 명이 떠남 

* 가장 가벼운 사람이 돌아오고, 무게 순으로 인접한 세 명이 떠나고, 두 번째로 가벼운 사람이 돌아오고, 돌아온 두 명과, 아직 가지 않은 한 명이 떠남 

* 가장 가벼운 사람이 돌아오고, 무게 순으로 인접한 세 명이 떠나고, 두 번째로 가벼운 사람이 돌아오고, 무게 순으로 인접한 세 명이 떠나고, 세 번째로 가벼운 사람이 돌아오고, 돌아온 세 명이 떠남 (총 6명 모두 무게 순으로 인접해야 한다.) 

패턴 1, 2, 4만 있다면 가장 무거운 사람이 어떻게 떠났는 지를 픽스해 주면 k = 2인 경우와 똑같이 O(n) 동적 계획법으로 풀 수 있다. 패턴 3이 문제인데, 다행이도 

* 패턴 3을 실행할 때, 같이 떠나는 3명은 가장 몸무게가 큰 3명, 혼자 가는 1명은 가장 몸무게가 작은 1명으로 해 줘도 충분하다. 

* 패턴 3을 맨 앞에서 실행해도 괜찮다 

는 좋은 성질이 있다고 한다. 왜인지는 잘 모르지만 직관적이니 뭐...

고로, 패턴 3을 실행한 횟수를 고정시키고 문제를 해결해보자. 패턴 3을 실행한 횟수를 X라고 했을 때, [2, 2 + X - 1] 구간과 [N - 3X, N-1] 구간에 있는 사람들은 다 오른쪽 사이드로 움직이고, 나머지 원소들만 수열에 남아있게 된다. 나머지 원소에 대해서 O(n) 동적 계획법을 사용하면 O(n^2) 풀이가 나온다. 

이제 O(n) 풀이가 나올 차례이다. O(n)을 만드는 건 n^2보다는 훨씬 쉽다. 몇가지 관찰과, 미친듯한 노오력만 있으면 된다 (...) 패턴 1, 2, 4만 있을 때, 최적의 sequence는 동적 계획법까지 쓰지 않더라도 상당히 간단한 꼴로 나온다. 정확히 3가지 형태가 있는데 

* 1 여러개 / 2 여러개 

* 1 여러개 / 2 / 4 여러개 

* 1 여러개 / 4 여러개 (순서대로다.) 

이 세가지 형태를 정말 열심히 처리해주면 (해보면 케이스가 더 나올거다) 문제는 구간 최솟값 문제로 바뀐다. 이 부분은 세그먼트 트리를 써서 O(nlgn)에 처리할 수도 있겠지만, O(n)에 할 수도 있다. 최솟값을 구하는 구간이 모두 (n+2)/4 지점을 지나기 때문에, 이 지점을 기준으로 하는 prefix / suffix minimum을 합쳐주면 되기 때문이다. 구간 최솟값이라고 하니까 케이스가 없어 보이지만 이 부분도 케이스를 나눠야 한다 (6으로 나눈 나머지가 3인지 0인지를 가지고 나눠야 한다 (....)) 시간 복잡도는 선형이고, 만점을 받을 수 있다.

quo

임의의 정점에서 현재 정점으로 오는 경로가 주어졌으니, 임의의 정점으로 가려면 입력을 뒤부터 봐가면서 유추해나가는 게 당연하다. 

그리고 몇가지 관찰을 더 하자면 

* LP, RP와 같은 패턴이 주어졌을 경우, 이 두 문자를 같이 지워도 답은 같다. 

* P만 N개 있는 문자열이면 답은 2^N이다. 

* L, R만 있는 문자열이면 답은 0이거나 1이며 이는 어렵지 않게 결정할 수 있다 

이제 문제를 풀 수 있다. 스택을 관리해서, P가 들어올 때마다 스택에 P를 쌓아주자. L과 R이 들어왔다면, 스택에 P가 있을 경우 P를 빼주고, 스택이 비었다면 현재 위치인 k를 바꿔주자. 문자열을 뒤부터 가면서 다 보고, 이 과정에서 답이 0이 되는 일이 일어나지 않았다면 2 ^ |스택 크기| 가 답이 된다. 

실제 구현시에는, 스택의 사이즈만 중요하기 때문에 스택이 아니라 P의 개수만 카운팅을 해도 해결이 가능하다.

squ

파싱을 해야 하는 문제인데 (..) 다행이도 그 부분은 그렇게 어렵지 않다. 일단 문자열의 구조가 단순하고, 또한 항상 올바른 것만 주어지기 때문에, 대충 top down으로 짜면 이 부분은 쉽게 해결할 수 있다. 파싱을 하면 이진 트리 형태로 입력을 분석할 수 있고, 이진 트리의 두 노드를 문제에서 나온 대로 합치면 O(|S|^2)의 시간이 걸린다. 이게 30점이 나와야 정상인데 난 이걸 구현하고 100점이 나왔다 (...) TLE 데이터를 만드는 것도 아주 쉽다. 뭐야..

아무튼, |S|lg|S|로 복잡도를 줄이기 위해서는 작은 거에서 큰 거로 합쳐주는 그 테크닉 (?) 을 사용하면 된다. 테크닉 자체에 대해서는 여기에 작성했다. 점들의 리스트 뿐만 아니라, x좌표가 i일 때 최대 y좌표를 가지는 셀 / 최소 y좌표를 가지는 셀, y좌표가 i일 때 똑같이... 이 리스트를 같이 관리하면, O(작은 집합 크기)에 merge가 가능하다. 저 리스트는 deque로 관리하면 된다. 이걸 구현하는 건 파싱보다 훨씬 더 더러우니까 화이팅..

klo

도저히 못 풀겠어서 원문을 읽었는데 잘못 읽은 거였다. 이런.... 폴란드어 너무 힘들다. 앞으로는 영어로 된 것만 풀어야지...

문제 자체는 어렵지 않다. 직관적으로 떠오르는 거는 현재 상태와, 쓸 수 있는 연산의 수가 주어졌을 때 오류의 크기를 최소화하는 것이지만, m이 상당히 크기 때문에 DP 인자에 갖고 다니기에는 너무 버겁다. 이럴 때는 인자를 바꿔서, 현재 상태와, 가능한 오류의 최대 개수가 주어졌을 때, 이를 만들기 위한 최소 m을 구하는 식으로 DP를 돌리자. 상태는 앞에서 넣었던 inc/dec의 양을 가지고 다니면 된다. 이렇게 하면 O(n^2k^2)인데, 반복되는 연산이 있어서 쉽게 O(n^2k)로 줄일 수 있다.

man

coo랑 아주 비슷하게 풀리는 문제. 오프라인으로 분할 정복으로 해결할 수 있다.

slo

솔직히 디스크립션 해석을 나도 못하겠어서 그냥 포기. jcvb 풀이를 봤는데 그냥 더러운 문제 같다

gcd

분할 정복으로 풀 수 있다. 분할 정복을 통해서 시작점이 [S, M] 이고 끝점이 [M+1, E]인 모든 gcd 쌍을 열거할 수 있는데, 이 때 prefix나 suffix로 가능한 의미 있는 gcd의 개수는 많아야 lg(10^18) 개이다. 개수가 적으니 단순 이중 루프만 돌려도 가능한 모든 구간 gcd와 그의 개수를 알 수 있다. 이를 모두 구한 후 std::map이나 적당한 정렬을 통해서 결과를 합쳐주면 쿼리를 이진 탐색 등으로 해결할 수 있다. 시간 복잡도는 O(NlgNlg(a_i)) 이다.

obr

답을 찾기 위해서, 모든 K개의 점들의 부분집합을 다 골라본 후, 그 점들을 모두 포함하는 최적의 직선을 찾는다고 생각해 보자. 부분집합이 정해져 있다면, 이 점 집합의 컨벡스 헐을 구한 후, rotating calipers를 하듯이 모든 기울기를 다 시도해보는 방법을 생각해 볼 수 있다. 

이제 이 rotating calipers 과정에서 봐야 하는 기울기의 후보는 컨벡스 헐을 이루는 변 중 하나라는 것을 보일 수 있다. calipers가 현재 두개의 점과만 접하고 있고, 어떠한 변과도 접하고 있지 않다고 생각해 보자. 접하는 변들 중 각도 상으로 가장 가까운 변으로 calipers를 이동했을 때, 이 각도가 x라면 cos(x) 배만큼 길이를 줄일 수 있다. 

이 관찰을 했다면 O(N^3lgN) 정도에 작동하는 솔루션을 만들 수 있다. 모든 N^2개의 기울기에 대해서, 해당 기울기를 기준으로 점들을 정렬하고, 길이 K의 모든 연속된 구간을 봐서, 해당 구간에 있는 점들을 모두 포함하며, 기울기는 정렬할 때 쓴 그 기울기를 그대로 유지하는, 최소 둘레를 계산하면 되기 때문이다. 

각도 기준으로 sweeping을 하면 이를 O(N^2lgN)에 작동하게 할 수 있다. 먼저 처음에 모든 N^2개의 기울기를 각도 순으로 정렬하고, 점들을 순서대로 바꿔주면서 점들의 각도 관계를 유지하게 하는 것이다. K개의 모든 연속된 구간을 봐야 하니 O(N^3) 솔루션이 아닌가 의아해 할 수 있겠지만, 현재 보고 있는 각도 상에서 한 직선상에 있는, 즉 당장 스왑을 하게 될 두 점이, 해당 직선에서 가장 멀리 떨어진 점이 될 것이다. 즉, 그 두점을 끝점으로 잡고 위 아래로만 trial을 해주면 된다는 것이다. 

이 부분이 이해가 안 가면, 아래 세 문제 중 하나를 해결해보자. 

http://koitp.org/problem/KOITP_201601_TRIANGLES/read/ 

https://www.acmicpc.net/problem/3121

https://www.acmicpc.net/problem/9484

결론적으로, O(N^2lgN)에 이 문제를 해결할 수 있다.

prz

각각의 쿼리에 대해서 가능한 경로는 시작점 -> 술집 1 -> ... -> 술집 S -> 끝점 의 형태일 것이다. 고로 모든 술집에 대해서 정점 v -> 술집 T, 술집 T -> 정점 v로 가는 최단 경로를 계산해 놓고, DP를 통해서 술집 S -> 술집 T로 가는 길이 S-1의 최단 경로도 계산해 놓고, 쿼리당 K^2에 대충 돌리면 풀 수 있다. 시간 제한이 넉넉해서 그냥 대충 하면 되는 문제... 복잡도는 O(SK^3 + KMlgM + QK^2) 이다. 

las

포레스트에 있는 각각의 트리를 어떻게 잇는 것이 거리의 합을 최소화 할 수 있을 지 살펴보자. 

먼저, 어떠한 트리가 다른 트리와 연결되어 있고, 둘을 연결하는 에지가 해당 트리의 centroid가 아니라면, 이를 centroid로 바꿔줌으로써 거리를 줄일 수 있다. (그렇지 않다면 centroid에 가깝게 움직였을 때 거리를 반복적으로 줄일 수 있다.) 이는 최적해에서 모든 추가된 에지들은 centroid를 잇는다는 결론으로 바꿀 수 있다.

같은 트리를 잇는 경로들의 거리는 바꿀 수 있는 게 아니니 신경쓰지 않아도 되고, 다른 트리를 잇는 경로들의 거리를 최소화해야 한다. 즉, centroid들을 잘 이어줘야 한다. 이 때는 트리의 사이즈가 가장 큰 centroid에 모든 에지를 몰아주는 것이 최적임을 알 수 있다. 그렇게 하면 O(n) 에 만점이 나온다. 

mod

무슨 CRT 쓰면 된다고 하는데 왜 되는지도 모르겠고 흑흑 난 못 품

pod

문자를 한 개 이상 지워야 하는 것이 문제의 정의인데, 생각해 보면 당연히 문자를 두 개 이상 지워서 쉽게 부분문자열이 되도록 만들어 줄 이유가 없다 (...) 고로 문자를 한 개만 지운다고 생각하자.

이제 답 T를 1부터 N까지 늘려가면서, 해당 길이의 prefix로 이길 수 있는지를 판별해보자. 지울 수 있는 모든 m개의 경우에 대해서, 현재의 prefix가 지울 수 있는 모든 m개의 경우 중 어떤 하나라도 subsequence로 가지지 않는다면, 해당 T는 답이 될 수 없다. subsequence 판별은 그리디로 쉽게 할 수 있다. 총 시간 복잡도는 O(n^3) 인데, T가 답이면 T+1 이상도 항상 답이 될 수 있기 때문에, 답에 대한 이진 탐색으로 쉽게 O(n^2lgn) 정도의 시간 복잡도가 나온다.

이 알고리즘을 O(nlgn)으로 줄이기 위해서는 T가 답인지를 선형 시간에 판단해야 한다. 그리디 알고리즘을 돌리면서, L[i] = B의 문자열 중 길이 i의 prefix를 포함하기 위해서 필요한 A의 최소 길이 prefix, R[i] = B의 문자열 중 길이 i의 suffix를 포함하기 위해서 필요한 A의 최소 길이 suffix 테이블을 O(n) 시간에 저장한다. 이제, i를 지웠을 때 해당 수가 subsequence인지 O(1)에 판별할 수 있다.