Codeforces Round #737 (Div. 2)

https://codeforces.com/contest/1557

Dashboard - Codeforces Round #737 (Div. 2) - Codeforces

최종적인 퍼포먼스는 1639점으로 나쁘지 않게 나왔지만

대회중 판단에 아쉬운 점이 꽤 있었다.

---

A. Ezzat and Two subsequences

Tag : sort, prefix sum

 

풀이

작은건 작은거끼리, 큰건 큰거끼리 합쳐주는게 평균에 이득이라 생각했다. 두 그룹을 가르는 기준선을 순회하며 모든 기준선에 대해 계산을 수행하면 답을 얻을 수 있다. 나는 딱 보자마자 이것을 생각해내지 못해서 20분을 날려먹었고

long double로 입력을 받아서 첫 제출은 TLE, 두번째 제출은 아슬아슬하게 980ms로 통과했다. 아마 내 풀이에 소수점 출력을 몇자리 늘렸다면 TLE를 맞지않았을까 하고 생각한다. 운이 좋았다. 

+ 티스토리 프사가 988ms라닛...호엥...하는 피림이인데 이걸 실제로 겪어보니 묘하다

 

시간복잡도 : \(O(NlogN)\)

 

전체 코드 

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()), ((x).end())
#define endl '\n'
using namespace std;
using ll = long long;
 
void solve(){
    using ld = long double;
    int n; cin >> n;
    vector<ld> v(n); for(auto &i : v) cin >> i;
    sort(all(v));
    ld ans = -1e18;
    vector<ld> sum(n + 1);
    for(int i = 0; i<n; i++) sum[i + 1] = sum[i] + v[i];
    for(int i = 1; i<n; i++){
        ld t = sum[i]/i + (sum[n]-sum[i])/(n-i);
        ans = max(ans, t);
    }
    cout << ans << endl;
}
 
int main(){
    cin.tie(0)->sync_with_stdio(0), cout.tie(0);
 
    int tc = 1;
    cin >> tc;
    cout << fixed << setprecision(12);
    while(tc--){
        solve();
    }
}

---

B. Moamen and k-subarrays

Tag : Greedy, sort

 

풀이

이 문제는 상당히 고생했다.... 일단 연산에 대해 잘못이해하기도 하고 연산의 횟수가 무한히 가능한줄 알았다.

20분쯤이 지나고 나서야 문제를 다시 차근차근 읽어봤다. 예전에 풀어본 문제와 혼동해서 그랬었는데 이건 내 특유의 버릇이다. 뭘 물어보는지 대충 알거같다!하면 바로 지문을 그만읽고 코딩 하러간다.  문제를 이해만 했다면 구현 외에는 어려울 점이 없는 듯하다. 경험이 많이 없다면 정렬 후의 인덱스를 구하는 것에 어려움을 느낄 수도 있을 듯하다. 원본 배열을 정렬 후 인덱스가 오름차순으로 연속된 \(P\)개의 구간으로 쪼갰을 때 이 \(P\)가 \(K\)이하라면 항상 가능하다. 정렬된 배열의 부분배열은 항상 정렬이 되어있기 때문이다.

 

시간복잡도 : \(O(NlogN)\)

 

전체 코드

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()), ((x).end())
#define endl '\n'
using namespace std;
using ll = long long;
 
void solve(){
    int n, k; cin >> n >> k;
    vector<pair<int,int>> v(n + 1);
    vector<int> kth(n + 1);
    set<pair<int,int>> st;
    for(int i = 1; i<=n; i++) {
        cin >> v[i].fi; v[i].se = i;
        st.insert(v[i]);
    }
    int cnt = 0;
    while(st.size()){
        kth[st.begin()->se] = ++cnt;
        st.erase(st.begin());
    }
    int p = 0;
    for(int i = 2; i<=n; i++){
        if(kth[i-1] + 1 != kth[i]) p++;
    }
    if(p + 1 > k) cout << "NO" << endl;
    else cout << "YES" << endl;
}
 
int main(){
    cin.tie(0)->sync_with_stdio(0), cout.tie(0);
 
    int tc = 1;
    cin >> tc;
    while(tc--){
        solve();
    }
}

