Educational Codeforces Round 126 (Div. 2)

리뷰

A는 평소처럼 살짝 늦지만 틀리지 않고 풀었다.

B에서 말렸다. 일단, DP가 정해일 리는 없는데 DP 밖에 생각이 안 났다. WA 1 한 번 받고서 시간 지체하다가 제출했다. 에듀라서 다행이다.

C는 계산이랑 케이스 나누는게 너무 고단해서 '망했다...' 싶었는데, 다들 힘들어하더라. $ \max_{1\le i\le n}h_i+1$로 만드는 경우를 빼먹고 있다가 극적으로 떠올리며 AC...

D는 B보다도 아이디어가 쉬웠다. 일단, 문제에서 주어진 연산을 무엇을 사용해서 풀 수 있는지를 알고 있기 때문이다. 하지만 나는 그런 문제를 푼 적이 없어서 검색을 해서 코드를 하나씩 맞춰나갔다. 7초 남짓 남았을 때 $a_1,\ldots, a_{k-1}$에만 적용하는 방법을 그리디로 진행한 방법이랑 동일하게 작성해서 제출해서 틀렸고, 끝난 뒤 5분 뒤에 틀렸음을 파악하고 6분뒤에 고친 코드를 제출하여 그대로 맞았다. 내게 6분만 더 있었더라면..!

Array Balancing

매 $a_i,b_i$에 대해 $\text{swap}$할 것이냐 말 것이냐를 결정해주면 된다.

코드

#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>;
using ll = long long; using ld = long double;
#define _(x) const x&
#define REP(i,a,b) for (auto i = (a); i <= (b); ++i)
#define ZIP(x) (x).erase(unique((x).begin(),(x).end()),(x).end())
#define MP make_pair
#define mup(x,y) x = min(x,y)
#define Mup(x,y) x = max(x,y)
#define size(x) int((x).size())

const int N = 28;
int n, a[N], b[N];

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t; cin >> t;
    REP(_,1,t) {
        cin >> n;
        REP(i,1,n) cin >> a[i];
        REP(i,1,n) cin >> b[i];
        ll answer = 0;
        REP(i,2,n) {
            if (abs(a[i]-a[i-1])+abs(b[i]-b[i-1]) < abs(b[i]-a[i-1])+abs(a[i]-b[i-1]))
                 answer += abs(a[i]-a[i-1])+abs(b[i]-b[i-1]);
            else answer += abs(b[i]-a[i-1])+abs(a[i]-b[i-1]);
        }
        cout << answer << '\n';
    }
}

Getting Zero

$2^x||(a_i+y)$에서 $x=0,1,\ldots , 15$로 조절하면서 $y$를 구하면 된다.

sedev57님의 코드가 제일 깔끔하고 정확하다고 생각한다.

내 코드

#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>;
using ll = long long; using ld = long double;
#define _(x) const x&
#define REP(i,a,b) for (auto i = (a); i <= (b); ++i)
#define ZIP(x) (x).erase(unique((x).begin(),(x).end()),(x).end())
#define MP make_pair
#define mup(x,y) x = min(x,y)
#define Mup(x,y) x = max(x,y)
#define size(x) int((x).size())

const int N = 40000;
int n, a[N], dp[N];
ll answer = 0;

int main() {
    cin.tie(0)->sync_with_stdio(0);
    fill(dp+1,dp+32768,1e9);
    for (int i = 32768; i > 0; --i)
        dp[i] = 15-__builtin_ctz(i);
    for (int i = 32767; i >= 0; --i) {
        mup(dp[i],dp[2*i%32768]+1);
        mup(dp[i],dp[i+1]+1);
    }
    cin >> n;
    REP(i,1,n) cin >> a[i], cout << dp[a[i]] << ' ';
}

Water the Trees

모든 원소를 $\max_{1\le i\le n} h_i$으로 맞추는 방법이 있고, $\max_{1\le i\le n} h_i+1$로 맞추는 방법이 있다.

하지만, $\max_{1\le i\le n} h_i+2$부터는 첫 번째 방법보다 비효율적임이 자명하다. 따라서 2가지 케이스에 대해 구하면 된다.

 

그 2가지 케이스는 각각 다음의 논리로 따져주면 된다:

