Codeforces Round 863 (Div. 3)
색칠잼
오랜만에 Div3 순회공연을 해보았다. F, G 같은 경우에 풀긴 풀었는데 그다지 쉽게 푼건 아닌것같다.
에디토리얼을 다시보니 $G$는 얼추 해설자가 의도한대로 동일하게 푼 것 같다.
가끔가다 코드포스 문제도 풀어야겠다.
A. Insert Digit (800)
A. Insert Digit
$d$ 보다 작은 수가 나오기 바로 직전에 끼워넣어주면 된다.
그런 수가 없다면 제일 뒤에 붙이면 된다.
B. Conveyor Belts (1000)
B. Conveyor Belts
이런 인덱스 다루는거가 갑자기 헷갈렸는데, 결국 컨베이어벨트의 레벨을 따졌을 때 그 레벨차이만큼이 정답이다.
어떻게든 컨베이어 벨트를 변경하는 움직임만 하면서 $(x_1,y_1) \to (x_2,y_2)$ 로 갈 수 있다.
C. Restore the Array (1100)
C. Restore the Array
$b$에서 $b_i$와 $b_{i+1}$ 를 봤을 때, $a_{i+1}$를 둘 중 작은것으로 설정해주면 된다.
그리고 $a_1$과 $a_n$은 $b_1$과 $b_{n-1}$ 것을 그대로 옮겨주면 충분하다.
D. Umka and a Long Flight (1600)
D. Umka and a Long Flight
그리디 수학문제인 줄 알았는데, 그런거없고 그냥 재귀함수 구현해서 풀면 된다.
$wlog.$ $W>H$ 처럼 계속 유지해줄 수 있는데, 이제 $H \times H$ 인 정사각형을 빼줄 차례가 된다.
근데 가로 부분에서 $[1,H]$ 쪽이나 $[W-H+1,W]$ 쪽 둘 다 현재 $x$ 가 포함이 되어있어서 제거해줄 수 없는 상태라면 정답은 no이고, 그렇지 않다면 yes이다.
int fib[50];
void pre_calc() {
fib[0] = fib[1] = 1;
for (int i = 2; i <= 49; i++) fib[i] = fib[i - 1] + fib[i - 2];
}
void solve() {
int n, x, y;
cin >> n >> y >> x;
bool find = 0;
function<void(int, int, int, int)> fn = [&](int Y, int X, int y, int x) -> void {
if (Y > X) {
swap(Y, X), swap(y, x);
}
if (Y == 1 && X == 1) {
find = 1;
return;
}
if (x >= X + 1 - Y && x <= Y) return;
x = min(x, X + 1 - x);
fn(X - Y, Y, x, y);
};
fn(fib[n], fib[n + 1], y, x);
if (!find) cout << "no\n";
else cout << "yes\n";
}
E. Living Sequence (1500)
E. Living Sequence
$[1, 10^k)$ 까지 $4$가 들어가지 않는 숫자의 개수를 $dp[i]$ 라고 한다면,
$dp[0]=1$, $dp[i]=9dp[i-1]$ 이다.
이제 역추적을 해줄 수 있다.
현재 $10^i$번 째 자리를 보고있다면, 남은 $k$가 $dp[i]$로 나눈 몫이 몇인지 본다.
이것을 $q$ 라 할 때, $4$이상이라면 정답엔 $q+1$ 을 한 것을 붙여주고, $k$에선 그대로 $q \cdot dp[i]$를 빼준다. $4$미만이라면 그냥 동일하게 $q$를 붙여주면 된다.
왜냐면 $4$로 시작하는 숫자는 세지긴 해야하지만 $4$가 정답에붙을 수 없기 때문에 그만큼 skip해줘야 하기 때문이다.
int dp[20];
void solve() {
dp[0] = 1;
dp[1] = 9;
for (int i = 2; i <= 19; i++) dp[i] = dp[i - 1] * 9;
int k;
cin >> k;
//k--;
string ans;
function<void(int i)> fn = [&](int i) -> void {
if (i == -1) return;
int q = k / dp[i];
int add = q;
if (q >= 4) {
add++;
}
k -= q * dp[i];
if (q == 0 && !sz(ans));
else ans += char(add + '0');
fn(i - 1);
};
fn(15);
cout << ans << endl;
}
F. Is It Flower? (2100)
F. Is It Flower?
문제를 읽다가 아니 슈바 Div 3에 선인장이나와? 라는 생각이 들었지만 선인장 문제처럼 생긴 그래프 문제이다.
하지만 여러 조건을 따져줘야해서 꼼꼼하게 풀어야 하는 문제이다.
나는 overkill해서 단절점들을 구해서 풀었다.
각 정점에서의 degree로 판단하는 것이 강력한 조건이 된다.
중앙에 단절점에 포함되어있는 것들은 항상 $degree=4$ 여야 하고, 다른 것들은 $degree=2$ 여야 한다.
그리고 항상 $n=k^2$ 여야하기 때문에 단절점의 개수를 $k$라고 두고 풀자.
코드는 더럽지만 그냥 첨부한다.
void solve() {
int n, m;
cin >> n >> m;
vvi edges(n + 1);
for (int i = 0, u, v; i < m; i++) cin >> u >> v, edges[u].pb(v), edges[v].pb(u);
vi order(n + 1, -1);
int dfsn = 0;
vi articulation_points, is_points(n + 1);
function<int(int, int, int)> dfs = [&](int cur, int isRoot, int p) -> int {
order[cur] = ++dfsn;
int ret = order[cur];
int child = 0;
for (int to: edges[cur]) {
if (to == p) continue;
if (order[to] == -1) {
int lowest = dfs(to, false, cur);
if (!isRoot && lowest >= order[cur]) {
articulation_points.pb(cur);
}
ret = min(ret, lowest);
child++;
} else {
ret = min(ret, order[to]);
}
}
if (isRoot && child >= 2) articulation_points.pb(cur);
return ret;
};
dfs(1, true, -1);
uniq(articulation_points);
for (int i = 2; i <= n; i++) {
if (order[i] == -1) {
cout << "no\n";
return;
}
}
int k = sz(articulation_points);
if (k < 3) {
cout << "no\n";
return;
}
ll tot_n = 1ll * k * k;
if (tot_n != n) {
cout << "no\n";
return;
}
for (int i: articulation_points) is_points[i] = 1;
vi vis(n + 1);
bool fail = 0;
function<int(int)> dfs2 = [&](int cur) -> int {
int size = 1;
vis[cur] = 1;
for (int to: edges[cur]) {
if (!vis[to] && !is_points[to]) {
size += dfs2(to);
}
}
if (is_points[cur] && size != k) fail = 1;
if (!is_points[cur] && sz(edges[cur]) != 2) fail = 1;
return size;
};
for (int i: articulation_points) dfs2(i);
if (fail) {
cout << "no\n";
return;
}
fill(all(vis), 0);
int cnt = 0;
function<void(int)> dfs3 = [&](int cur) -> void {
vis[cur] = 1;
cnt++;
int connected = 0;
for (int to: edges[cur]) {
if (is_points[to] && !vis[to]) {
dfs3(to);
}
if (is_points[to]) connected++;
}
if (connected != 2) fail = 1;
};
dfs3(articulation_points[0]);
if (cnt != k || fail) {
cout << "no\n";
return;
}
cout << "yes\n";
}
G1. Vlad and the Nice Paths (easy version) (2100)
G1. Vlad and the Nice Paths (easy version)
G2. Vlad and the Nice Paths (hard version) (2200)
G2. Vlad and the Nice Paths (hard version)
G2 기준으로 $n, k \le 5,000$ 이기 때문에 $O(n^2)$이 아니면 가망이 없다.
$dp[i]=$ $i$까지 봤을 때 (길이(2k 일 때 2 같이), 경우의 수)
라고 하자.
$dp[i]$를 채우기 위해선 $dp[i-1]$ 에 추가적으로 $i$ 위치의 블록을 써서 경로를 만들어야 한다.
$i \to 1$ 로 가면서 $c[i]$ 와 같은 숫자들을 세면서 지금까지 나온 $c[i]$ 와 같은 블록의 개수를 $x$ 라고 할 때, 지금까지 본 구간에서 항상 좌우 두 개의 블록을 포함하는 경우의 수는 $_{x-2}C_{k-2}$ 이다.
$k=1$ 일 때는 항상 정답이 1이다. 따로 처리하자.
이제 이걸 지금까지 본 구간 바로 왼쪽의 $dp$ 값을 이용해서 일단 $dp$ 값의 길이는 $+1$ 해주고, 경우의 수는 곱해서 모아보자.
거기서 또 한번 길이가 가장 긴 것들만 추려서 그것들의 경우의 수들의 합만 $dp[i]$ 에 업데이트 해주면 된다.
그러면 시간복잡도 $O(n^2)$ 에 풀 수 있다.
int bino[5001][5001];
void pre_calc() {
for (int i = 0; i <= 5000; i++)
for (int j = 0; j <= i; j++) bino[i][j] = !i || !j ? 1 : md(bino[i - 1][j] + bino[i - 1][j - 1]);
}
void solve() {
int n, k;
cin >> n >> k;
vi c(n + 1), c_values;
fv1(c);
for (int i = 1; i <= n; i++) c_values.pb(c[i]);
uniq(c_values);
int C = sz(c_values);
c[0] = -1;
for (int i = 1; i <= n; i++) c[i] = lbi(c_values, c[i]);
vector<pi> dp(n + 1);
dp[0] = {0, 1};
for (int i = 1; i <= n; i++) {
if (k == 1) {
dp[i] = {dp[i - 1].fi + 1, dp[i - 1].se};
continue;
}
int color_cnt = 0;
vector<pi> cand;
for (int j = i; j >= 1; j--) {
if (c[i] == c[j]) {
color_cnt++;
if (color_cnt >= k) {
int nxt_m = (dp[j - 1].fi + 1);
int nxt_v = md(dp[j - 1].se * bino[color_cnt - 2][k - 2]);
pi nxt = {nxt_m, nxt_v};
cand.pb(nxt);
}
}
}
int max_k_cnt = dp[i - 1].fi;
int max_v = 0;
for (auto &[k_cnt, v]: cand) max_k_cnt = max(max_k_cnt, k_cnt);
for (auto &[k_cnt, v]: cand) if (k_cnt == max_k_cnt) max_v = md(max_v + v);
if (dp[i - 1].fi == max_k_cnt) max_v = md(max_v + dp[i - 1].se);
dp[i] = {max_k_cnt, max_v};
}
cout << dp[n].se << endl;
}
Comments