Codeforces Round 917 (Div.2)

원래 짜증나서 안 쓸려 했는데 원래 망한 대회에서 배울 점이 생기므로 그냥 쓰겠다.

와 너무 재밌다

A

뒤에 있을 모든 문제가 충격이 강해서 문제가 기억이 안난다. n개 곱 부호 판별하는 문제였는데 그냥 다 곱하면 오버플로나서 1틀했다.

using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
#define debug(x) cout << #x<<" is "<<x<<"\n";
#define X first
#define Y second
#define DEB cout<<"[DEBUG]"
#define PAIR(a,b) "("<<a<<", "<<b<<")"
#define PRINT1(V) DEB<<#V<<endl; for(auto i : V)DEB<<i<<"\n"
#define PRINT2(V) DEB<<#V<<endl; for(auto [a,b] : V)DEB<<PAIR(a,b)<<"\n";
typedef long long ll;
typedef __int128_t lll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;
void solve(){
    ll n; cin>>n;
    vector<ll> v(n);
    ll t = 1;
    bool iszero = 0;
    bool f = 0;
    for(auto &i : v){
        cin>>i;
        if(i==0)iszero = 1;
        if(i<0)f = !f;
    }
    if(iszero or f){
        cout<<"0\n";
        return;
    }
    cout<<"1\n"<<1<<" "<<0<<"\n";
}
int main(){
    fast;
    ll t; cin>>t; while(t--)solve();
}

 

 

B

얘가 문제다. 아니 이게 어떻게 B인지 모르겠다. 진짜 30분을 봤는데 하나도 모르겠는데 이미 수천명이 풀고 C로 갔길래 C로 갔다.

얘 핵심은 첫번째 글자 지우는 거랑 두번째 글자 지우는 거의 순서를 강제하는 건데, 그렇게 하다보면 관찰이 금방 나오고 쉽게 풀 수 있다.

개인적으로 C보다 어려운 것 같다.

using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
#define debug(x) cout << #x<<" is "<<x<<"\n";
#define X first
#define Y second
#define DEB cout<<"[DEBUG]"
#define PAIR(a,b) "("<<a<<", "<<b<<")"
#define PRINT1(V) DEB<<#V<<endl; for(auto i : V)DEB<<i<<"\n"
#define PRINT2(V) DEB<<#V<<endl; for(auto [a,b] : V)DEB<<PAIR(a,b)<<"\n";
typedef long long ll;
typedef __int128_t lll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;
void solve(){
    ll n, k, d; cin>>n>>k>>d;
    vector<ll> v(n);
    ll c = 1, cur = 0;
    for(auto &i : v){
        cin>>i;
        if(i==c)cur++;
        c++;
    }
    ll ans = cur + (d - 1)/2;
    vector<ll> e(k);
    for(auto &i : e)cin>>i;
    for(int i = 1 ; i <= n*2 ; i++){
        for(int j = 0 ; j < e[(i-1)%k] ; j++){
            if(v[j]-1==j)cur--;
            v[j]++;
            if(v[j]-1==j)cur++;
        }
        if(i<=d-1)ans = max(ans, cur + max(0LL,(d - i - 1)/2));
    }
    cout<<ans<<"\n";
}
int main(){
    fast;
    ll t; cin>>t; while(t--)solve();
}

 

 

C

얘도 문제다. 사실 문제 해석도 되게 어려웠고 보자마자 필자가 가장 싫어하는 유형 같았는데 그래도 한번 초기화하고 나서는 1번-2번 연산을 반복해서 해주는 것이 최적이라는 관찰만 하면 적당한 문제로 바뀐다. 그런데..

    ll ans = cur + (d - 1)/2;
    for(int i = 1 ; i < k ; i++){
        ll a; cin>>a;
        for(int j = 0 ; j < a ; j++){
            if(v[j]-1==j)cur--;
            v[j]++;
            if(v[j]-1==j)cur++;
        }
        ans = max(ans, cur + (d - i - 1)/2);
    }
    ll x; cin>>x;
    cout<<ans<<"\n";

 

