[CF] Codeforces Round #806 (Div. 4)

https://codeforces.com/contest/1703

Dashboard - Codeforces Round #806 (Div. 4) - Codeforces

G도 업솔빙하자!

그린 갔습니당!

A. YES or YES? (00:02)

(s[0]=='y' || s[0]=='Y') && (s[1]=='e' || s[1]=='E') && (s[2]=='s' || s[2]=='S') 인지를 확인해 풀었다.

B. ICPC Balloons (00:05)

주어진 문자열의 각각의 문자를 순회하면서, 처음 나온 알파벳이면 답에 +2, 아니면 +1을 해서 답을 출력하면 된다.

C. Cypher (00:17)

A, B까지는 속도감 있게 빨리 풀었던 것 같은데, 점수를 더 높이려면 이 문제를 10분 정도에 풀었으면 좋겠다는 생각이 들었다.

영어로 된 문제 지문을 정확하고 빠르게 읽는 능력도 중요한 것 같다. 처음에 문제를 반대로 읽었어서 약간 헤맸던 점이 아쉽다.

내가 출력해야 하는 것을 해당 명령을 시행한 결과를 구하는 것으로 착각했기 때문이다. "the initial sequence of the cypher"

이 어구의 의미를 빠르게 파악했어야 했다. 내가 출력해야 하는 것은 해당 명령을 시행하기 전의 상태였다.

 

U연산이 나오면 암호 숫자를 하나 빼고, D연산이 나오면 암호 숫자를 하나 더하는 구현 문제였다.

0~9 숫자들만 나오도록 처리도 해줘야 한다.

D. Double Strings (00:39)

이 문제는 어떤 문자열을 쪼갰을 때, 쪼갠 부분 문자열이 모두 존재하는지 판단하는 문제이다. 이 문제를 풀 수 있었던 가장 큰 힌트는 문자열을 오직 2개로 쪼갠다는 점이다.

0번~i번 문자까지의 부분 문자열의 존재 && i+1번~(문자열 길이-1)번까지의 부분 문자열 존재가 참이면 1, 아니면 0을 출력하면 된다.

부분 문자열이 존재하는지를 판단할 때에는 C++의 map을 이용하면 된다.

E. Mirror Grid (01:09)

왼쪽 위 사분면을 기준으로 (i, j)는 (j, n-1-i), (n-1-j, i), (n-1-i, n-1-j)로 돌아가므로, 이 4개의 지점마다 0, 1의 개수를 세주고, 답에 더 작은 것의 개수를 추가하면 된다. 

F. Yet Another Problem About Pairs Satisfying an Inequality (01.30)

\( a[i]<i<a[j]<j (1 \leq i, j \leq n)\) 쌍의 개수를 구하는 문제이다.

 

일단 내 풀이부터 정리해보겠다.

1. 일단 \( a[i]<i \)를 만족하는 i를 미리 찾아서 따로 배열 b[i]에 만족하면 true로 표시해놓는다. 이제 미리 찾아놓은 i 중 서로 다른 2개를 고르면 되는 문제로 바뀐다. 고를 때에 \( i<a[j] \)를 만족하기만 하면 된다. 

2. a[i]<i 이고 i<=x (1 <= x <= n)인 i의 개수를 따로 배열 c[x]에 저장한다. c[x]는 prefix sum으로 만들어 줄 수 있다.

이때, 답은 c[a[i]-1]의 합 (1<=i<=n, b[i]==true, a[i]-1>0)이다. 

 

에디토리얼을 보면 2. 부분을 lower_bound()를 통해 해결하는 풀이를 볼 수 있다. \( a[i]<i \)를 만족하는 i를 오름차순으로 순회하면서 답답에 lower_bound(v.begin(), v.end(), a[i])-v.begin() 를 추가해주고, 이후 i를 벡터 v 뒤에 추가해주면 풀 수 있다.

여기서 lower_bound()의 리턴 값이 iterator임을 알고 v.end()를 빼서 a[i]보다 작은 수들의 개수를 구할 수 있음을 까먹지 말고 배워가자.

G. Good Key, Bad Key (upsolved)

스스로 풀지 못해서 에디토리얼 보고 배웠다. 

bad key를 사용한 이후에는 무조건 bad key만 사용하는 것이 무조건 최대 코인을 얻을 수 있다.

i번째에 bad key, i+1번째에 good key를 사용했다면 얻는 코인은 a[i]/2 + a[i+1]/2 - k,

i번째에 good key, i+1번째에 bad key를 사용했다면 얻는 코인은 a[i] + a[i+1]/2 - k,

이므로 무조건 후자가 더 많은 코인을 얻을 수 있다. 

그러면 이제 언제 good key만 쓰다가, bad key만 쓸지를 모두 조사해서 그 중 최대 코인을 출력하면 된다.

 

아래는 G번 코드이다.

#include <bits/stdc++.h>
#define ll long long int
#define pll pair<ll, ll>
#define pii pair<int, int>
#define X first
#define Y second
using namespace std;
int dx[]={-1, 1, 0, 0};
int dy[]={0, 0, -1, 1};
void solve()
{
    ll n, k, ans=0, sum=0; cin>>n>>k;
    vector<ll> a(n);
    for(ll i=0;i<n;i++) cin>>a[i];
    for(ll i=-1;i<n;i++) //i까지 good key만 사용
    {
        ll now=sum;
        //1e9도 2로 30번 나누면 무조건 0이 되므로, 이 for문이 n-1-i번 돌아가게 하면 시간 복잡도, 값 둘다 엉망이 된다. 따라서 최대 30번 돌린 후에는 나오면 된다.
        for(ll j=i+1;j<min(n, i+31);j++) 
        {
            ll tmp=a[j];
            tmp>>=(j-i);
            now+=tmp;
        }
        if(now>ans) ans=now;
        if(i+1!=n) sum+=a[i+1]-k;
    }
    cout<<ans<<'\n';
}
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    int tc=1; cin>>tc;
    while(tc--) solve();
    return 0;
}

위 코드에서 주의할 점은

shift 연산(>>)을 너무 많이 하면 값, 시간 복잡도 모두 엉망이 되므로, n의 최대인 1e9도 2로 30번 나누면 0이 되므로, shift 연산을 최대 30번만 하도록 해야한다.

 

위 코드에서 새로 배워갈 점은

shift 연산을 통해 *2^x 또는 /2*x (x = 2를 곱하거나 나눌 횟수)를 간편하게 할 수 있다는 점이다.

 

오늘 하루 코포 글 2개 쓰다가 놀고, 쓰다가 놀고 하면서 하루 동안 백준 실버 1문제, 코포 업솔빙만 했다. 내일은 이분 그래프, 최단 경로 연습문제들 몇 개 풀어보면서 익숙해져 봐야겠다. 신촌 연합 세그먼트 트리 남은 연습문제 2개도 풀어야 되는데...