코드포스 - 업솔빙 몰아서 함

codeforce round #808(div 2), #803(div 2, virtual) 업솔빙

Codeforces Round #808, #803 개요

일단 지금 808 보고 난 직후 이고 역시나 2솔ㅠㅠ
c, d만 몰아서 업솔빙 해볼 것이다. 이번 808은 너무 힘들었다.
A가 잟안 풀려서 B를 해야하나 A를 해야하나 고민도 많이 됐고, 낼 때마다 WA를 받아서 내 멘탈도 Wa르르였다.
다행이 1시간 넘긴했지만 풀어서 다행이지 안그랬으면 100점이상 떨굴뻔했다. ㅠㅠ
원래 809를 진행하고 몰아서 할라고 했지만.. 건강검진 이슈로 809를 못봐서 버추얼로 803을 해보았다.
허나 의지가 박약하여 A, B 풀고 C풀다가 안되니깐 걍 포기했다 ㅋㅋㅋ
단식 중이라 배고파서 집중이 안된다(핑계임)

808 A. Difference Operations(1:25)

B보다도 늦게 풀었따. ㅋㅋㅋ
진짜 멘탈이 중요하단 걸 느꼈다.
A를 못풀면 다른게 안잡힌다.
600점 짜리를 맞았는데 150점이 오르는 기적같은 일이 일어났다. ㅋㅋㅋ
처음에는 인접한 배열을 뺀 값을 저장해서 관리했는데 그게 답이 없었나보다.
1시간 뒤에 그냥 배열 자체를 조작해보니 첫번째 배열요소만 중요하단걸 알았다.

int n; cin >> n;
arr  = vector<ll> (n+1);
bool ok = true;
for(int i=1;i<=n;i++){
    cin >> arr[i];
    if(i!=1&&!arr[i-1]&&arr[i]) ok = false;
    if(arr[i-1]>0&&arr[i]%arr[i-1]) ok = false;
    if(arr[i-1]) arr[i] = arr[i-1];
}
if(ok) cout << "YES\n";
else cout << "NO\n";

808 B. Difference of GCDs(1:18)

이건 직관은 빨리 얻었는데 구현하다가 잔실수가 너무 많았다.
배수인것만 확인하면 되는데 이상한 gcd를 구했다.(제목에 낚인건가..?)
머리와 손이 따로 논것이다.
그래도 이문제를 AC받으면서 멘탈이 조금 회복된듯 하다.

bool ok = true;
for(int i=1;i<=n;i++){
    int a = (l/i);
    int b = a*i;
    while(b<l) b+=i;
    if(b>r){
        ok = false;
        break;
    }
    res.push_back(b);
}

808 C. Doremy’s IQ(upsolving)

A, B를 푸니 30분남았었고 이건 아이디어라도 떠올려보자 하고 열심히 봤다.
규칙은 참 쉬운데.. 정렬로 일단 접근했다.
공짜로 참여할 수 있는건 대부분 참여하는게 이득이니까 대충 정렬 후 그리디 아닐까? 한것이다.
얼마전에 #805 에서 풀었던 good key, bad key문제랑 은근히 비슷해 보였기 때문이다.
결론은 뒤에서 부터 그리디하게 해결이 가능하다.
iq가 0인것부터 거꾸로 거슬로 올라가는 것이다… 아 그리디는 어렵고 재밌다.

int n, iq;
cin >> n >> iq;
for(int i=1;i<=n;i++) cin >> a[i];
int Q= 0;
for(int i=n;i>=1;i--){
    if(a[i]<=Q) res[i] = 1;
    else if(Q<iq){
        Q++;
        res[i] = 1;
    }else res[i] = 0;
}
for(int i=1;i<=n;i++) cout << res[i];
cout << '\n';

808 D. Difference Array(upsolving)

문제 그대로 구현한다고 하면 인접한거 다 빼고(N)* 정렬하고(NlogN) * 그걸 N번 반복하니까 N^3logN의 시간복잡도가 걸릴것이고 이는 당연히 시간 초과다.
모든 구간을 정렬하는게 아니라 일부분만 정렬해서 한번의 연산에 끝내는게 중요하다.

for(int i=1; i<=n;i++) cin >> arr[i];
for(int i=n-1;i>=1;i--){
    int last = arr[i+1];
    bool ok = false;
    for(int j=i;j>=1;j--){
        if(arr[j]==0) ok = true;
        arr[j] = last-arr[j];
        last -= arr[j];
        if(ok){
            sort(arr+j, arr+i+1);
            break;
        }
    }
    if(!ok) sort(arr+1, arr+i+1);
}
cout << arr[1]<<'\n';

803 A. XOR Mixup(0:04)

XOR 연산은 재밌다.
내가 좋아하는 문제고 전체 다 XOR한거에 하나씩 XOR하면서 비교하면 끝.
모든 문제에 XOR연산만 나오면 좋겠다.

803 B. Rising Sand(0:22)

꽤 오래걸린 문제이다.
10분 넘게 생각하고 나서야 k가 1이 아니라면 연산을 통해 결과를 바꿀 수 없다는 걸 알아냈다.
따라서 k=1인 경우만 예외처리하면 된다.

 cin >> n >> k;
sands = vector<int> (n+1);
for(int i=1;i<=n;i++) cin >> sands[i];
int res = 0;
for(int i=2;i<=n-1;i++){
    if(sands[i]>sands[i-1]+sands[i+1]) res++;
}
        
if(k==1){
    cout << (n-1)/2 << '\n';
}else{
    cout << res << '\n';
}

803 C. 3SUM closure(upsolving)

모든 경우를 검사하기는 당연히 무리고 계속 해보니 양수인게 3개가 넘어가면 절대 안된다.
왜냐면 그것만으로 계속해서 새로운 뭔가가 생기니까 문제가된다.
여기까진 알아냈는데.. 그래서 어쩌지 하다가 버추얼이라서 생각하기가 귀찮아져서 걍 플스하러 갔다.ㅠㅠ
에디토리얼 보니까 생각은 맞았더라 근데 여기서 범위를 줄여서 브루트포스를 했다.
난 뭔가 딱 떨어지는 문제들만 많이 풀어서 그런지 이런식으로 범위를 줄여서 검사하는 생각을 잘 못하는것같다.
음수 최대 2개 양수 최대 2개 0도 최대 2개로 6개를 모두 검사하면 된다 해봐야 6의 3승이다.

int n, iq;
cin >> n >> iq;
for(int i=1;i<=n;i++) cin >> a[i];
int Q= 0;
for(int i=n;i>=1;i--){
    if(a[i]<=Q) res[i] = 1;
    else if(Q<iq){
        Q++;
        res[i] = 1;
    }else res[i] = 0;
}
for(int i=1;i<=n;i++) cout << res[i];
cout << '\n';

803 D. Fixed Point Guessing(upsolving)

코드포스를 할거라면 interactive문제는 알아둬야할 것 같다.
이건 그냥 어떻게 해야할 지 몰라서 답을 봤다.
interactive문제는 그냥 믿고 입력을 받으면 되는 구나 싶었다.
assert문의 필요성도 배웠다.
대충 문제는 이해했는데 idleness limit error가 떠서 빡쳐서 접었다.