본문 바로가기
codeforces/div2

Codeforces Round 924 (Div.2)

satturn80 2024. 2. 11. 20:53

여러모로 잊을 수가 없는 라운드가 되었다.

일단 점수판을 보면 알겠지만 C에서 말렸다. 풀이 시간은 정확히는 모르겠는데 생각까지 무조건 20분 안이었다. 근데 이 풀이에서 고려하지 않은 케이스가 있었다. 근데 구현 실수인줄 알고 진짜 시간을 내다버렸다. 그렇게 1시간만에 힘들게 C를 풀고 망했다고 마음속으로 외치며 D를 봤다. 그 뒤의 이야기는 풀이를 적으면서 설명하겠다.

 

 

A

얘 보자마자 뇌가 멈췄다. 머릿속에선 홀짝성을 외치고 있는데 내 손은 이상한 관찰만 하고 있다. 근데 이 덕분에 judgement error 이슈를 피해갔다(?). 결국 6분째에 AC

예제 보고 있었는데 이거 나옴

더보기 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC 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 MOD2 998244353
#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;
    if(a&1 and b&1){
        cout<<"NO\n";
        return;
    }
    if(~a&1 and ~b&1){
        cout<<"YES\n";
        return;
    }
    if(min(a,b)*2 == max(a,b)){
        cout<<"NO\n";
        return;
    }
    cout<<"YES\n";
}
int main(){
    fast;
    ll t; cin>>t; while(t--)solve();
}

 

 

B

보자마자 일단 답이 그렇게 크지 않을 것이라는 생각을 했고, 최솟값이 될 값을 고정하니 바로 풀렸다.

A보다 쉬웠다.

더보기 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC 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 MOD2 998244353
#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;
    deque<ll> dq;
    vector<ll> v(n);
    for(auto &i : v)cin>>i; sort(all(v)); comp(v);
    ll ans = 0;
    for(auto i : v){
        dq.push_front(i);
        while(abs(dq.back() - dq.front()) >= n)dq.pop_back();
        ans = max<ll>(ans,dq.size());
    }
    cout<<ans<<"\n";
}
int main(){
    fast;
    ll t; cin>>t; while(t--)solve();
}

 

 

C

수학 싫어............................

더럽게 문제를 정리하면 결국 n-x가 2k-2의 배수이고, 2k-x-n이 2k-2의 배수인 k임을 알 수 있다.

그래서 약수만 봐주고 중복 빼주면 되는데... 처음에 풀이 과정에서 2k-x-n을 음수 때문에 안 될 줄 알고 아예 이 케이스를 배제해버렸다.

그러다가 나중에 진짜 왜 안나오는지 궁금해서 실제 k를 출력해보다가 2k-x-n이 음수인 케이스를 발견해서 바로 고치고 AC.

더보기 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC 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 MOD2 998244353
#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, x; cin>>n>>x;
    ll ans = 0;
    bool flag = 0;
    if((n-x)%2==0){
        set<ll> st;
        for(ll i = 1 ; i*i <= (n-x) ; i++){
            if((n-x)%i==0){
                if(i%2==0){
                    if(i/2+1 >= x){
                        st.insert(i/2+1);
                    }
                }
                if(i*i != (n-x) and (n-x)/i % 2 == 0){
                    if((n-x)/i/2+1 >= x){
                        st.insert((n-x)/i/2+1);
                    }
                }
            }
        }
        for(ll i = 1 ; i*i <= n+x-2 ; i++){
            if((n+x-2)%i==0){
                if(i%2==0){
                    if(i/2+1 >= x){
                        st.insert(i/2+1);
                    }
                }
                if(i*i != (n+x-2) and (n+x-2)/i % 2 == 0){
                    if((n+x-2)/i/2+1 >= x){
                        st.insert((n+x-2)/i/2+1);
                    }
                }
            }
        }
        cout<<st.size()<<"\n";
    }
    else cout<<"0\n";
}
int main(){
    fast;
    ll t; cin>>t; while(t--)solve();
}

 

 

D

솔직히 말하면 찍었다(?).

일단 그룹을 고정하면 각 i마다 (c[i]C2 - 각 그룹C2) * b만큼 더하니까 그룹마다 최대한 고르게 배정해야 될 것이라는 관찰을 하나 했고, 이를 통해 그룹 개수 k에 대한 함수 f(k)를 만들었다. 그리고 생긴걸 보니까 뭔가 볼록할 것 같았다. 그래서 살면서 한번도 삼분 탐색을 써본 적이 없지만 구글링해서 삼분탐색을 했더니 맞았다?????

아무튼 맞았으면 된거다. C가 1시간 걸렸는데 얘 20분 걸렸다.

더보기 
#include <bits/stdc++.h>
using namespace std;
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC 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 MOD2 998244353
#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;
ll n,b,x;
vector<ll> c;
ll cal(ll x){ return x*(x-1)/2; }
ll f(ll k){
    ll ret=0;
    for(int i = 0 ; i < n ; i++){
        ll q = (c[i]/k), r = (c[i]%k);
        ret += b * (cal(c[i]) - cal(q) * (k-r) - cal(q+1) * r);
    }
    return ret - (k-1) * x;
}
void solve(){
    cin>>n>>b>>x;
    c.resize(n);
    for(auto &i : c)cin>>i;
    ll mx = *max_element(all(c));
    ll l = 1, r = mx;
    while(l+2 < r){
        ll a = l+r>>1;
        ll b = a+1;
        if(f(a) > f(b))r = b;
        else l = a;
    }
    cout<<max({f(l),f(l+1),f(r)})<<"\n";
}
int main(){
    fast;
    ll t; cin>>t; while(t--)solve();
}

 

대회에서 찍어서 그것도 1트에 맞춘건 처음이다..

C에서 빨리 맞았으면 오히려 D 찍을 생각을 안했을 것 같아서 어떻게 됐을지 궁금하다.

저작자표시 비영리 동일조건

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

Codeforces Round 961 (Div.2) (코포 복귀전)  (1) 2024.07.24
Codeforces Round 930 (Div.2) (+퍼플 달성)  (3) 2024.03.01
Codeforces Round 917 (Div.2)  (1) 2023.12.25
Codeforces Round 915 (Div.2)  (1) 2023.12.17
Codeforces Round 904 (Div.2) + 905 (Div.2)  (2) 2023.10.23

'codeforces/div2' Related Articles

티스토리툴바