홀수인 $h_i$에 대해서는 반드시 $+1$을 하는 시행이 존재할 것이고, 어떤 경우에서든 $+1$을 2번 하는 시행은 결국 $+2$로 전환할 수 있으므로...

우선 홀수인 $h_i$의 개수를 구해야 한다. 이는 필요한 $+1$ 시행의 '최소' 횟수가 된다.

 

필요한 $+1$ 시행의 '최소' 횟수를 $o$, 필요한 $+2$의 '최대' 횟수를 $e$라고 하자.

$(o,e)$ 구성으로 더하는 경우는 $(o+2k,e-k)$ 구성으로도 더할 수 있을 것이다. 그리고 그렇게 모든 구성을 고려할 수 있을 것이다. (단, $0\le k\le e$)

그 중에서 $o$와 $e$의 차이를 적당히 작게한 것이 답으로 고려되어야 시간안에 돌아갈 것이다. 필자는 그런 경우를 대소관계 2가지로 나누어 계산했다.

 

$\text{i. }o+2k>e-k:$

$....\iff 3k>e-o$

$....\iff k>\frac{e-o}3$

$....\iff k\ge\left \lfloor \frac{e-o}3\right\rfloor +1$

$....\therefore $차이를 최소로 만드는 $k=\left \lfloor \frac{e-o}3\right\rfloor +1.$

$....$홀수날에 끝나므로 소요하는 전체 기간은 $(o+2k)+(o+2k-1)$일이다.

 

$\text{ii. }o+2k\le e-k:$

$....\iff 3k\le e-o$

$....\iff k\le\frac{e-o}3$

$....\iff k\le \left \lfloor \frac{e-o}3 \right \rfloor$

$....\therefore $차이를 최소로 만드는 $k=\left \lfloor \frac{e-o}3\right\rfloor.$

$....$짝수날에 끝나므로 소요하는 전체 기간은 $(e-k)+(e-k)$일이다.

 

 

코드

#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>;
using ll = long long; using ld = long double;
#define _(x) const x&
#define REP(i,a,b) for (auto i = (a); i <= (b); ++i)
#define ZIP(x) (x).erase(unique((x).begin(),(x).end()),(x).end())
#define MP make_pair
#define mup(x,y) x = min(x,y)
#define Mup(x,y) x = max(x,y)
#define size(x) int((x).size())

constexpr ll floor(ll p, ll q) {
    return p/q-((p^q) < 0 and p%q);
}

constexpr ll ceil(ll p, ll q) {
    return p/q+((p^q) > 0 and p%q);
}

const int N = 3e5+3;
int n, h[N];

int main() {
    cin.tie(0)->sync_with_stdio(0);
    int t; cin >> t;
    REP(_,1,t) {
        cin >> n;
        REP(i,1,n) cin >> h[i];
        int toMake = *max_element(h+1,h+n+1);
        ll odd = 0, even = 0, ans = 1e18, k;
        REP(i,1,n) {
            if ((toMake-h[i])%2) ++odd;
            even += (toMake-h[i])/2;
        }
        // 1
        k = clamp(floor(even-odd,3)+1,0LL,even);
        if (0 <= even-k and even-k < odd+2*k)
            mup(ans,2*(odd+2*k)-1);
        // 2
        k = clamp(floor(even-odd,3),0LL,even);
        if (0 <= odd+2*k and odd+2*k <= even-k)
            mup(ans,2*(even-k));
        
        odd = 0, even = 0;
        REP(i,1,n) {
            if ((toMake+1-h[i])%2) ++odd;
            even += (toMake+1-h[i])/2;
        }
        // 1
        k = clamp(floor(even-odd,3)+1,0LL,even);
        if (0 <= even-k and even-k < odd+2*k)
            mup(ans,2*(odd+2*k)-1);
        // 2
        k = clamp(floor(even-odd,3),0LL,even);
        if (0 <= odd+2*k and odd+2*k <= even-k)
            mup(ans,2*(even-k));
        
        cout << ans << '\n';
    }
}

Progressions Covering

만약에 전부 같은 값을 modify한다고 생각해보자. 그리디하게 앞에서부터 진행하면서 각 $a_i$에 대해 $\le 0$가 될 때까지 감소시키면 될 것이다.