---

C. Moamen and k-subarrays

Tag : Bitmasks, Combinatorics, Dp

 

풀이

\( A_{1} and A_{2} .... and A_{N} >= A_{1} xor A_{2} .... xor A_{N} \) 가 성립하는 경우의 수를 물어보는 문제다.

이 때 A의 비트는 0번부터 k-1번까지만 고려한다.   

K가 1일 때를 고려해보자. 모든 \(A_{i}\)는 0 또는 1이다. 이러한 상황에서 and가 더 큰 경우는 한가지뿐이다.

모든 \(A_{i}\)가 1이고 ( and = 1 ) N이 짝수여야 한다. ( xor = 0 ) 

\(and = xor\)이 되는 경우는 두가지 있다.

\(and = 1, xor = 1 \) ) 모든 \(A_{i}\)는 1이고 \(N\)이 홀수\(

\(and = 0, xor = 0\) ) \(A_{i}\)중 하나라도 0이 존재한다면 and는 0이 되고 xor = 0 인 경우는 짝수개만이 1인 경우이다.

이 두개의 교집합을 구하면 \( NC0 + NC2 + NC4 + NC6..... \) 가 된다. 이항계수의 성질에 의해 이는 \(2^{N-1}\)이고 \(N\)이 짝수라면 and가 1이 되는 경우를 배제하기 위해 1을 빼줘야한다. 

 

이제 \(K > 1\)일 때로도 확장을 해보자. \(and\)가 이기는 것이 결정나는 비트의 번호를 \(P\)라고 하면 \(P\)의 상위 비트의 결과는 모두 비기는 경우여야하고 \(P\)에서는 \(and\)가 1 \(xor\)은 \(0\)이어야한다. 그 아래비트는 어떻게 되던지 상관없다. 풀이의 핵심이라 할 것은 이기는 경우와 비기는 경우를 구분해서 따로 계산해주는 것이다.

 

+ 수업 진행을 하게 될 일이 생겨서 평소에 쓰던 템플릿을 사용하지 않고 있는데 ( 나만 아는 이상한 매크로들을 수업 자료로 쓸 순 없으니... ) 그 때문에 거듭제곱 분할정복 구현을 몇달만에 다시 해봤다. 여기서 오버플로우를 내는 실수를 저질러 패널티가 쌓여버렸다.... 애꿎은 풀이의 정당성이나 검토하며 시간을 날린게 아깝다. 이런 구현 실수가 항상 내 발목을 잡는데 고쳐야겠다.

 

시간복잡도 : \(O(Klog(K * N))\)

 

전체 코드

#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()), ((x).end())
#define endl '\n'
using namespace std;
using ll = long long;
 
const ll MOD = 1e9 + 7;
 
ll power(ll a, ll b){
    if(b == 0) return 1ll;
    ll t = power(a, b/2);
    if(b % 2) return (t * t % MOD * a) % MOD;
    else return t * t % MOD;
}
 
void solve(){
    ll n, k; cin >> n >> k;
    ll ans = 0;
    ll now = 1;
    for(ll i = k - 1; i>=0; i--){
        if(n % 2 == 0) ans = (ans + now * power(2ll,n * i) % MOD) % MOD;
 
        ll t = 0;
        if(n % 2) t = 1;
 
        t = (t + power(2ll,n-1)) % MOD;
        if(n % 2 == 0) t = (t - 1 + MOD) % MOD;
 
        if(t < 0) t = (t + MOD) % MOD;
 
 
        now = now * t % MOD;
    }
    ans = (ans + now) % MOD;
    cout << ans << endl;
}
 
int main(){
    cin.tie(0)->sync_with_stdio(0), cout.tie(0);
 
    int tc = 1;
    cin >> tc;
    while(tc--){
        solve();
    }
}

 

---

마무리

A번을 좀만 더 빨리 풀었다면.... B 지문을 좀 더 꼼꼼히 읽었다면.... C 구현을 좀 오래걸리더라고 신경썼더라면....

하는 아쉬움들이 남는다.  ㅠㅠ 그래도 어찌저찌 C까지 풀었으니 블루 퍼포먼스는 만들어서 다행이다.