abc320

등수는 계속 비슷하다.

솔브수는 계속 비슷하게 나오지만, 실력은 확실히 성장하고 있는 것 같다. 저저번에는 F가 감도 안잡혔는데, 이번엔 꽤 풀이를 진행했다.

 

A (0:00 ~ 0:35)

n^m + m^n.

using namespace std;
#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())
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define MOD 998244353
typedef long long ll;
int main(){
    string s,t;
    ll n,m,k;
    vector<ll> v;
    map<ll,ll> mp;
    fast;
    cin>>n>>m;
    cout<<(ll)(pow(n,m)+pow(m,n));
}

 

B (0:35 ~ 2:01)

부분문자열 중 팰린드롬인 것의 최대 길이. O(N^3)

#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 <list>
#include <ctime>
#include <random>
using namespace std;
#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())
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define MOD 998244353
typedef long long ll;
int main(){
    string s,t;
    ll n,m,k;
    vector<ll> v;
    map<ll,ll> mp;
    fast;
    cin>>s;
    ll ans=0;
    for(int i = 0 ; i < s.size() ; i++){
        for(int j = i ; j < s.size() ; j++){
            bool f=1;
            for(int l = i, r = j ; l < r ; l++,r--)if(s[l]!=s[r])f=0;
            if(f)ans = max(ans,(ll)j-i+1);
        }
    }
    cout<<ans;
}

 

C (2:01 ~ 8:15 + penalty 5:00)

그냥 m*3짜리 for문 3번 돌려서 슬롯 멈출 위치를 정해주면 된다. 근데 처음에 m*2로 돌려서 1틀

using namespace std;
#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())
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define MOD 998244353
typedef long long ll;
int main(){
    string s1,s2,s3;
    ll n,m,k;
    fast;
    cin>>m>>s1>>s2>>s3;
    ll ans = 1e18;
    for(int i = 0 ; i < m*4 ; i++){
        for(int j = 0 ; j < m*4 ; j++){
            if(i==j)continue;
            for(int k = 0 ; k < m*4 ; k++){
                if(i==k or j==k)continue;
                if(s1[i%m]==s2[j%m] and s2[j%m]==s3[k%m])ans = min(ans, (ll)max({i,j,k}));
            }
        }
    }
    if(ans==1e18)cout<<-1;
    else cout<<ans;
}

이걸 생각보다 늦게 푼 사람이 많다. 해석이 어려워서 그런가? 근데 1틀만 안했으면 퍼포가 1900이 넘었는데 좀 아쉽다.

 

D (8:15 ~ 17:22)

A->B를 (x,y)로 바라보면 가중치를 그걸로 해서 간선을 만들고 1번에서 dfs를 해주면 된다.

using namespace std;
#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())
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define MOD 998244353
typedef long long ll;
ll n, m;
vector<tuple<ll,ll,ll>> adj[202020];
pair<ll,ll> visited[202020];
bool chk[202020];
void dfs(ll x){
    chk[x]=1;
    for(auto [next,dx,dy] : adj[x]){
        if(chk[next])continue;
        else{
            visited[next] = {visited[x].first+dx,visited[x].second+dy};
            dfs(next);
        }
    }
}
int main(){
    fast;
    cin>>n>>m;
    for(int i = 0 ; i < m ; i++){
        ll a,b,x,y; cin>>a>>b>>x>>y;
        adj[a].push_back({b,x,y});
        adj[b].push_back({a,-x,-y});
    }
    dfs(1);
    for(int i = 1 ; i <= n ; i++){
        if(!chk[i])cout<<"undecidable\n";
        else cout<<visited[i].first<<" "<<visited[i].second<<"\n";
    }
}

생각보다 제출이 적었어서 틀린 풀이인지 1분정도 의심했다가 그냥 냈다. 자신을 믿도록 하자

 

E (17:22 ~ 32:19)

이걸 왜 세그로 했지? 아마 이 문제의 영향일 것이다.

28326번: 고기 파티

