단대소프트고 2023 알고리즘 대회 (작성중)

*작성중*

 

A

구현

#include <iostream>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cstring>
#include <vector>
#include <string>
#include <climits>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <bitset>
#include <cassert>
#include <iomanip>
#include <list>
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
typedef long long ll;
string t = "DKSH";
int main(){
    fast;
    string s; cin>>s;
    ll cnt=0;
    for(int i = 0 ; i < s.size()-3 ; i++){
        bool f=1;
        for(int j = 0 ; j < 4 ; j++){
            if(s[i+j]!=t[j])f=0;
        }
        cnt += f;
    }
    cout<<cnt;
}

 

B

그리디

#include <iostream>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cstring>
#include <vector>
#include <string>
#include <climits>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <bitset>
#include <cassert>
#include <iomanip>
#include <list>
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
typedef long long ll;
vector<ll> v;
ll n, k;
int main(){
    fast;
    cin>>n>>k;
    ll s = 0;
    for(int i = 0 ; i < n ; i++){
        ll a; cin>>a;
        s += a;
        v.push_back(s);
    }
    sort(rll(v));
    ll ans = 0;
    for(int i = 0 ; i < k ; i++)ans += v[i];
    cout<<ans;
}

 

C

애드혹? constructive?

#include <iostream>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cstring>
#include <vector>
#include <string>
#include <climits>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <bitset>
#include <cassert>
#include <iomanip>
#include <list>
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
typedef long long ll;
ll n, k;
int main(){
    fast;
    cin>>n>>k;
    k--;
    string ans;
    for(int i = 0 ; i < n-k ; i++)ans += 'a';
    ll cnt = 0;
    for(int i = n-k ; i < n ; i++){
        ans += char('a' + ++cnt);
    }
    cout<<ans;
}

 

D (무려 22WA후 AC)

금광세그 비슷하게 짜기

#include <iostream>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <cstring>
#include <vector>
#include <string>
#include <climits>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <bitset>
#include <cassert>
#include <iomanip>
#include <list>
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
typedef long long ll;
ll n, q;
typedef tuple<ll,ll,ll> T;
const tuple<ll,ll,ll> no = {-1e18,0,0};
bool f;
T merge(T a, T b){
    auto [d1, siz1, idx1] = a;
    auto [d2, siz2, idx2] = b;
    if(d1!=d2){
        if(d1>d2){
            return {d1,siz1,idx1};
        }
        else return {d2,siz2,idx2};
    }
    else{
        if(siz1<siz2){
            if(idx1+siz1==idx2){
                f=1;
                siz2 += siz1;
                idx2 = idx1;
            }
            return {d2,siz2,idx2};
        }
        else{
            if(idx1+siz1==idx2){
                f=0;
                siz1 += siz2;
            }
            return {d1,siz1,idx1};
        }
    }
}
bool cmp(T a, T b){//a>b?
    auto [x,y,z] = a;
    auto [x2,y2,z2] = b;
    if(x==x2){
        if(y==y2)return z<z2;
        return y>y2;
    }
    return x>x2;
}
struct segtree{
    vector<tuple<T,T,T>> tree;
    segtree(): tree(1212121) {}
    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,1,idx},{diff,1,idx},{diff,1,idx}};
        else{
            ll mid = s+e>>1;
            upd(node*2,s,mid,idx,diff); upd(node*2+1,mid+1,e,idx,diff);
            auto [a,b,c] = tree[node*2];
            auto [D,E,F] = tree[node*2+1];
            auto &[g,h,i] = tree[node];
            auto [d1, siz1, idx1] = c;
            auto [d2, siz2, idx2] = E;
            g = merge(a,D);
            auto [D1,Siz1,Idx1] = b;
            auto [D2,Siz2,Idx2] = F;
            if(Idx1+Siz1==idx2)h = merge(b,E);
            else h = b;
            if(idx1+siz1==Idx2)i = merge(c,F);
            else i = F;
            if(idx1+siz1==idx2){
                if(cmp(merge(c,E),g))g = merge(c,E);
            }
            if(cmp(h,g))g=h;
            if(cmp(i,g))g=i;
        }
    }
} seg;
int main(){
    fast;
    cin>>n;
    for(int i = 1 ; i <= n ; i++){
        ll a; cin>>a; seg.upd(1,1,n,i,a);
    }
    cin>>q;
    while(q--){
        ll a,b; cin>>a>>b;
        seg.upd(1,1,n,a,b);
        auto [A,B,c] = seg.tree[1];
        auto [diff,siz,idx] = A;
        cout<<idx<<" "<<idx+siz-1<<"\n";
    }
}