Codeforces Round 866 (Div. 2)
A. Yura’s New Name (800)
$N=1$ 일 땐 직접 처리를 해주자.
__ 의 개수를 세주자.
그리고 양 옆을 잘 처리하면 된다.
B. JoJo’s Incredible Adventures (1100)
B. JoJo’s Incredible Adventures
모두 다 0이나 1로 되어있는 경우를 따로 처리한다.
이후에는 1이 가장 길게 이어진 구간을 본다.
이 때, 주의할 점은 회전시켜서도 이어져있다면 이어진것으로 봐야하기 때문에
s = s + s[0, sz(s) - 1] 처럼 문자열을 변환시키고 해주는 것이 편리하다.
가장 긴 길이의 구간이 $L$이라면 정답은 $\left\lceil \dfrac{L+1}{2} \right\rceil \cdot \left\lceil \dfrac{L+2}{2} \right\rceil$ 이다.
int sum(int i) {
return ((i + 1) / 2) * ((i + 2) / 2);
}
void solve() {
string s;
cin >> s;
int n = sz(s);
if (cntt(s, '0') == n) {
cout << 0 << endl;
return;
}
if (cntt(s, '1') == n) {
cout << n * n << endl;
return;
}
s += s.substr(0, n - 1);
n = sz(s);
int ans = 0;
for (int i = 0; i < n;) {
if (s[i] == '1') {
int j = i;
while (j < n && s[j] == '1')j++;
int len = j - i;
ans = max(ans, sum(len));
i = j;
} else {
i++;
}
}
cout << ans << endl;
}
C. Constructive Problem (1300)
$\text{MEX}(a)=k$ 라면 $a$에 있는 $k+1$ 들을 모두 $k$ 로 바꿔줘야만 가능하다.
$k+1 \not\in a$ 라면 항상 가능하다.
그러면 최대한 그리디하게 $k+1$이 나오는 가장 처음과 가장 끝 부분의 연속된 값들을 모두 $k$로 바꿔줘야 한다.
바꿔준 후에 $\text{MEX}(a)$를 다시 구해서 이것이 $k+1$ 가 나온다면 가능하고 그렇지 않다면 불가능하다.
D. The Butcher (1900)
관찰해야하는 것은 가장 처음에 자를 때 세로로 잘랐다면 $\text{Max}~h_i$ 는 처음 직사각형의 높이이고 처음에 가로로 잘랐다면 $\text{Max} \ w_i$ 는 처음 직사각형의 넓이라는 것이다.
$A=\displaystyle \sum h_i \cdot w_i$ 라고 하면 처음에 높이나 넓이를 결정했다면 나머지 넓이나 높이도 결정할 수 있다.
$w'=\dfrac{A}{\text{Max} \ h_i}$ 처럼 이다.
이제 두 가지 경우가 가능한지를 판단해야한다.
$wlog.$ 처음에 세로로 잘랐다고 한다면
$\text{Max} \ h_i$ 를 가진 직사각형들을 모두 제거한다. 그럼 그 직사각형들의 넓이의 합을 원래 넓이에서 뺀 것이 나머지 남은 부분이다. 이를 $w'$ 라 한다.
이제 무조건 가로로 잘라야 하므로 남은 것들 중 넓이가 $w'$ 인 것들을 모두 제거하면 그 다음은 세로로 잘라야 한다.
이렇게 모두 직사각형이 제거될 때 까지 모순이 없다면 처음에 세로나 가로로 자르는 것이 valid하다는 것을 판별할 수 있고, 이는 std::set 을 이용해 구현할 수 있다.
따라서 시간복잡도는 $O(n \log n)$으로 해결할 수 있다.
void solve() {
int n;
cin >> n;
vector<pi> r(n);
int area_sum = 0;
int hmax = 0, wmax = 0;
for (auto &[h, w]: r) {
cin >> h >> w;
area_sum += h * w;
hmax = max(h, hmax);
wmax = max(w, wmax);
}
debug(area_sum, hmax, wmax);
if (n == 1) {
cout << 1 << endl;
cout << r[0].fi << ' ' << r[0].se << endl;
return;
}
vector<pi> ans;
for (int it = 0; it < 2; it++) {
if (area_sum % hmax == 0) {
int w = area_sum / hmax;
int can = 1;
int cur_h = hmax, cur_w = w, parity = 0;
multiset<pi, greater<>> hw, wh;
for (int i = 0; i < n; i++) hw.insert({r[i].fi, r[i].se}), wh.insert({r[i].se, r[i].fi});
while (sz(hw)) {
int nxt_val = parity == 0 ? cur_w : cur_h;
// h = cur_h 인 것들을 제거한다.
if (parity == 0) {
if (!sz(hw) || hw.begin()->fi != cur_h) {
can = 0;
break;
}
while (sz(hw) && hw.begin()->fi == cur_h) {
pi cur = *hw.begin();
wh.erase({cur.se, cur.fi});
hw.erase(hw.begin());
nxt_val -= cur.se;
}
cur_w = nxt_val;
} else {
if (!sz(wh) || wh.begin()->fi != cur_w) {
can = 0;
break;
}
while (sz(wh) && wh.begin()->fi == cur_w) {
pi cur = *wh.begin();
hw.erase({cur.se, cur.fi});
wh.erase(wh.begin());
nxt_val -= cur.se;
}
cur_h = nxt_val;
}
parity ^= 1;
}
if (can && !sz(hw)) {
if (it == 0)
ans.pb({hmax, w});
else
ans.pb({w, hmax});
}
}
for (auto &[h, w]: r) swap(h, w);
swap(hmax, wmax);
}
cout << sz(ans) << endl;
for (auto &[h, w]: ans) cout << h << ' ' << w << endl;
}
E. The Fox and the Complete Tree Traversal (2400)
E. The Fox and the Complete Tree Traversal
Comments