위 코드가 시스텟에서 터졌다. 왜냐면 바깥쪽 루프를 2n번 돌려야 최악의 경우에도 정답이 보장되기 때문이다.

지금보니 말도 안되는 코드인데 테케가 약한건지 이게 어떻게 프텟을 통과했는지 모르겠다.

using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 1000000007
#define debug(x) cout << #x<<" is "<<x<<"\n";
#define X first
#define Y second
#define DEB cout<<"[DEBUG]"
#define PAIR(a,b) "("<<a<<", "<<b<<")"
#define PRINT1(V) DEB<<#V<<endl; for(auto i : V)DEB<<i<<"\n"
#define PRINT2(V) DEB<<#V<<endl; for(auto [a,b] : V)DEB<<PAIR(a,b)<<"\n";
typedef long long ll;
typedef __int128_t lll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;
void solve(){
    ll n, k, d; cin>>n>>k>>d;
    vector<ll> v(n);
    ll c = 1, cur = 0;
    for(auto &i : v){
        cin>>i;
        if(i==c)cur++;
        c++;
    }
    ll ans = cur + (d - 1)/2;
    vector<ll> e(k);
    for(auto &i : e)cin>>i;
    for(int i = 1 ; i <= n*2 ; i++){
        for(int j = 0 ; j < e[(i-1)%k] ; j++){
            if(v[j]-1==j)cur--;
            v[j]++;
            if(v[j]-1==j)cur++;
        }
        if(i<=d-1)ans = max(ans, cur + max(0LL,(d - i - 1)/2));
    }
    cout<<ans<<"\n";
}
int main(){
    fast;
    ll t; cin>>t; while(t--)solve();
}

 

 

D

답없어 보였는데 잡아보니까 생각보다 할만 했다. 먼저 A[i+k*j]를 A[i][j]로 생각하자. 이러면 2차원 배열이 된다. 이제 여기서 inversion을 셀 건데, 다음과 같은 2가지 경우를 고려하자.

(i)같은 행의 inversion을 세는 경우

(ii)다른 행의 inversion을 세는 경우

(i)의 경우, 행을 고정하면 P[i]가 고정되어서 P[i] * 2^Q[j] 꼴의 inversion을 찾는거라서 P[i]로 나누면 Q 배열의 inversion을 세는 것과 같아진다. 이는 기본적인 inversion counting으로 해결할 수 있으며, 행이 총 N개이므로 (Q의 inversion 개수) * n이 된다.

 

(ii)의 경우, 다른 행에서 다른 행으로 오므로 같은 행은 정렬되어있다고 생각해도 무방하다. 즉, Q = {0,1,2,3...}이라고 생각해도 된다. 이러면 초항이 P[i]고 2씩 곱해지는 등비수열끼리 inversion을 세는 문제가 된다.

예를 들어 {3,6(3*2)}과 {5,10(5*2)}의 inversion을 구해보자. (6,5)밖에 없다는 것을 알 수 있다. 이를 아래 그림과 같이 표현하자.

파란색 배열에서 빨간색 배열의 inversion을 센다고 생각하자.

Q를 한칸 더 확장해서, {3,6(3*2),12(3*4)}와 {5,10(5*2),20(5*4)}의 inversion을 구해보자.

느껴지는 것이 있는가? 바로 같은 색깔끼리 화살표가 평행하다는 것이다. 그래서 얘네를 한꺼번에 세줄 것이다. Q가 2^i 꼴이므로 최대 약 i <= 20인(즉, 처음 20개 원소) 경우만 고려해도 된다는 것을 알 수 있다. 그리고 이제, 2가지를 세줄 것이다.

(i)파란색 배열의 첫 번째 원소에서 오른쪽으로 가는 화살표.

(ii)두번째~20번째 원소에서 왼쪽으로 가는 화살표.

오른쪽으로 간다는 것은 수직하여 올라가는 것도 포함이며, 왼쪽으로 가는 것은 수직하는 방향을 포함하지 않는다. 그 전에 빨간색 배열의 초항을 y, 파란색 배열의 초항을 x라 하자.

