Codeforces Round #829 (Div.2)

Contest 링크
아니 5솔을 했는데 왜 떨어져??

기껏 C1, C2 풀고 D로 넘어간 게 억울하고, E를 아깝게 못 낸 게 슬프다.

WA 부자

A. Technical Support

어떤 Q에 대응되는 A가 나올 때마다 Q가 해결되는 것이다.
따라서 남은 Q의 개수를 관리하면서 풀면 된다.

그냥 Q의 총 개수와 A의 총 개수를 비교하면 되는 줄 알고 풀었다가 그대로 WA... 어림도 없지...

void solution(int tc) {
    int n; string s;
    cin >> n >> s;
    int q = 0;
    for (char c : s) {
        if (c =='Q') q++;
        else if (q > 0) q--;
    }
    cout << (q == 0 ? "Yes\n" : "No\n");
}

 

B. Kevin and Permutation

$\min$값이 $\lfloor \frac n2 \rfloor$이라고 찍고 맞춰서 잘 배열하면 된다.

처음에는 $\min$값이 5부터 전부 2일 거라고 억측을 해서 WA를 쌓았다. 제발 헛소리 좀 그만 하자...

void solution(int tc) {
    int n; cin >> n;
    if (n%2) {
        rep(i,1,n/2+1) {
            cout << i << ' ';
            if (i != n/2+1) cout << i+n/2+1 << ' ';
        }
    } else {
        rep(i,1,n/2) {
            cout << n/2+i << ' ' << i << ' ';
        }
        cout << el;
    }
}

 

C1. Make Nonzero Sum (easy version)

꽤 까다롭다. 여기서 멘탈이 갈렸다...

$n$이 홀수면 단순히 -1를 출력해주면 된다.

$n$이 짝수일 때는 연속한 두 칸씩 끊어 보면서 얘를 반으로 가를지, 통으로 쓸지 골라주면 된다.

구현에서 꼬일 염려가 좀 있으니 주의... (나만 그럴지도?)

const int N = 2e5+3;
int n, a[N];

void solution(int tc) {
    cin >> n;
    rep(i,1,n) cin >> a[i];
    if (n%2) {
        cout << "-1\n";
        return;
    }
    vector<int> v {1};
    for (int i = 1; i <= n; i += 2) {
        if (a[i] == a[i+1]) {
            v.pb(i), v.pb(i+2);
        } else {
            v.pb(i), v.pb(i+1), v.pb(i+2);
        }
    }
    v.pb(n+1);
    v.erase(unique(v.begin(),v.end()),v.end());
    cout << siz(v)-1 << '\n';
    for (int i = 0; i+1 < siz(v); ++i) {
        cout << v[i] << ' ' << v[i+1]-1 << '\n';
    }
}

 

C2. Make Nonzero Sum (hard version)

C1에 비해 0이 추가되었다.
쉬운데 생각보다 D로 많이들 탈주하셨더라...

앞에 나온 0의 개수의 기우성에 따라서 부호를 바꿔주면 된다.
구현이 짜증나긴 하는데, C1 코드를 수정하면 생각보다 크게 어렵지는 않다.

const int N = 2e5+3;
int n, a[N];

void solution(int tc) {
    cin >> n;
    rep(i,1,n) cin >> a[i];
    if ((n-count(a+1,a+n+1,0))%2) {
        cout << "-1\n";
        return;
    }
    bool zero = 0;
    rep(i,1,n) {
        if (a[i] == 0) zero ^= 1;
        else if (zero) a[i] = -a[i];
    }
    vector<int> v {1};
    for (int i = 1; i <= n;) {
        int f = -1, s = -1, lz = -1;
        for (f = i; f <= n; ++f) if (a[f] != 0) break;
        for (s = f+1; s <= n; ++s) if (a[s] != 0) break;
        for (lz = s+1; lz <= n; ++lz) if (a[lz] != 0) break;
        if (f > n or s > n) break;
        if (a[f] == a[s]) {
            v.pb(f), v.pb(lz);
        } else {
            v.pb(f), v.pb(f+1), v.pb(lz);
        }
        i = lz;
    }
    v.pb(n+1);
    v.erase(unique(v.begin(),v.end()),v.end());
    cout << siz(v)-1 << '\n';
    for (int i = 0; i+1 < siz(v); ++i) {
        cout << v[i] << ' ' << v[i+1]-1 << '\n';
    }
}

 

D. Factorial Divisibility

예제를 보면 감이 좀 잡힌다.
$k!$을 $k+1$번 더하면 $(k+1)!$이 된다는 성질을 이용하면 된다.
만약 $k!$이 $k$개 이하 존재한다면, $\square \times k! + (k+1) \times \bigcirc$ 모양이 되니까 $k+1$로 나눈 나머지가 $0$이 아니게 된다.

구현은 매우 간단하다. 단, m[k+1]에 더할 때 계속 만들어 버리면 안 되니까 0보다 큰지 확인 후 더하기.

const int N = 5e5+3;
int n, x, a[N];
map<int,int> m;

void solution(int tc) {
	cin >> n >> x;
	rep(i,1,n) cin >> a[i], m[a[i]]++;
	for (auto &[k,v] : m) {
		if (v/(k+1) > 0) m[k+1] += v/(k+1);
		v %= k+1;
		if (v != 0 and k < x) {
			cout << "No";
			return;
		}
	}
	cout << "Yes";
}

 

E. Wish I Knew How to Sort

대충 힌트를 보고 찍으면 정답이 보인다.
아마 기댓값의 선형성으로 (한 쌍 정렬 횟수 기댓값)+(나머지 중 한 쌍 정렬 횟수 기댓값)+...이 되는 것 같다.

tistory가 아직 맛이 갔는지 사진이 안 올라간다.

UPD - 용량 큰 사진은 그냥 뱉어내는 거였는데, 못 올린다는 팝업 같은 게 안 떠서 그게 문제일지 몰랐다.

 

using mint = modnum<998244353>;
const int N = 2e5+3;
int n, a[N];

void solution(int tc) {
    cin >> n;
    rep(i,1,n) cin >> a[i];
    int c0 = count(a+1,a+n+1,0), c = 0;
    rep(i,1,c0) if (a[i] == 1) c++;
    mint x = ll(n)*(n-1)/2, ans = 0;
    rep(i,1,c) ans += x/i/i;
    cout << ans << el;
}