using namespace std;
#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())
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define MOD 998244353
typedef long long ll;
ll n, m;
vector<tuple<ll,ll,ll>> tim[404040], tim2[404040];
vector<ll> T;
struct segtree{
    vector<pair<ll,ll>> tree;
    segtree(): tree(808080){}
    void upd(ll node, ll s, ll e, ll idx, ll diff){ //first가 0: 있다 1 : 없다
        if(idx<s or e<idx)return;
        if(s==e)tree[node] = {diff,idx};
        else{
            ll mid = s+e>>1;
            upd(node*2,s,mid,idx,diff);
            upd(node*2+1,mid+1,e,idx,diff);
            tree[node] = min(tree[node*2],tree[node*2+1]);
        }
    }
    pair<ll,ll> query(ll node, ll s, ll e, ll l, ll r){
        if(e<l or r<s)return {1e18,0};
        if(l<=s and e<=r)return tree[node];
        ll mid=s+e>>1;
        return min(query(node*2,s,mid,l,r),query(node*2+1,mid+1,e,l,r));
    }
} seg;
ll ans[202020];
ll cp(ll x){ return lower_bound(all(T),x)-T.begin();}
int main(){
    fast;
    cin>>n>>m;
    vector<tuple<ll,ll,ll>> Q;
    for(int i = 1 ; i <= n ; i++)seg.upd(1,1,n,i,0);
    for(int i = 0 ; i < m ; i++){
        ll t,w,s; cin>>t>>w>>s;
        T.push_back(t); T.push_back(t+s);
        Q.push_back({t,w,s});
    }
    sort(all(T)); comp(T);
    for(int i = 0 ; i < m ; i++){
        auto [t,w,s] = Q[i];
        tim[cp(t)].push_back({w,0,t+s});
    }
    for(int i = 0 ; i <= 400000 ; i++){
        for(auto [query,type,TIME] : tim2[i]){
            seg.upd(1,1,n,query,0);
        }
        for(auto [query, type, TIME] : tim[i]){
            auto [diff,idx] = seg.query(1,1,n,1,n);
            if(diff==1)continue;
            ans[idx] += query;
            seg.upd(1,1,n,idx,1);
            tim2[cp(TIME)].push_back({idx,1,0});
        }
    }
    for(int i = 1 ; i <= n ; i++)cout<<ans[i]<<"\n";
}

세그 중독....

 

---

upsolving

F - (32:19 ~ 100:00)

바이토닉 투어 변형이다.

이거랑 비슷하게 왕복이 아니고 출발지에서 2명이 서로 다른 주유소를 이용해서 $X_n$까지 간다고 생각하자.

그러면 처음에 이렇게 dp식을 세울 것이다. 1번은 0->n, 2번은 n->0으로 가는 것인데 2번은 거꾸로 생각할 것이다.(즉 이동할때마다 용량이 증가하고 주유소를 사용하면 용량이 그만큼 감소한다.)

dp[i][j][k][l] := 1번이 i, 2번이 j 주유소에 있고 1번은 현재 용량이 k, 2번은 용량이 l일때 최소 비용

하지만 이 문제는 주유소를 둘 중 하나가 반드시 이용할 필요가 없다. 따라서 이렇게 식을 세울 수 있다.

dp[i][j][k] := i번째 주유소까지 봤을 때 1번은 용량이 k, 2번은 l일 때 최소 비용

그럼 다음과 같은 3가지 경우가 있다.

1. 둘다 i번 주유소를 이용하지 않는다

2. 1번이 이용한다

3. 2번이 이용한다

셋 다 용량이 0~H임을 고려하여 점화식을 세워주면 된다.

그리고 하나 더 고려해야 할 게 있는데, 실제로는 왕복을 해야 하므로 둘다 n번에 도착했을 때 k>=l이어야 한다. 1번이 온 용량을 2번이 그대로 이어받는 것이기 때문이다.

using namespace std;
#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())
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#define MOD 998244353
typedef long long ll;
ll dp[303][303][303];
ll n, H;
ll X[303], F[303], p[303];
ll f(ll x, ll y, ll z){
    if(x==n)return y>=z ? 0 : 1e18;
    ll &ret = dp[x][y][z];
    if(~ret)return ret; ret = 1e18;
    ll w = X[x+1]-X[x];
    if(y-w>=0 and z+w<=H)ret = min(ret, f(x+1,y-w,z+w));
    if(y-w+F[x]>=0 and z+w<=H)ret = min(ret, f(x+1,min(H,y+F[x])-w,z+w)+p[x]);
    if(y-w>=0 and z+w-F[x]<=H)ret = min(ret, f(x+1,y-w,max(0LL,z-F[x])+w)+p[x]);
    return ret;
}
int main(){
    fast;
    cin>>n>>H;
    for(int i = 1 ; i <= n ; i++)cin>>X[i];
    for(int i = 1 ; i <= n-1 ; i++)cin>>p[i]>>F[i];
    memset(dp,-1,sizeof(dp));
    ll ans = 1e18;
    for(int i = 0 ; i <= H ; i++)ans = min(ans, f(0,H,i));	//f(0,H,0)만 구해도 된다
    cout<<(ans==1e18 ? -1 : ans);
}

대회 때는 위 점화식까지 세우고 dp짜다가 시간이 없어서 끝났다. 조금만 더 빨리 떠올랐으면 풀었을 것 같다.