KimHwon

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;

#define TREE_NODE ll
#define ordered_set tree<TREE_NODE, null_type, less<TREE_NODE>, rb_tree_tag, tree_order_statistics_node_update>
// 중복이 있을 때 less<TREE_NODE> 이면 첫 원소, less_equal<TREE_NODE> 이면 마지막 원소

{
	ordered_set X;
	*X.find_by_order(x);
	X.order_of_key(x);
}

codeforces.com/blog/entry/11080

gcc.gnu.org/onlinedocs/libstdc++/manual/policy_data_structures_design.html

solved.ac 레이팅 시스템 바뀌면서 플래1로 올라왔길래 어려운거 위주로 풀어서 다이아까지 갔다. 올리는 김에 학교 2등까지 찍음.

실력에도 맞지 않는 너무 어려운 문제를 풀어댄 거 같다. 코포 블루가 다이아라니 좀 부끄럽다. 골플이나 밀어야지...

=== 수정1 ===

다시 학교 3등됨 ㅎㅎ

올라간 김에 기억에 남는 문제들 몇 개를 포스트로 써볼까 한다

난이도가 좀 괴상하다. B1+B2 푼 사람보다 C푼 사람이 더 많다.

꾸역꾸역 B2를 밀었더니 Codeforces Anytime에서 오렌지 퍼포먼스가 떴다 ㅋㅋ

A. Common Prefixes

인접한 두 문자열의 공통 prefix의 갯수가 주어질 때, 만족하는 문자열의 배열을 출력하는 문제. 각 문자열의 한 문자에 대해서 생각해보면, 서로 같은지 다른지만 중요하는 것을 알 수 있다. 따라서 모든 문자를 a와 b로 통일해보자. prefix 갯수만큼은 그대로 두고, 그 이후는 이전 문자열과 다르게 선택하면 된다. 문자열의 길이에 대한 조건이 있는데, 이미 조건을 만족했으므로 그냥 최대 길이인 200개로 꽉 채워서 만들어도 된다.

B2. Koa and the Beach

시간에 따른 파도를 { k, k-1, k-2, ... , 2, 1, 0, 1, 2, ... , k-2, k-1, k } 로 변환해보자. 그러면 각 위치에서 존재할 수 있는 시간이 구간으로 나타나게 된다. 시간이 지남에 따라 현재 높이를 잘 관리하면, 현재 높이가 구간 안에 들어가 있는지 확인해줄 수 있다. 만약 모든 구간이 가능한 경우 즉, 시간과 무관하게 항상 가능한 위치가 있다면 원하는 높이로 이동할 수 있다.
현재 높이가 구간 왼쪽에 있다면, 조금 더 기다려서 높이가 낮아지기를 기다릴 수 있다. 반대로 구간 오른쪽에 있다면 더 이상 진행할 수도 없고 기다릴 수도 없기 때문에 실패한다. 이 과정을 시뮬레이션하면 O(n)안에 해결이 가능하므로, 두 문제 모두 해결이 가능하다.

딱봐도 더러워보이는 문제다. 버추얼이라 그냥 망할 각오하고 구현했더니 다행히 맞았다. 레이티드였으면 나도 C로 도망갔을 것 같다.

C. String Transformation 1

제일 먼저, 더 작은 문자로는 변경할 수 없으므로 모든 문자를 순회하면서 예외처리해준다.
각 문자를 변경하는 과정을 그래프로 모델링해보자. 어떤 문자 X를 Y로 바꾸는 것을 정점 X에서 Y로의 간선으로 표현할 수 있다. 잘 관찰해보면 간선의 방향이 더 큰 문자 방향으로만 생기므로, 이 그래프는 DAG임을 알 수 있다. 즉, DAG에서 최소 갯수의 간선을 사용해서 모든 정점을 지나는 방법에 대한 문제가 된다. 그래프에서 모든 정점이 연결되면서 간선의 갯수가 최소인 경우는 spanning tree임이 자명하다. 트리의 간선의 갯수는 (연결된 정점의 갯수)-1 이므로 union-find 등으로 그래프의 연결 상태를 세어주고 간선의 갯수를 계산하면 된다. 그래프들이 서로 연결되지 않을 수도 있음에 주의하여, 각 컴포넌트끼리 따로 계산해준다.

약간 짬밥?으로 풀었다. 아이디어가 없어서 말린 문제들 중에 그래프로 모델링하는 풀이가 많았어서, 뭔가 상태 전이가 있는데 아이디어가 전혀 떠오르지 않으면 그래프로 한번 모델링해보는 경향이 있다. 모델링해보니까 금방 규칙이 보였다.

딥3라 언레. 너무 급하게 풀어서 그런지 B번에서 뇌절을 심하게 했다.

A. Spy Detected!

map을 사용해 등장한 숫자의 개수를 세고, 1개인 원소의 위치를 출력함.

B. Almost Rectangle

두 점의 위치를 각각 (x1, y1), (x2, y2)라고 하면, 조건을 만족하는 위치들은 (x1, y1), (x1, y2), (x2, y1), (x2, y2) 이다.
그런데 만약 x1과 x2가 같거나 y1과 y2가 같으면 직사각형 모양이 나오지 않기 때문에 x'을 임의로 x1+1 또는 x1-1로 정할 수 있다. 둘 중에 가능한 것 하나를 골라서 새로운 위치로 지정한다. 마찬가지로 y에 대해서도 y'을 잘 정한다.
쉬운 문제였지만 x' 또는 y'이 가능한지 확인을 제대로 하지 못해서 두 번이나 틀렸다. 너무 긴장해서 급하게 제출했던 것 같다.