(i)에서는 x > y * 2^k꼴인 경우를 세주어야 하며, x / 2^k > y인 꼴을 세주는 경우와 같으므로 x를 반씩 줄이면서 inversion을 쭉 세주면 된다. 이때 평행한 모든 화살표를 같이 세주어야 하므로 적절히 합을 세주어야 한다.

(ii)는 반대로 x를 2배씩 늘려주면서 inversion을 세주면 된다. 이 경우도 적절히 합을 세주면 된다.

위 내용들을 세그먼트 트리 등으로 적절히 구현하면 된다.

using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma optimize("unroll-loops")
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define all(x) x.begin(), x.end()
#define rll(x) x.rbegin(), x.rend()
#define comp(x) x.erase(unique(all(x)), x.end())
#define MOD 998244353
#define debug(x) cout << #x<<" is "<<x<<"\n";
#define X first
#define Y second
#define DEB cout<<"[DEBUG]"
#define PAIR(a,b) "("<<a<<", "<<b<<")"
#define PRINT1(V) DEB<<#V<<endl; for(auto i : V)DEB<<i<<"\n"
#define PRINT2(V) DEB<<#V<<endl; for(auto [a,b] : V)DEB<<PAIR(a,b)<<"\n";
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;
struct segtree{
    vector<ll> tree;
    void upd(ll node, ll s, ll e, ll idx, ll diff){
        if(idx<s or e<idx)return;
        if(s==e)tree[node] = diff;
        else{
            ll mid = s+e>>1;
            upd(node*2,s,mid,idx,diff);
            upd(node*2+1,mid+1,e,idx,diff);
            tree[node] = tree[node*2+1]+tree[node*2];
        }
    }
    ll query(ll node, ll s, ll e, ll l, ll r){
        if(e<l or r<s)return 0;
        if(l<=s and e<=r)return tree[node];
        ll mid = s+e>>1;
        return query(node*2,s,mid,l,r)+query(node*2+1,mid+1,e,l,r);
    }
};
P p[202020], q[202020];
ll mypow(ll x, ll y){
    ll ret = 1;
    while(y--)ret*=x;
    return ret;
}
void solve(){
    ll n, k; cin>>n>>k;
    segtree segP, segQ;
    segP.tree.resize(n*8); segQ.tree.resize(k*4);
    for(int i = 1 ; i <= n ; i++){
        cin>>p[i].X, p[i].Y = i;
    }
    for(int i = 1 ; i <= k ; i++){
        cin>>q[i].X, q[i].Y = i-1;
    }
    sort(q+1,q+k+1);
    ll ans = 0;
    for(int i = 1 ; i <= k ; i++){
        ans += segQ.query(1,0,k-1,q[i].Y,k-1);
        segQ.upd(1,0,k-1,q[i].Y,1);
    }
    ans %= MOD;
    ans *= n; ans %= MOD;
    for(int i = 1 ; i <= n ; i++){
        ll tmp = 0;
        for(int j = 0 ; j < min(k,20LL) ; j++){
            ll x = mypow(2,j);
            ll z = (p[i].X+x-1)/x;
            ll t = segP.query(1,0,n*2-1,z,n*2-1);
            if(j==min(k,20LL)-1)tmp = (tmp + (k-j)*(k-j+1)/2 * t)%MOD;
            else tmp = (tmp + (k-j) * t) % MOD;
        }
        ans = (ans + tmp) % MOD;
        tmp = 0;
        for(ll j = 1, l = p[i].X*2 ; j < min(k,20LL) ; j++, l *= 2){
            ll t = segP.query(1,0,n*2-1,l,n*2-1);
            tmp = (tmp + (k-j) * t) % MOD;
        }
        ans = (ans + tmp) % MOD;
        segP.upd(1,0,n*2-1,p[i].X,1);
    }
    cout<<ans<<"\n";
}
int main(){
    fast;
    ll t; cin>>t; while(t--)solve();
}

 

생각보다 풀이도 빨리 나왔고 구현도 약간 오차가 있었지만, 총 1시간 정도 걸렸고 C까지 솔직히 40분만 걸렸어도 D는 풀었을 것 같다.