Codeforces Round 961 (Div.2) (코포 복귀전)

B에서 말려서 멸망!

오랜만에 푸니까 코포 스타일 문제가 적응이 안되네요

D도 50분 줬으면 풀었을 것 같은데 좀 아쉽지만

아무튼 다시 열심히 해서 오렌지 ㄱㄱ

20240724 +)

블루 복귀 :(

A(0:00 ~ 0:04, 0WA)

문제 요약 : n x n 판에 k개의 기물을 올릴 때 기물이 올라가있는 대각선의 개수는 최소 몇 개인가? ((i,j)는 i+j번 대각선 위에 있음)

풀이

기물이 많은 대각선부터 순서대로 나열하면 그 크기가 n, n-1, n-1, n-2, n-2 ... , 1, 1이므로 큰 곳부터 놔주면서 k를 언제 넘는지 보면 된다.

구현하다가 좀 실수해서 2분 정도 낭비.

#include <bits/stdc++.h>
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
#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 __int128_t lll;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<P,ll> PP;
void solve(){
    ll n, k; cin>>n>>k;
    if(!k){
        cout<<"0\n";
        return;
    }
    if(k<=n){
        cout<<"1\n";
        return;
    }
    k -= n;
    for(ll i = n-1, j = 0 ;; j++){
        if(j>0 and j%2==0)i--;
        k -= i;
        if(k<=0){
            cout<<j+2<<"\n";
            return;
        }
    }
}
int main(){
    fast;
    ll t; cin>>t; while(t--)solve();
}

B1, B2(0:04 ~ 1:07, B1 3WA + 1 skipped, B2 1WA)

문제 요약 : 어떤 값 A[i]가 몇 개 있는지에 대한 정보가 n개 주어진다. A[i]와 A[i]+1을 주어진 개수 이하로 더하여 만들 수 있는, m을 넘지 않는 가장 큰 수는? (B1 : 모든 수 개수 합이 최대 20만개, B2 : 어떤 수가 최대 10^9개)

참 할 말이 많은 문제다. 일단 B1을 풀었는데 알고 보니 그게 B2까지 풀리는 풀이였다. B2를 1번 틀린 이유는 B1에서 pretest 통과한 풀이가 사실 틀린 풀이여서 고쳐서 내서 그렇다. 그래서 B1에 skipped가 있다. -> 패널티를 미친듯이 올렸다.

아무튼 풀이 자체는 금방 나왔는데 구체화가 안되서 구현에 시간을 너무 오래 지체했고 여러 번 틀렸다.

풀이

일단 m을 넘지 않고 최대한 A[i]를 많이 쓰자. 그렇게 쓴 상태에서 A[i]+1도 최대한 많이 쓰자. 이제 사용한 A[i] 몇 개를 사용하지 않은 A[i]+1로 바꿀 것이다. 이 때 값은 1 증가하기 때문에 값이 m이 되거나 어떤 한 값이 부족해질 때까지 최대한 많이 바꾸면 된다.

//코드는 B2 기준입니다.
#include <bits/stdc++.h>
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
#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 __int128_t lll;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<P,ll> PP;
void solve(){
    ll n, m; cin>>n>>m;
    map<ll,ll> cnt;
    vector<ll> v(n);
    for(auto &i : v)cin>>i;
    for(int i = 0 ; i < n ; i++){
        ll a; cin>>a; cnt[v[i]]+=a;
    }
    ll ans = 0;
    for(auto [a,c] : cnt){
        ll d = (cnt.contains(a+1) ? cnt[a+1] : 0);
        ll cur = a * min(m/a, c);
        ll x = min((m-cur)/(a+1), d);
        cur += (a+1) * x;
        if(x < d)cur += min(m-cur, min(min(m/a, c),d-x));
        ans = max(ans, cur);
    }
    cout<<ans<<"\n";
}
int main(){
    fast;
    ll t; cin>>t; while(t--)solve();
}

C(1:07 ~ 1:33, 1WA)

문제 요약 : 배열을 오름차순으로 만들기 위해서 어떤 위치의 값을 제곱하는 시행을 할 수 있다. 필요한 최소 시행 수를 출력하거나 불가능하다면 -1을 출력한다.

이 문제랑 거의 똑같이 풀 수 있다. 다만 1:23에 낸 제출이 실수 오차로 WA를 받았는데, 저 문제도 실수를 써서 AC를 받았기 때문에 이 문제도 AC가 될 것이라고 생각하고 1:33에 고쳐서 AC를 받았다.

풀이

일단 1은 제곱해도 1이기 때문에 1보다 큰 수가 1 왼쪽에 있을 경우 불가능하다. 그렇지 않으면 항상 가능한데, 최소 시행 횟수를 알아내보자.

일단 i까지 잘 제곱해서 오름차순이라고 가정하고, 이때 A[i]를 V[i]번 제곱했다고 하자. 그럼 우리가 구해야 할 V[i+1]은 다음을 만족하는 최소의 음이 아닌 정수이다.

$A_{i}^{2^{V_{i}}} \leq A_{i + 1}^{2^{V_{i + 1}}}$

이걸 상용로그랑 밑이 2인 로그를 씌워서 잘 정리하면 O(1)에 V[i+1]을 구할 수 있는 형태가 된다. 실수 오차에 주의하자.

#include <bits/stdc++.h>
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
#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 __int128_t lll;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<P,ll> PP;
void solve(){
    ll n; cin>>n;
    vector<ll> a(n), v(n,1);
    for(auto &i : a){
        cin>>i;
    }
    for(int i = 1 ; i < n ; i++){
        if(a[i]==1 and a[i]<a[i-1]){
            cout<<"-1\n";
            return;
        }
    }
    ll ans = 0;
    for(int i = 0 ; i < n-1 ; i++){
        if(a[i]==1)continue;
        ld a1 = log(a[i]), a2 = log(a[i+1]);
        v[i+1] = v[i] + ceil(log2(a1/a2));
        v[i+1] = max(1LL, v[i+1]);
        ans += v[i+1]-1;
    }
    cout<<ans<<"\n";
}
int main(){
    fast;
    ll t; cin>>t; while(t--)solve();
}

D(upsolved)

문제 요약 : c종류의 알파벳으로 이루어진 문자열이 주어진다. 이 c종류의 알파벳 중 몇 가지를 선택하여 주어진 문자열을 길이가 k 이하인 문자열 여러 개로 분할할 것이다. 이 때 분할된 문자열들의 마지막 글자가 선택한 알파벳 중 하나여야 한다. 최소 몇 개의 알파벳을 선택해야 할까?

진짜 B만 조금 빨리 풀었다면 충분히 대회 시간 내에 풀었을 것 같다.

풀이

몇가지 관찰이 필요하다. 먼저 알 수 있는 자명한 사실은 주어진 문자열의 마지막 문자는 반드시 포함되어야 한다. 이건 나중에 예외 처리할 때 써주면 되고 좀 더 관찰해보면 다음과 같은 사실을 알 수 있다.

주어진 문자열에서 내가 선택한 알파벳은 1로, 아닌 알파벳은 0으로 바꾸자. 이때 연속한 0의 최대 개수가 k 이상이라면 불가능하다는 사실을 알 수 있다. 이를 다시 나타내면 길이가 k인 모든 부분문자열에 대하여 내가 선택한 문자가 하나도 없는 문자열이 존재하면 안된다는 것이다.

이걸 빠르게 계산해보자. 먼저 슬라이딩 윈도우를 써서 길이가 k인 부분문자열이 갖고 있는 알파벳 집합을 비트마스킹으로 나타낸 값을 모두 구하자. 그리고 알파벳을 선택하는 2^c개의 모든 조합을 고려했을 때(이 또한 비트마스킹으로 나타낸다), 미리 구해놓은 비트마스킹 값과 비트가 하나도 안 겹치는 경우가 없을 경우 이 조합은 적절하므로 답을 갱신하면 된다.

이제 미리 구해놓은 비트마스킹 값과 비트가 하나도 안 겹치는 경우가 있는지를 빠르게 구해야 한다. 이건 dp 느낌으로 전처리 해주면 된다.

예를 들어보자. 1001이 있을 때 0100, 0001이 있다면 0100은 1001과 안 겹친다. 그런데 만약 0110이 있었다면 더 판별하기가 쉽다. 왜냐하면 1001의 비트를 반전시키기만 하면 되기 때문이다(O(1)). 그리고 생각해보면 0100은 0110보다 강한 조건이기 때문에 0100이 있다면 0110이 있다고 생각해도 무방할 것이다. 즉 0100이 있을 때 0100보다 약한 모든 비트 값도 다 있다고 가정할 수 있다면 저런 식으로 판별할 수 있다. 즉 X1XX 꼴을 모두 추가해주면 된다. 이걸 naive하게 하면 TLE가 나므로 dp[i] := 비트 상태 i가 존재하는가? 로 정의하여 풀어주면 된다. (더보기의 chk 배열 참조)

#include <bits/stdc++.h>
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
#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 __int128_t lll;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> P;
typedef pair<P,ll> PP;
void solve(){
    ll n, k, c;
    string s; cin>>n>>c>>k>>s;
    vector<bool> chk(1<<c);
    vector<ll> cnt(c);
    for(int i = 0 ; i < k ; i++)cnt[s[i]-'A']++;
    ll cur = 0;
    for(int i = 0 ; i < c ; i++)if(cnt[i])cur |= (1<<i);
    chk[cur] = 1;
    for(int i = k ; i < n ; i++){
        cnt[s[i-k]-'A']--;
        if(cnt[s[i-k]-'A'] == 0)cur &= ~(1<<s[i-k]-'A');
        if(cnt[s[i]-'A'] == 0)cur |= (1<<s[i]-'A');
        cnt[s[i]-'A']++;
        chk[cur] = 1;
    }
    for(int i = 0 ; i < (1<<c) ; i++){
        if(!chk[i])continue;
        for(int j = 0 ; j < c ; j++){
            if(i&(1<<j))continue;
            chk[i|(1<<j)] = 1;
        }
    }
    ll ans = c;
    for(int i = 0 ; i < (1<<c) ; i++){
        if(i&(1<<s.back()-'A')){
            if(!chk[(1<<c)-i-1])ans = min<ll>(ans, __builtin_popcount(i));
        }
    }
    cout<<ans<<"\n";
}
int main(){
    fast;
    ll t; cin>>t; while(t--)solve();
}

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

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

Codeforces Round 987 (Div. 2) (2)	2024.11.15
Educational Codeforces Round 168 (Rated for Div. 2) (0)	2024.07.31
Codeforces Round 930 (Div.2) (+퍼플 달성) (3)	2024.03.01
Codeforces Round 924 (Div.2) (0)	2024.02.11
Codeforces Round 917 (Div.2) (1)	2023.12.25

내 블로그 - 관리자 홈 전환	`Q` `Q`
새 글 쓰기	`W` `W`

글 수정 (권한 있는 경우)	`E` `E`
댓글 영역으로 이동	`C` `C`

이 페이지의 URL 복사	`S` `S`
맨 위로 이동	`T` `T`
티스토리 홈 이동	`H` `H`
단축키 안내	`Shift` + `/` `⇧` + `/`

shjeong

Codeforces Round 961 (Div.2) (코포 복귀전)

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

티스토리툴바

단축키

내 블로그

블로그 게시글

모든 영역

Codeforces Round 961 (Div.2) (코포 복귀전)

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

'codeforces/div2' Related Articles

티스토리툴바

단축키

내 블로그

블로그 게시글

모든 영역