C. A-B Palindrome

constructive하게 해결이 가능하다. 수열에서 0의 갯수와 1의 갯수가 주어지므로(각각 a와 b), 입력된 수열에서 이미 정해진 숫자만큼 미리 센다. 만약에 a나 b가 음수가 되면 더 볼 것도 없이 불가능한 상태이다.
수열을 한 번 순회하면서 S[i] == S[N-1-i]를 만족하도록 ?를 가능한대로 채워 넣는다. 동시에 a와 b를 소모하면서 음수가 되지 않는지 확인한다. 이렇게 하여 먼저 자명한 숫자들에 대해서 팰린드롬을 만족하게 할 수 있다.
남는 ?들에는 숫자를 가능한대로 채워 넣는다. 다 채웠을 때 a나 b가 음수가 되면 불가능한 상태임을 알 수 있다.

D. Corrupted Array

먼저 미리 주어진 수열의 합을 구해둔다. 그 후 주어진 수열 b를 순회하면서 b에서 제외할 숫자 x를 정한다. 수열의 총 합에서 x를 뺀 값은, a의 각 원소들과 a의 모든 원소의 합이다. 다시 말해서 (a의 합)*2이라는 뜻이다. 이를 2로 나눈 뒤 (나눠지지 않으면 예외처리한다.) 그 값이 b에 존재하는지 set등을 사용해 확인한다.

E. Permutation by Sum

구간 [L, R]에 대해서 가장 작은 경우는 [1, 2, ... , L-R+1]이고 가장 큰 경우는 [N, N-1, ... , N-(L-R+1)]이다. S가 가장 작은 경우랑 큰 경우 바깥이면 불가능하다. 반대로 가장 작은 경우랑 큰 경우 안쪽에선 S를 만족하는 수열이 항상 존재한다.
만약 가장 작은 경우에 모든 원소에 1씩 더해준다고 하면, 구간합이 L-R+1씩 증가한다. 그런데 구간의 길이가 L-R+1이므로 한 원소씩 더해주면 사이에 모든 공간이 채워진다.
큰 원소부터 하나씩 더해나가면 구간 [L, R]의 합이 S면서 항상 서로 겹치지 않는 수들의 집합으로 만들 수 있다. [L, R]을 잘 구성하고 남은 위치들에 아직 사용되지 않은 수를 적절히 채워 넣으면 된다.

F. Education (업솔빙)

각 위치에서 가진 돈을 일차함수로 그려보면 CHT 처럼 나타난다. O(n)으로 시뮬레이션하면서, 현재 일차식과 다른 일차식을 비교해서 목표하는 돈을 먼저 모으는 쪽으로 계속 업데이트해 나가면 된다.

C번에서 엄청 말렸다. 결과는 똑떨.  아슬아슬하게 1600점 파킹했다.

학기 시작하고 PS를 자주 못하니 실력이 떨어지는게 눈에 보이기 시작했다.

A. Déjà Vu

처음 주어진 문자열이 팰린드롬이라면 정가운데를 제외하고 어디에 넣든지 팰린드롬이 아니게 된다. 주어진 문자열이 팰린드롬이 아닌데 a를 넣어 팰린드롬이 되는 경우를 생각해보면, 만약 맨 뒤에 a를 추가해 팰린드롬이 되었다면 반대로 맨 앞에 a를 추가한 경우는 전자를 왼쪽 쉬프트한 문자열이고 반대도 마찬가지다. 따라서 둘 중 하나는 무조건 팰린드롬이 아니게 된다. 따라서 처음 주어진 문자열의 맨 앞 또는 맨 뒤에 a를 추가해보고 둘 다 팰린드롬이 나오는 경우만 제외한 모든 경우가 불가능하다.

B. Flip the Bits

주어진 문자열을 반전시킬 수 있는 조건은 그 부분수열의 0의 개수와 1의 개수가 같아야 한다. 그런데 0과 1의 개수가 같으므로 반전시킨다고 해도 같다는 것이 보장되며, 처음 상태에서 0과 1의 개수가 같기만 하면 얼마든지 연산을 적용해도 성립함을 알 수 있다. 따라서 주어진 문자열을 뒤에서부터 확인하면서 두 문자열이 같아지도록 마음대로 뒤집으면 된다. 반전하지 못하는 경우가 생기면 실패이고, 아니면 성공이다. 뒤집어진 상태를 boolean 으로 플래그를 정해서 관리하면 편리하다.

C. Balance the Bits

일단 괄호 문자열의 시작점은 여는 괄호, 끝점은 닫는 괄호임이 자명하다. 따라서 두 괄호문자열의 시작점과 끝점은 동일해야 하므로 둘다 1로 표시되어야 한다. 또한 첫 번째 괄호 문자열이 성립한다고 가정했을 때 두 번째 괄호 문자열도 성립하려면, 첫 번째 괄호 문자열에서 짝수 개의 괄호가 바뀌어야 한다. 따라서 주어진 수열에 1과 0이 모두 짝수 개 등장해야 한다. 이 조건을 만족하면 모두 성립한다.

괄호 문자열을 construct하는 방법은, 첫 번째 괄호 문자열을 ()()()... 이런 식으로 정한다. 두 번째 괄호 문자열은 첫 번째에 맞춰서 정한다. 두 개씩 끊어서 하나로 보고, 두 번째 문자열이 성립하지 않으면 반전시키고 첫 번째 문자열도 함께 반전시킨다. 이렇게 되면 첫 번째 괄호 문자열은 () 또는 )(로만 이루어지는데 이는 항상 성립하는 형태이다.