코드포스 - 또 3솔의 벽

codeforce round #807(div 2) 업솔빙

Codeforces Round #807 개요

하… 진짜 미칠 것 같다 이번엔 A, B를 20분 만에 풀어서 2시간동안 한 문제만 풀어도 3솔의 벽을 깨는 건데…
그걸 못했다. 2시간동안 C,D하나 풀기를…ㅠㅠ
이쯤 되면 이번 방학 목표를 코드포스 3솔로 바꿔야 할 것 같다.(원래 블루였음ㅋㅋ)
내 생각보다 블루, 퍼플이 엄청 대단한 사람들이란걸 몸소 느낀다.

A. Mark the Photographer(0:05)

정렬하고 반 나눠서 연산하면 바로 끝이다.
근데 n이 주어지고 n/2가 주어지는게 아니라 이미 절반을 한 값을 준다는 특징이 있었다.
그래서 좀 어버버하다가 5분에 AC

int n, x; cin >> n >> x;
vector<int> height(2*n+1);
for(int i=1;i<=2*n;i++) cin >> height[i];
sort(height.begin(), height.end());
bool possible = true;
for(int i=1;i<=n;i++){
    if(height[i+n]-height[i]<x) possible = false;
}
if(possible) cout << "YES\n";
else cout << "NO\n";

B. Mark the Dust Sweeper(0:18)

이 문제까진 꽤 느낌이 좋았다.
왜냐면 내가봐도 좀 잘풀었기 때문이다.
먼지를 뒤로 모는 문제고 0이 중간에 껴있는경우 턴을 좀 더 써야한다.
그래서 스위핑으로 끝점 빼고 먼지+추가적인 턴을 더해서 단 3줄로 끝냈다.

 int n; cin >>n;
rooms = vector<ll> (n+1);
ll res = 0;
for(int i=1;i<=n;i++){
    cin >> rooms[i];
    if(i!=n) res += rooms[i];
    if(!rooms[i]&&res&&i!=n) res++;
}
cout << res << '\n';

C. Mark and His Unfinished Essay(upsolving)

마크한테 실망했다. substr문제인가 하고 보니 쿼리의 범위가 long long형까지 갔다..
당연히 메모리 초과 날걸 알았지만 해봤고 역시 메모리 초과가 났다.
그렇다면 연산으로 역추적? 을 해야하는데 그게 생각이 1도 안났다.
string이 계속 바뀌는데 어케 역추적을 해야하지..라는 생각을 하다가 시간 다쓰고 망했다.
첫 글자랑 위치만 저장해볼까 했는데 그게 string이 바뀌니깐 너무 곤란했다. ㅠㅠ
에디토리얼 보니 비슷하다..다만 왼쪽 오른쪽 복사된 idx만 저장하는게 아니라 diff라는 이름의 배열로 왼쪽 시작점-왼쪽 쿼리시작점을 뺀것을 저장한다.
이것의 의미는 바로 이전 시작점인것이다.
왜 이걸 못했을까…?
솔직히 좀 좋은 문제였다.

for(int i=0;i<q;i++){
    ll k; cin >> k;
    k--;
    for(ll j=c;j>=1;j--){
        if(k<left[j]) continue;
        k -= diff[j];
    }
    cout << str[k] << '\n';
}

D. Mark and Lightbulbs(upsolving)

C보다 이게 더 나을 것 같아서 꽤 오래 본 문제이지만 어..이건가?? 하는데 반례가 계속 나왔다 ㅠㅠ
일단 하나의 전구를 바꿀 수 있어서 그걸 바꾸면 그 양옆의 상태가 변한다는 특징이 있었다.

모든 상태를 변화시킬 수 없을 때
양 끝은 어짜피 바꿀 수 없는데 양끝이 다를 때 이 두 경우가 -1을 출력하는 경우라고 생각하고 문제를 풀었다.
핵심은 구간을 한칸씩 옮길 수 있다는 것이고 이를 계산 할 때
- abs(l-l’)+abs(r-r’)

이런 식으로 계산 할 수 있다는 것이다.

ll n, c,q;
int main(){
    fast_io;
    int test; cin >> test;
    while (test--) {
        int n; cin >> n;
        string s1, s2;
        cin >> s1 >> s2;
        bool ok = true;
        if(s1[0]!=s2[0]||s1[n-1]!=s2[n-1]) ok = false;
        vector<int> pos1, pos2;
        for(int i=0;i<n-1;i++){
            if(s1[i]!=s1[i+1]) pos1.push_back(i);
            if(s2[i]!=s2[i+1]) pos2.push_back(i);
        }
        if(pos1.size()!=pos2.size()) ok = false;
        
        if(ok){
            ll res = 0;
            for(int i=0;i<pos1.size();i++){
                res += abs(pos1[i]-pos2[i]);
            }
            cout << res << '\n';
        }else{
            cout << -1 << '\n';
        }
    }
}

코드포스 - 또 3솔의 벽

codeforce round #807(div 2) 업솔빙

Codeforces Round #807 개요

A. Mark the Photographer(0:05)

B. Mark the Dust Sweeper(0:18)

C. Mark and His Unfinished Essay(upsolving)

D. Mark and Lightbulbs(upsolving)

Leave a comment

2024

2023

2022