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분)

리프끼리 이어주면 \( \left \lceil \frac{leaf}{2} \right \rceil \)번 하면 됨을 알 수 있다. 증명은 수학적 귀납법으로 하면 된다.

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)

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

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

처음에 주어진 순열이 [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)가 \( A_{1} \)에 영향을 받았다면, 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' 카테고리의 다른 글

Codeforces Round 930 (Div.2) (+퍼플 달성) (3)	2024.03.01
Codeforces Round 924 (Div.2) (0)	2024.02.11
Codeforces Round 917 (Div.2) (1)	2023.12.25
Codeforces Round 904 (Div.2) + 905 (Div.2) (2)	2023.10.23
Codeforces Round 665 (Div. 2) A~D (0)	2023.09.24

shjeong

Codeforces Round 915 (Div.2)

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

티스토리툴바

Codeforces Round 915 (Div.2)

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

'codeforces/div2' Related Articles

티스토리툴바