Codeforces Round 736 (Div.2)

A. Gregor and Cryptography

• \(P\mod a=P\mod b\)
• \(2\le a<b\le P\)

를 만족하는 \((a,b)\)쌍 하나를 출력하라는 문제입니다.

\((2,P-1)\)는 크기 조건에 따라 항상 만족하는 해입니다.

B. Gregor and the Pawn Game

체스의 1행과 8행을 따온 상황에서 1행에는 상대 pawn들, 8행에는 우리 pawn들이 있다고 할 때,

퀸을 만들 수 있는(=1행에 도달 가능한) pawn의 개수를 찾는겁니다.

그냥 그리디하게 매칭시켜주면 풀립니다.

string을 통해 비교적 간단하게 구현할 수 있습니다.

void solution() {
    cin >> n;
    string x, y; cin >> x >> y;
    x = " "+x+" ", y = " "+y+" ";
    bool chk[n+2] = {0,};
    int cnt = 0;
    REP(i,1,n) {
        if (y[i] == '1') {
            if (chk[i-1] == false && x[i-1] == '1') chk[i-1] = true, ++cnt;
            else if (x[i] == '0') chk[i] = true, ++cnt;
            else if (chk[i+1] == false && x[i+1] == '1') chk[i+1] = true, ++cnt;
        }
    }
    cout << cnt << '\n';
}

C. Web of Lies

우선, 쿼리간에 정보가 이월되지 않는다는 조건을 주의하세요. 그것 때문에 많이 고생했습니다.

자신보다 값이 큰 놈이 연결되어있으면 무조건 죽습니다.

따라서 outdegree만 관리하면 풀 수 있습니다.

방법만 안다면 구현은 쉽습니다.

D. Integers Have Friends

\(a_i\equiv a_{i+1}\equiv \cdots \equiv a_j\ (mod\ m)\)일 때 "친구 그룹"을 만족합니다.

최대 친구 그룹의 크기를 구하세요.

\(a_i-a_{i+1}\equiv a_{i+1}-a_{i+2}\equiv \cdots \equiv a_{j-1}-a_j\equiv 0\ (mod\ m)\)을 만족하므로,

\(b_k=a_k-a_{k+1}\ (1\le k < n)\)이라 정의하면 \(m|\gcd_{k=i}^{j-1}(b_k)\)를 만족합니다.

따라서 \(m\ge 2\)라는 조건을 만족시키는 경우는 \(\gcd_{k=i}^{j-1}(b_k)\neq 1\)이라는 조건과 동치입니다.

 

따라서 구간 \(\gcd\)가 1이 되지 않는 가장 긴 부분 배열 길이를 구하면 됩니다. 이는 sparse table(업데이트 쿼리가 없기 때문에) 또는 segment tree를 통해 관리할 수 있습니다.

 

가장 긴 부분 배열의 길이를 구하기 위해서는 two-pointers method를 사용하면 됩니다.

\(n=1\)인 경우를 따로 처리하지 않으면 WA 5가 뜹니다. 주의하세요.

 

void solution() {
    int n; cin >> n;
    SegmentTree<ll> gcdtree(n-1,0,[&](ll a, ll b) {return gcd(a,b);});
    REP(i,1,n) cin >> a[i];
    if (n == 1) {
        cout << 1 << '\n';
        return;
    }
    REP(i,1,n-1) gcdtree.update(i,abs(a[i]-a[i+1]));
    int l = 1, r = 1, ans = 0;
    while (r <= n-1) {
        if (gcdtree.query(l,r) == 1) ++l;
        else ans = max(ans,r-l+2), ++r;
    }
    cout << ans << '\n';
}