본문 바로가기

codeforces/div2

Codeforces Round 915 (Div.2)

나쁘지 않은 결과이다.

 

그와중에 이거 뭐임 ㅠㅠ

A (4분)

사실 풀이를 모른다. 그냥 사람들 푸는 속도 보고 예제 규칙보고 맞췄다.

더보기
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 long double ld;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;
void solve(){
    ll a,b; cin>>a>>b;
    cout<<max(a,b)<<"\n";
}
int main(){
    fast;
    ll t; cin>>t; while(t--)solve();
}

 

 

B (6분)

리프끼리 이어주면 leaf2번 하면 됨을 알 수 있다. 증명은 수학적 귀납법으로 하면 된다.

더보기
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 long double ld;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;
void solve(){
    ll n; cin>>n;
    vector<ll> deg(n+1,0);
    for(int i = 0 ; i < n-1 ; i++){
        ll a,b; cin>>a>>b;
        deg[a]++; deg[b]++;
    }
    ll cnt = 0;
    for(int i = 1 ; i <= n ; i++){
        if(deg[i]==1)cnt++;
    }
    cout<<(cnt+1)/2<<"\n";
}
int main(){
    fast;
    ll t; cin>>t; while(t--)solve();
}

 

 

C (15분)

아주 중요한 관찰 하나를 하면 된다. 그건 바로 사전순으로 가장 큰 부분집합에 항상 문자열의 마지막 원소가 포함된다는 점이다.

생각해보면 되게 당연하다. 그래서 이게 의미하는 것은, 처음에 사전순 가장 큰 부분 집합을 하나 찾으면, 걔를 cyclic 하면서 크기가 1씩 줄어들고 결국 사전순으로 가장 큰 문자가 마지막 원소로 이동해 더 이상 cyclic이 일어날 수 없게 된다. 즉 1번만 찾아서 cyclic해주면 된다.

더보기
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 long double ld;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;
void solve(){
    ll n;
    string s;
    cin>>n>>s;
    vector<ll> v;
    for(int i = 0 ; i < n ; i++){
        while(v.size() and s[v.back()] < s[i])v.pop_back();
        v.push_back(i);
    }
    string t = s;
    ll siz = v.size();
    for(int i = 0 ; i < siz; i++){
        t[v[i]] = s[v[siz-i-1]];
    }
    ll cnt = 0;
    for(int i = 0 ; i < siz ; i++){
        if(s[v[i]] != s[v[0]])break;
        cnt++;
    }
    cout<<(is_sorted(all(t)) ? siz-cnt : -1)<<"\n";
}
int main(){
    fast;
    ll t; cin>>t; while(t--)solve();
}

 

 

D (57분, +3)

먼저 해야하는 관찰은, mex(1..Ai)=min(Ai+1..An)가 성립한다는 것이다. (i=n일때는 그 값을 n으로 정의하자.) 이는 배열 A가 순열이기 때문에 성립한다.이제 모든 cyclic 꼴에서 이 값의 합을 빠르게 구해주면 된다.

먼저 배열을 2배 늘려서 모든 cyclic을 순회한다고 생각하자.

편의상 min(l~r) = min(A_l ~ A_r)을 의미한다.

처음에 주어진 순열이 [1,3,0,2,4]라고 하자. 그럼 위 사진처럼 원본 순열의 값은 위와 같이 min(1,4)+min(2,4)+min(3,4)+min(4,4)+n이 된다. 이제 한번 left shift한 [3,0,2,4,1]을 보자.

그럼 이런식으로 값이 옮겨감을 알 수 있다. 이제 이것들이 실제로 어떤 값을 가지는지 알아보자. min(1,4)와 min(2,5)에는 어떤 관계가 있을까? 만약 min(1,4)가 A1에 영향을 받았다면, min(2,5)에서 값이 바뀔 것이다. 그렇지 않다면 바뀌지 않을 것이다. 그럼 반대로 생각해보자. 어떤 원소가 실제로 몇개의 구간에 영향을 줄까? 예를 들어 바로 위 [3,0,2,4,1]의 경우 0이 1개, 1이 3개의 구간에 영향을 준다.

 

우리가 [l..r]을 보고 있을 때, 실제로 값이 될 수 있는 원소는 r에서 시작해서, 자기보다 작으면서 왼쪽에 있는 가장 오른쪽 원소를 반복해서 찾은 값들이다. 예를 들어 [0,4,1,3]에서는 가장 오른쪽인 3에서 자기보다 작으면서 왼쪽에 있는 가장 오른쪽 원소는 1이 되며, 1 다음은 0이 된다. 

그럼 이것들이 실제로 몇개에 영향을 주는지를 구하면 되며, 이는 결국 자기보다 작으면서 왼쪽에 있는 가장 오른쪽 원소를 반복해서 찾은 값들의 인접한 인덱스 차임을 알 수 있다(가장 왼쪽은 자기 인덱스-구간 시작위치+1). 즉 [0,4,1,3]에서 [0,1,3]을 찾았을 때, 3과 1의 인덱스 차가 1이므로 3은 1개, 1과 0의 인덱스 차가 2이므로 1은 2개에 영향을 준다. 0은 시작지점부터 자기 인덱스까지 영향을 주므로 1개에 영향을 준다.

이제 이 방식을 구현하면 되는데, 이는 덱을 back에서 monotone increase하게 유지하면서, front에서 빠지는 값들을 빼주는 방식으로 구현할 수 있다.

더보기
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 long double ld;
typedef pair<ll,ll> P;
typedef pair<ll,P> PP;
void solve(){
    ll n; cin>>n;
    vector<ll> v(n);
    for(auto &i : v)cin>>i;
    if(n==1){
        cout<<"1\n";
        return;
    }
    ll ans = 0;
    vector<ll> e = v;
    for(auto i : v)e.push_back(i);
    deque<ll> dq;
    for(int i = 1 ; i < n ; i++){
        while(dq.size() and e[dq.back()] > e[i])dq.pop_back();
        dq.push_back(i);
    }
    ans = e[dq.front()]*dq.front();
    for(int i = 1 ; i < dq.size() ; i++)ans += e[dq[i]]*(dq[i]-dq[i-1]);
    ll cur = ans;
    //for(auto i : dq)cout<<i<<" "; cout<<endl;
    //DEB<<cur<<endl;
    for(ll l = 2, r = n ; r < n*2 ; l++, r++){
        if(dq.size())cur -= e[dq.front()];
        if(dq.front()<l)dq.pop_front();
        while(dq.size() and e[dq.back()] > e[r]){
            if(dq.size()==1)cur -= e[dq.back()]*(dq.back()-l+1);
            else cur -= e[dq.back()]*(dq.back()-dq[dq.size()-2]);
            dq.pop_back();
        }
        dq.push_back(r);
        if(dq.size()==1)cur += e[dq.back()]*(dq.back()-l+1);
        else cur += e[dq.back()]*(dq.back()-dq[dq.size()-2]);
        ans = max(ans,cur);
        //for(auto i : dq)cout<<i<<" "; cout<<endl;
        //DEB<<s<<" "<<cur<<endl;
    }
    cout<<ans+n<<"\n";
}
int main(){
    fast;
    ll t; cin>>t; while(t--)solve();
}

 

 

 

 

그래프가 진동한다 ㄷㄷ..

'codeforces > div2' 카테고리의 다른 글