[알고리즘] Codeforces Round #751 (Div. 2)

연습용으로 예전 Contest에 버추얼참가를 했다.

아쉽게도 4솔에 실패했다.

세자리수 진입 실패

 

A - Two Subsequences [Solved!]

문자열 $s$가 주어지고 그 문자열을 $a, b$인 두 개의 문자열로 나눌건데 $a$는 사전순으로 가장 앞서는 문자열, $b$는 $s$에서 $a$를 제외한 문자열인 조건이 있을 때 나눠진 문자열들을 출력하는 문제이다.

 

$a$는 $s$에서 사전순으로 가장 앞서는 문자 하나이면 충분하다.

예를들어 $s = ``helloworld"$일 때 $a = ``d"$이고 $b  =``helloworl"$이 된다.

 

B - Divine Array [Solved!]

배열 $a$가 주어지고 그 배열에 연산을 여러번 하려고 할 때 $k$번 연산을 수행한 후 $x$번째 위치의 수를 묻는 문제이다. 

수행하려는 연산은 $a'$를 수행한 후 배열이라고 할 때 $a'_i=(a$에 있는 $a_i$의 개수$)$이다.

 

쿼리형 문제이고 연산은 무한번 가능하고, 쿼리에 들어오는 연산 횟수가 최대 $10^9$이어서 단순히 시뮬레이션해서는 풀 수가 없었다. 그렇다고 뭔가 규칙성도 보이지 않았다.

일단 $k$크기는 뒤죽박죽으로 들어올테니 오프라인 쿼리 기법을 사용해서 $k$를 오름차순으로 정렬하고 풀었다.

문제에서 무한번 가능하다고 나와있어서 연산을 많이 수행하다보면 언젠가는 연산을 수행해도 배열이 변화하지 않을 것이라는 믿음을 가지고 해결을 했다.

운좋게 이 방법으로 성공해서 AC를 받았다.

 

Editorial에서 최대 배열 길이만큼 연산하면 변화하지 않는다고 한다.

 

C - Array Elimination [Solved!]

크기가 $n$인 배열 $a$가 주어지고 배열에서 서로 다른 $k$개의 수를 골라 $x = a_{i_1} \& a_{i_2} \& \cdots \& a_{i_k}$ 라고 하자. $a_{i_j}:=a_{i_j}-x (1 \le j \le k)$를 여러번 수행하여 모든 원소를 $0$으로 만들 수 있는 $k$의 목록을 구하는 문제이다.

 

일단 $k=1$이면 언제나 가능하다. (자기 자신을 고르면 되기 때문)

그리고 초기상태에 모든 원소가 $0$이면 $1\le k \le n$ 모두 가능하다.

일단 내가 푼 방법은 모든 원소를 이진수로 바꾸고 각 자릿수에서 $1$인 원소의 개수를 세고 그 개수들의 최대공약수를 구한 뒤 그 수의 약수들이 답이었다.

이것도 약간 감으로 푼 문제여서 왜 이렇게 되는지는 잘 모르겠다.

 

D - Frog Traveler

개구리는 우물안 $n$ m에 빠져있고 $i$ m에서 한번 점프할 때 $a_i$ m까지 점프할 수 있고 $j$ m에 착지하면 $b_j$ m만큼 미끄러져 내려간다. 이 때 우물에서 탈출하기 위해 밟아야하는 높이들을 출력하면 된다.

 

대략적인 아이디어는 떠올랐는데 틀린 문제이다.

우선 내가 생각했던 아이디어를 적어보고자 한다.

현재위치에서 어디로 점프해야하는지를 구하지 말고 도착지점을 어디서 점프했는지를 구하자.

도착위치가 $x$ m이면 $x+1, \cdots, n$ 까지 돌면서 $x$m 에 착지할 수 있는지를 구하면 된다. (미끄러짐 고려하면서)

그렇게 $n$에서 $x$로 점프할 수 있다면 그 경로가 정답이다.

 

라고 생각했는데 python에서 MLE, C++에서 WA를 받아 틀린 방법이다.

 

Editorial에서 목적지로 갈 수 있는 step수를 dp테이블에 저장해서 특정 구간에서 최소를 찾는 구간트리를 사용해서 해결했다.

세그먼트 트리도 공부해야할 것같다.