Educational Codeforces Round 147 (Rated for Div. 2)
Educational Codeforces Round 147 (Rated for Div. 2)
A. Matching (800)
처음이 $0$으로 시작하면 답은 $0$이다.
처음이 $?$로 시작하면 그건 $9$를 곱해주고,
나머지 $?$들은 모두 $10$을 곱해준다.
B. Sort the Subarray (1100)
투포인터로 좌우의 끝부터 $a_i=b_i$ 이면 계속 좁혀주고 서로 다른 첫 구간을 $l', r'$ 라 하자.
이제 그 구간을 정렬할 것이므로 $a[l'-1]$ 가 구간에서 가장 작다면 왼쪽으로 확장, $a[r'+1]$ 가 구간에서 가장 크다면 오른쪽으로 확장할 수 있다.
void solve() {
int n;
cin >> n;
vi a(n), b(n);
fv(a);
fv(b);
int l = 0, r = n - 1;
set<int> s;
while (l < r) {
if (a[l] == b[l]) {
l++;
continue;
}
if (a[r] == b[r]) {
r--;
continue;
}
break;
}
for (int i = l; i <= r; i++) s.insert(a[i]);
while (l - 1 >= 0 && a[l - 1] <= *s.begin()) {
s.insert(a[l - 1]);
l--;
}
while (r + 1 < n && a[r + 1] >= *s.rbegin()) {
s.insert(a[r + 1]);
r++;
}
cout << l + 1 << ' ' << r + 1 << endl;
}
C. Tear It Apart (1300)
길이 $k$의 문자들을 모두 지우는 개수는 $f(k)=1+f\left( \left\lfloor \dfrac{k}{2} \right\rfloor \right)$ 로 DP로 전처리해둘 수 있다.
$26$개의 문자들을 모두 순회하며, 그 문자와 다른 것들을 하나의 블록으로 본다.
그 블록의 길이 들 중 가장 $f$가 큰 것이 그 문자만 남기는데 필요한 최소 횟수이다.
int remove_cost[200005];
void pre_calc() {
remove_cost[1] = 1;
for (int i = 2; i <= 200000; i++) {
remove_cost[i] = 1 + remove_cost[i / 2];
}
}
void solve() {
string s;
cin >> s;
vvi idx(26);
for (int i = 0; i < sz(s); i++) {
idx[s[i] - 'a'].pb(i);
}
int ans = 1e9;
for (int i = 0; i < 26; i++) {
if (!sz(idx[i])) continue;
int tmp = 0;
// 시작
maxa(tmp, remove_cost[idx[i][0]]);
maxa(tmp, remove_cost[sz(s) - 1 - idx[i].back()]);
for (int l = 0; l < sz(idx[i]) - 1; l++) {
int len = idx[i][l + 1] - idx[i][l] - 1;
maxa(tmp, remove_cost[len]);
}
mina(ans, tmp);
}
cout << ans << endl;
}
D. Black Cells (1900)
Observation 1
구간은 모두 떨어져있다.
Observation 2
길이 $2$이상의 구간은 스킵할 필요가 없다. 구간이 최소 $1$ 떨어져있기 때문에 shift를 눌렀다 떼는 동작을 아끼는거랑 다음 구간으로 넘어가는 최소 $2$번의 이동횟수와 같기때문이다.
Observation 3
길이 $1$의 구간은 이미 지나왔다면 모두 동일하게 생각해줄 수 있다.
이미 지나온 구간에서 어떤 길이 $1$의 구간을 먼저지났냐 늦게지났냐는 정답에 영향을 미치지 않는다.
Solution
나는 이분탐색을 썼지만 $O(n)$에 구할 수 있다.
현재 지나온 구간에서 길이 $2$이상인 구간의 총 길이 합을 $s$라고 하고, 길이 $1$인 구간의 총 길이 합을 $c$라 한다.
1- $s+c < k$ 라면 아직 모두 사용해도 채우지 못한다는 것이므로 넘긴다.
2- $s < k,~~ s+c \ge k$
긴 구간만으로 $k$를 채울 수 없지만 $1$구간들 몇개를 써서 채울 수 있다는 것을 의미한다.
이때의 정답은 $2 \cdot$ (써야하는 길이 $1$구간 수 + 지금까지 지나온 길이 $2$이상 구간수) + 현재 구간의 가장 끝의 위치 이다.
왜 현재 구간의 가장 끝 위치인지 $\Rightarrow$ 길이 $1$의 구간을 최소로 골라 $k$가 될 때 까지만 사용할 것이기 때문에 끝나는 구간은 현재 구간의 끝이다.
3- $s \ge k$
이땐 긴 구간들만 으로 $k$개를 채울 수 있으므로
$2 \cdot (\text{지금까지 지나온 2이상의 구간의 개수})+(L_i+\text{현재 구간에서 어디까지 가야하는지})$
가 정답이 된다.
2,3번 케이스에서 가장 작은 값을 정답으로 채택하면 된다.
E. Rearrange Brackets (2100)
올바른 괄호 문자열이 주어진다.
우선 문제에서 얘기하는 Minimum cost를 만드는 그리디한 방법은 뒤에서부터 () 인 괄호를 제거해나가는 것이다.
이를 다시 해석하면 ((())) 같은 친구는 2+1 이 소모되므로 어떤 ) 를 기준으로 자신을 감싸고 있는 괄호 쌍의 개수를 모두 더한것이 최소 비용이다.
따라서 우리의 목적은 최대한 겹쳐진 괄호를 제거하는 것에 있다는 걸로 재정의된다.
$k \le 5$이기 때문에 매 단계 직접 문자열을 구성해줄 수 있다.
어떤 괄호가 있고 인덱스가 $l, r$ 이라면 이 괄호를 없앰으로 얻을 수 있는 이득은 $\dfrac{r-l-1}{2}$이다.
따라서 항상 가장 바깥쪽에 있는 괄호를 재배열하는게 최적이다. 그리고 가장 바깥쪽의 괄호는 올바른 괄호 문자열에 항상 존재한다.
((())(())) 처럼 되어있다면 가장 바깥의 괄호를 앞이나 뒤로 붙여 ()(())(()) 처럼 만들어줄 수 있다.
따라서 괄호 중 $r-l$ 이 가장 큰 것중 하나를 다른 하나 옆으로 붙여주는것이 항상 최적이다.
이걸 $k$번 반복하면 된다.
void solve() {
int k;
cin >> k;
string s;
cin >> s;
int n = sz(s);
auto get_sub = [&](int l, int r) -> string {
int len = r - l + 1;
if (len <= 0) return "";
return s.substr(l, len);
};
while (k--) {
stack<int> t;
vector<array<int, 3>> change;
vi a(n);
for (int i = 0, o = 0; i < n; i++) {
if (s[i] == '(')o++;
else o--;
a[i] = o;
}
for (int i = 0; i < n; i++) {
if (s[i] == '(') t.push(i);
else {
int l = t.top(), r = i;
change.pb({l, r, a[r]});
t.pop();
}
}
if (!sz(change)) break;
sort(all(change), [&](auto &a, auto &b) {
return a[1] - a[0] > b[1] - b[0];
});
int l = change[0][0], r = change[0][1];
string news = get_sub(0, l - 1) + "()" + get_sub(l + 1, r - 1) + get_sub(r + 1, n - 1);
s = news;
}
ll ans = 0;
for (int i = 0, o = 0; i < n; i++) {
if (s[i] == '(')o++;
else o--;
if (s[i] == ')') {
ans += o;
}
}
cout << ans << endl;
}
Comments