Codeforces Round #752 (Div. 2)

이번에 CR#752에서 314등으로 퍼플퍼포가 되었고, +110이 되어 코드포스 블루에 드디어 도달했습니다.

아무래도 운이 많이 따른 라운드인 것 같습니다. D는 그냥 수학문제였고, C는 나이브로 풀었지만 시스텟에서 다행히도 TLE가 나지 않았습니다(아니면 TLE날 데이터가 원초 없었을 지도 모르겠네요).

 

이대로 끝내기는 뭐하니까 이미 에디토리얼은 나왔지만 그냥 풀이를 쓰겠습니다.

 

 

A. Era

$a[i]-i$의 max를 찾으면 끝나는 문제입니다.

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    while(T--) {
        int n, a[101], m=0;
        cin >> n;
        for(int i=1; i<=n; i++) cin >> a[i];
        for(int i=1; i<=n; i++) m=max(m, a[i]-i);
        cout << m << "\n";
    }
}

 

B. XOR Specia-LIS-t

$n$이 짝수이면 그냥 1개씩의 배열로 쪼개면 해답이 0이 나옵니다.

$n$이 홀수이며 $\{a\}$가 증가수열일 시, 어떻게 잘라도 전체 XOR값의 $2^0$자릿수는 1이 되어 불가능합니다. 증가수열이 아닐 시에는 감소하는 부분 수열 $\{a_i,\ a_{i+1}\}$를 고를 수 있고, 이 두 원소를 뺀 나머지를 한 개씩의 배열로 쪼개면 답이 0이 나와 성립합니다.

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    while(T--) {
        int n, a[100001];
        cin >> n;
        for(int i=0; i<n; i++) cin >> a[i];
        if(!(n%2)) cout << "YES\n";
        else {
            int k=0;
            for(int i=1; i<n; i++) if(a[i]<=a[i-1]) k=1;
            if(k) cout << "YES\n";
            else cout << "NO\n";
        }
    }
}

 

C. Di-visible Confusion

정해가 생각이 안 나서 naive하게 $O(N^2)$에 짰습니다.

$1\leq i \leq n$인 모든 정수 $i$에 대해 $a_i$가 $2\leq x \leq i+1$을 만족하는 어떤 정수 $x$의 배수라면 가능합니다(너무 자명하여 설명은 하지 않겠습니다).

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    while(T--) {
        int n, a[100001];
        bool k=1;
        cin >> n;
        for(int i=1; i<=n; i++) cin >> a[i];
        for(int i=1; i<=n; i++) {
            int j;
            for(j=2; j<=i+1; j++) if(a[i]%j) break;
            if(j==i+2) {k=0;break;}
        }
        if(k) cout << "YES\n";
        else cout << "NO\n";
    }
}

 

D. Moderate Modular Mode

그냥 수학문제.

입력으로 주어지는 $x,\ y$의 크기 조건에 따라 나누어 풀면 됩니다.

$x>y$일 땐, $n=x+y$이면 $x+y \ \mathrm{mod} \ x=y=y\ \mathrm{mod}\ n$이므로 성립합니다.

$x=y$일 땐, $n=x$이면 두 값이 모두 0이 되어 성립합니다.

$x<y$일 때 $x,\ y$가 모두 짝수이므로 $x=2p,\ y=2q$라 하고, $a=\left [ \frac{q}{p} \right ]$라 할 때 $n=ap+q$이면 $n\ \mathrm{mod}\ x=q-ap$ ($ap\leq q<(a+1)p$이므로)이며, $y\ \mathrm{mod}\ n=2q\ \mathrm{mod}\ ap+q=q-ap$가 되어 성립합니다.

#include <bits/stdc++.h>
using namespace std;
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int T;
    cin >> T;
    while(T--) {
        long long x, y;
        cin >> x >> y;
        if(x>y) cout << x+y << "\n";
        else if(x==y) cout << x << "\n";
        else {
            long long p=x/2, q=y/2;
            long long a=q/p;
            cout << a*p+q << "\n";
        }
    }
}