Educational Codeforces Round 149 (Rated for Div. 2)
Educational Codeforces Round 149 (Rated for Div. 2)
대체적으로 쉬웠지만 E를 입력을 잘못봐서 못풀었다는게 아쉽다.
A. Grasshopper on a Line
$k \nmid x$ 라면 $1$번으로 $x$로 가면 되고, $k \mid x$라면 $x-1$ 로 먼저 이동한다음에 $k \ge 2$ 이므로 $1$ 이동하면 된다.
B. Comparison String
대회중에 문제푸는데 출력이 이상하긴 했는데 그냥 3분만에 풀긴했더니 막 공지가 올라오며 뭐 예제 잘못됐다고 다시 채점한다고 난리부르스였다.
그냥 > 나 < 중 연속된 길이중 가장 큰 것이 정답이다.
C. Best Binary String
? 이 없다고 할 때 뒤집어야 하는 횟수는 오른쪽부터 봤을 때 첫 번째 1 이나오기 전까지 0 으로 이어진 구간의 개수이다.
그리디하게 ? 옆에 하나라도 1 이 있다면 그냥 1 로 바꿔줘서 1 로 된 구간을 merge 시켜주는게 최적이다.
따라서 s[i-1] 이나 s[i+1] 이 1 인지를 검사하면 되는데,
문제는 ? 를 채울때도 s[i-1] 이 ? 에서 1 이 될 수 있기 때문에 그걸 적절히 처리해줘야 한다.
이걸 처리 안해줘서 두 번 틀렸다.
D. Bracket Coloring
정답은 최대 2 이다. 누적 balance 값이 0 이 되는 부분들을 기준으로 구간으로 쪼갰을 때, 특정 구간은 항상 그 내부의 수들이 음수이고 특정 구간은 양수이기 때문이다.
따라서 음수인 구간과 양수인 구간을 각각 모두 합쳐주면 최대 $k \le 2$ 이다.
귀찮아서 세그먼트 트리로 풀었다.
E. Playoff Fixing
1시간 동안 고민해서 코드를 올바르게 짰지만 입력을 잘못봐서 $a_i$ 번째 팀이 $i$ 번째 시드를 받는게 아닌 $i$번째 팀이 $a_i$ 시드를 받는걸로 착각했다.
대회 끝나고 고쳤더니 바로 맞았다.
$2^k$ 명의 사람이 있을 때 $2^{k-1}$ 명의 $[2^{k-1}+1, 2^k]$ 팀들은 항상 바로 붙어있으면 안된다는 아이디어부터 풀어나가기 시작했다.
그렇다면 $[2^{k-2}+1, 2^{k+1}]$ 의 사람들은 $4$ 칸 안에 같이 있으면 안되고 등등이다.
전역적으로 $n$ 길이의 가능한 자리를 계속 관리한다. 코드의 available 변수
현재 보고있는 구간이 $[2^{x-1}+1, 2^{x}]$ 이라고 하자.
이 구간에 있는 사람들은 첫 칸부터 봤을 때 한 사람이 $2^{k-x}$ 칸을 차지해야한다.
$x=k-1$ 를 대입해보면 가장 먼저 떨어지는 사람들이 $2$칸씩 차지한다는 것을 생각하면 올바르다.
이 글에서 차지한다는 것은, 한 팀당 그 만큼 구간을 가지고 동일하게 떨어져야 할 다른 팀은 각 구간당 하나씩만 존재해야 하는 것을 의미한다.
어떤 $x$에서 시드가 고정된 사람들과 $-1$ 인 사람들을 보자.
그럼 길이 $\dfrac{n}{2^{k-x}}$ 짜리 cnt 라는 배열을 만들고 고정된 사람들이 각 구간에 몇명이 들어있는지 확인한다.
$n=2^k$
만약 어떤 곳에 $2$명 이상이 들어있다면 정답은 없다. 모두 $1$명이나 $0$명이 있어야 한다.
우린 그럼 $0$명인 곳에 시드가 고정되지 않은 사람들을 넣어줘야 한다.
이 사람들의 명수를 $f$ 라고 한다면 정답에 일단 $f!$ 를 곱해준다.
이후에 $\dfrac{n}{2^{k-x}}$ 개의 구간을 각각 검사하며 각 구간마다 available 변수를 이용해 몇 자리가 남았는지 파악한다.
여기서 한 자리도 남지 않았다면 정답은 없다.
어떤 구간에 $m$ 개의 자리가 남았을 때, 정답에 $m$ 을 곱해주면 된다.
그럼 $m$개의 자리 중 시드가 없는 사람을 어디에 넣을 수 있을까?
결론적으로 어디에 넣어도 정답에 영향을 끼치지 않는다이다.
왜냐면 $x$가 감소하는 순으로 순회하고 있기 때문에 그 다음 $x$에서 구간의 길이가 두 배 넓어지며, 이 구간과 옆 구간 하나에 남은 사람의 수만 중요하지 어디에 차있는지가 중요하지 않게 되기 때문이다.
이런식으로 $x \coloneqq k-1 \to 0$ 까지 순회하며 정답을 구할 수 있다.
시간복잡도 $O(k \cdot 2^k)$
const int MAX = 1'000'000;
const ll mod = 998244353;
inline ll md(ll x) { return md(mod, x); }
vector<ll> fac(MAX + 1, 1LL);
vi two(21, 1);
void pre_calc() {
for (int i = 2; i <= MAX; i++) fac[i] = md(fac[i - 1] * i);
for (int i = 1; i <= 20; i++) two[i] = md(two[i - 1] * 2);
}
void solve() {
pre_calc();
int k;
cin >> k;
int n = 1 << k;
vi _a(n);
for (int i = 0; i < n; i++) {
cin >> _a[i];
//a[i] = -1;
}
for (int &i: _a) if (i != -1) i--;
vi a(n, -1);
for (int i = 0; i < n; i++) if (_a[i] != -1) a[_a[i]] = i;
int ans = 1;
vi available(n, 1);
for (int i: a) if (i != -1) available[i] = 0;
for (int x = k - 1; x >= 0; x--) {
int people = two[x], fixed = 0;
vi indice;
for (int j = two[x]; j < two[x + 1]; j++) if (a[j] != -1) fixed++, indice.pb(a[j]);
int free = people - fixed;
int d = two[k - x];
ans = md(ans * fac[free]);
vi cnt(n / d);
for (int x: indice) cnt[x / d]++;
for (int i: cnt) {
if (i > 1) {
cout << 0;
return;
}
}
int yes = 0;
for (int x = 0, y = 0; x < n; x += d, y++) {
if (cnt[y] == 1) continue;
yes++;
int l = x, r = x + d - 1, ac = 0, idx = -1;
for (int j = l; j <= r; j++) {
if (available[j]) {
idx = j;
ac++;
}
}
if (!ac) {
cout << 0;
return;
}
ans = md(ans * ac);
available[idx] = 0;
}
if (yes != free) {
cout << 0;
return;
}
}
cout << ans;
}
F. Editorial for Two
대회중에 보긴 했는데 세그먼트 트리로 왼쪽 오른쪽을 잘 스위핑하면 될 것 같긴 했는데,
다른사람 코드를 보니 binary search + priority queue로 풀어서 에디토리얼이 올라오면 한 번 풀어볼 예정이다.
Comments