그런데 문제의 경우는 $1,2,\ldots,k$로 modify하고 있다. 따라서 앞에서부터 $a_i$를 감소시킬때 $a_i$ 기준으로 생각하면 $1$씩 감소하지만, $a_k(k<i)$를 기준으로 생각하면 $i-k+1$씩 감소시킬 수 있기 때문에 성립하지 않는 방법이 된다.

그렇다면, 배열의 오른쪽부터 시작한다면? 성립한다.

 

그래서 Lazy Segtree로 우측으로 진행하면서 빼주면 된다.

 

그런데! $a_1,\ldots,a_{k-1}$는 고려되지 못한다. 하지만 부분배열을 잡아서만 감소시킬 수 있다는 조건 때문에 더 이상 진행할 수 없다.

따라서 $a_1,\ldots,a_{k}$에 대한 감소가 가장 최적이므로 이 감소만을 이용한다. 이 경우는 그리디 접근이랑 달라서, 그냥 앞에서부터 횟수를 늘려주는 식으로 세주면 된다.

코드

동일하지 않은 값을 modify하는 유형의 lazy seg 문제를 풀어본 적이 없어서,

대표 유형이라는 '하늘에서 떨어지는 1,2,...,k-1개의 별'(?) 문제에 사용된 Rebro님의 코드를 검색했다.

#include <bits/stdc++.h>
using namespace std; using ii = pair<int,int>;
using ll = long long; using ld = long double;
#define _(x) const x&
#define REP(i,a,b) for (auto i = (a); i <= (b); ++i)
#define ZIP(x) (x).erase(unique((x).begin(),(x).end()),(x).end())
#define MP make_pair
#define mup(x,y) x = min(x,y)
#define Mup(x,y) x = max(x,y)
#define size(x) int((x).size())

int N, k;

ll A[400001];
ll tr[1600001];
ll lazy[1600001];
void update_lazy(int x, int s, int e); 
ll sum(int x, int s, int e, int l, int r) { 
    update_lazy(x, s, e); 
    if (s > r || e < l) return 0; 
    else if (s >= l && e <= r) return tr[x]; 
    else return sum(x * 2, s, (s + e) / 2, l, r) + sum(x * 2 + 1, (s + e) / 2 + 1, e, l, r); 
} 
void update_range(int x, int s, int e, int l, int r, ll val) {
    update_lazy(x, s, e);
    if (s > r || e < l) return;
    if (s >= l && e <= r) {
        tr[x] += (e - s + 1)*val;
        if (s != e) { lazy[x * 2]+= val; lazy[x * 2 + 1]+= val; }
        return;
    }
    update_range(x * 2, s, (s + e) / 2, l, r, val);
    update_range(x * 2 + 1, (s + e) / 2 + 1, e, l, r, val);
    tr[x] = tr[x * 2] + tr[x * 2 + 1];
}
void update_lazy(int x, int s, int e) {
    if (lazy[x] != 0) {
        tr[x] += (e - s + 1)*lazy[x];
        if (s != e) { lazy[x * 2] += lazy[x]; lazy[x * 2 + 1] += lazy[x]; }
        lazy[x] = 0;
    }
}

int main() {
    cin.tie(0)->sync_with_stdio(0);
    cin >> N >> k;
    for (int i = 1; i <= N; i++) cin >> A[i];
    for (int i = 1; i <= N; i++) {
        update_range(1, 1, N, i, i, A[i] - A[i-1]);
    }
    ll answer = 0;
    for (int i = N; i >= k; --i) {
        ll t = sum(1, 1, N, 1, i);
        if (t <= 0) continue;
        ll x = (t-1)/k+1;

        if (x > 0) {
            answer += x;
            update_range(1,1,N, i-k+1, i, -x);
            update_range(1,1,N, i+1, i+1, +k*x);
        }
    }
    REP(i,1,k) {
        ll t = sum(1, 1, N, 1, i);
        if (t <= 0) continue;
        ll x = (t-1)/i+1;

        if (x > 0) {
            answer += x;
            update_range(1,1,N, 1, k, -x);
            update_range(1,1,N, k+1, k+1, +k*x);
        }
    }
    cout << answer;
}