Educational Codeforces Round 147 (Rated for Div. 2)
Educational Codeforces Round 147 (Rated for Div. 2)
A. Matching (800)Permalink
처음이 으로 시작하면 답은 이다.
처음이 로 시작하면 그건 를 곱해주고,
나머지 들은 모두 을 곱해준다.
B. Sort the Subarray (1100)Permalink
투포인터로 좌우의 끝부터 이면 계속 좁혀주고 서로 다른 첫 구간을 라 하자.
이제 그 구간을 정렬할 것이므로 가 구간에서 가장 작다면 왼쪽으로 확장, 가 구간에서 가장 크다면 오른쪽으로 확장할 수 있다.
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)Permalink
길이 의 문자들을 모두 지우는 개수는 로 DP로 전처리해둘 수 있다.
개의 문자들을 모두 순회하며, 그 문자와 다른 것들을 하나의 블록으로 본다.
그 블록의 길이 들 중 가장 가 큰 것이 그 문자만 남기는데 필요한 최소 횟수이다.
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)Permalink
Observation 1
구간은 모두 떨어져있다.
Observation 2
길이 이상의 구간은 스킵할 필요가 없다. 구간이 최소 떨어져있기 때문에 shift를 눌렀다 떼는 동작을 아끼는거랑 다음 구간으로 넘어가는 최소 번의 이동횟수와 같기때문이다.
Observation 3
길이 의 구간은 이미 지나왔다면 모두 동일하게 생각해줄 수 있다.
이미 지나온 구간에서 어떤 길이 의 구간을 먼저지났냐 늦게지났냐는 정답에 영향을 미치지 않는다.
SolutionPermalink
나는 이분탐색을 썼지만 에 구할 수 있다.
현재 지나온 구간에서 길이 이상인 구간의 총 길이 합을 라고 하고, 길이 인 구간의 총 길이 합을 라 한다.
1- 라면 아직 모두 사용해도 채우지 못한다는 것이므로 넘긴다.
2-
긴 구간만으로 를 채울 수 없지만 구간들 몇개를 써서 채울 수 있다는 것을 의미한다.
이때의 정답은 (써야하는 길이 구간 수 + 지금까지 지나온 길이 이상 구간수) + 현재 구간의 가장 끝의 위치 이다.
왜 현재 구간의 가장 끝 위치인지 길이 의 구간을 최소로 골라 가 될 때 까지만 사용할 것이기 때문에 끝나는 구간은 현재 구간의 끝이다.
3-
이땐 긴 구간들만 으로 개를 채울 수 있으므로
가 정답이 된다.
2,3번 케이스에서 가장 작은 값을 정답으로 채택하면 된다.
E. Rearrange Brackets (2100)Permalink
올바른 괄호 문자열이 주어진다.
우선 문제에서 얘기하는 Minimum cost를 만드는 그리디한 방법은 뒤에서부터 () 인 괄호를 제거해나가는 것이다.
이를 다시 해석하면 ((())) 같은 친구는 2+1 이 소모되므로 어떤 ) 를 기준으로 자신을 감싸고 있는 괄호 쌍의 개수를 모두 더한것이 최소 비용이다.
따라서 우리의 목적은 최대한 겹쳐진 괄호를 제거하는 것에 있다는 걸로 재정의된다.
이기 때문에 매 단계 직접 문자열을 구성해줄 수 있다.
어떤 괄호가 있고 인덱스가 이라면 이 괄호를 없앰으로 얻을 수 있는 이득은 이다.
따라서 항상 가장 바깥쪽에 있는 괄호를 재배열하는게 최적이다. 그리고 가장 바깥쪽의 괄호는 올바른 괄호 문자열에 항상 존재한다.
((())(())) 처럼 되어있다면 가장 바깥의 괄호를 앞이나 뒤로 붙여 ()(())(()) 처럼 만들어줄 수 있다.
따라서 괄호 중 이 가장 큰 것중 하나를 다른 하나 옆으로 붙여주는것이 항상 최적이다.
이걸 번 반복하면 된다.
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