Codeforces Round 665 (Div. 2) A~D

한국인 세터길래 풀어봤다.

cp느낌으로 한게 아니라서 푼 순서는 B-C-D-A

A

가장 문제가 난해했다. 쉬운 case work로 풀린다

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 1000000007
typedef long long ll;
void solve(){
    ll n,k; cin>>n>>k;
    if(n<k)cout<<k-n<<"\n";
    else if((n&1) == (k&1))cout<<0<<"\n";
    else cout<<1<<"\n";
}
int main(){
    ll t;
    cin>>t; while(t--)solve();
}

 

B

무섭게 생겼다. a에 있는 2와 b에 있는 1이 대응되어야 무조건 양수가 나오므로 얘들끼리 최대한 매칭시킨다.

그리고 b에 있는 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 t;
void solve(){
    ll a0,a1,a2,b0,b1,b2;
    cin>>a0>>a1>>a2>>b0>>b1>>b2;
    ll ans = min(a2,b1)*2;
    ll m = min(a2,b1);
    a2 -= m, b1 -= m;
    m = min(b2,a0);;
    b2 -= m, a0 -= m;
    if(b2>0){
        m = min(b2,a2);
        b2 -= m, a2 -= m;
    }
    ans -= b2*2;
    cout<<ans<<"\n";
}
int main(){
    cin>>t; while(t--)solve();
}

 

C (+1틀)

최솟값을 m이라 하면, Ai -> m -> Aj 느낌의 swap을 통해서 swap이 가능하다. 즉, m의 배수이면 m을 거쳐서 다른 m의 배수끼리 반드시 swap이 가능하다. 이걸 판별해서 정렬이 가능한지 보면 된다.

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 t;
void solve(){
    ll n; cin>>n;
    vector<ll> v(n);
    for(auto &i : v)cin>>i;
    auto e = v; sort(all(v));
    for(int i = 0 ; i < n ; i++){
        if(v[i]==e[i])continue;
        if(gcd(v[i],v[0]) != v[0] or gcd(e[i],v[0]) != v[0]){
            cout<<"NO\n";
            return;
        }
    }
    cout<<"YES\n";
}
int main(){
    cin>>t; while(t--)solve();
}

 

D

그리디 + dfs 느낌의 문제이다.

문제에서 주어진 수식은, 모든 정점간 거리의 합이다. 각 간선이 몇번 카운팅되는지를 구한 후, 가장 많이 카운팅되는 간선에게 최대한 k를 몰빵해준다는 느낌(나머지는 최대한 작게)으로 풀면 된다. 각 간선이 몇번 카운팅되는지 구하는 건, 이 간선 아래에 있는 서브트리의 크기 * (n-서브트리 크기) 이다. 왜냐하면 이 간선을 지나는 경로의 개수는 결국 간선 아래의 서브트리에서 1개 고르고, 간선 위에서 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 1000000007
typedef long long ll;
ll t;
vector<ll> adj[101010];
vector<ll> cnt_edge;
ll siz[101010];
ll n;
ll dfs(ll x, ll prv){
    siz[x] = 1;
    for(auto next : adj[x]){
        if(next==prv)continue;
        siz[x] += dfs(next,x);
    }
    if(x!=1)cnt_edge.push_back(siz[x] * (n-siz[x]));
    return siz[x];
}
void solve(){
    cin>>n;
    for(int i = 1 ; i <= n ; i++)adj[i].clear();
    cnt_edge.clear();
    memset(siz,0,sizeof(siz));
    for(int i = 0 ; i < n-1 ; i++){
        ll a,b; cin>>a>>b;
        adj[a].push_back(b);
        adj[b].push_back(a);
    }
    ll m; cin>>m;
    vector<ll> v(m);
    for(auto &i : v)cin>>i;
    sort(all(v));
    ll esiz = n-1;
    dfs(1,0);
    sort(all(cnt_edge));
    ll idx=0;
    if(esiz > m)idx += esiz-m;
    ll cur=0;
    for(int i = idx ; i < n-2 ; i++){
        cnt_edge[i] = (cnt_edge[i]%MOD * v[cur++] % MOD);
    }
    ll d = 1;
    for(int i = cur ; i < m ; i++)d = (d*v[i])%MOD;
    cnt_edge[n-2] = (cnt_edge[n-2]%MOD * d % MOD);
    ll ans=0;
    for(int i = 0 ; i < n-1 ; i++)ans = (ans+cnt_edge[i])%MOD;
    cout<<ans<<"\n";
}
int main(){
    cin>>t; while(t--)solve();
}