Codeforces #619

A. Three Strings

Problem - A - Codeforces

Problem - A - Codeforces

길이 \(n\)의 문자열 \(a, b, c\)가 주어진다.

\(a\)의 \(i\)번째 문자를 \(a_i\)라고 하자. (\(b_i, c_i\)도 동일하게 정의)

\(i(1\le i \le n)\)에 대해, \(c_i\)를 \(a_i\) 또는 \(b_i\)와 바꾼다.

모든 swap이 끝났을 때 \(a\)와 \(b\)가 같아질 수 있으면 YES를, 그렇지 않으면 NO를 출력한다.

 

\(c_i \ne a_i\) && \(c_i \ne b_i\)를 만족하는 \(i\)가 존재하면 NO이다.

#include <bits/stdc++.h>
using namespace std;
 
int main(void) {
    int t; cin >> t;
    while (t--) {
        string a, b, c;
        cin >> a >> b >> c;
 
        int len = a.size();
        bool flag = true;
        for (int i = 0; i < len; i++) {
            if (a[i] != c[i] && b[i] != c[i]) {
                flag = false;
                break;
            }
        }
        cout << (flag ? "YES\n" : "NO\n");
    }
    return 0;
}

 

 

B. Motarack's Birthday

Problem - B - Codeforces

Problem - B - Codeforces

배열 \(a\)는 \(n\)개의 non-negative integer로 구성된다.

\(a_i\)가 \(-1\)이면 \(i\)번째 숫자가 사라졌음을 의미한다. (적어도 하나의 \(-1\)이 주어진다.)

배열 \(a\)에서 인접한 두 숫자의 차가 최소가 되도록 만들어야 한다.

 

1) 인접한 두 숫자가 모두 \(-1\)이 아닌 경우
\(d = max(d, abs(a_i - a_{i-1}))\)
2) 인접한 두 숫자가 모두 \(-1\)인 경우
계산할 필요 없음
3) 인접한 두 숫자 중 하나가 \(-1\)인 경우
\(-1\)이 아닌 숫자를 배열 \(b\)에 추가한다.

배열 \(b\)가 비어있을 경우, 답은 \(0\)이다.

배열 \(b\)가 비어있지 않을 경우, 답은 \(max(d, \frac{b_{max} - b_{min} + 1}{2})\)이다.

#include <bits/stdc++.h>
using namespace std;
 
int main(void) {
    int t; cin >> t;
    while (t--) {
        int n; cin >> n;
        int diff = 0;
        vector<int> a;
        vector<int> v(n);
        cin >> v[0];
        for (int i = 1; i < n; i++) {
            cin >> v[i];
            if (v[i] != -1 && v[i-1] != -1) {
                diff = max(diff, abs(v[i] - v[i-1]));
            }
            else if (v[i] == -1 && v[i-1] == -1) {
                continue;
            }
            else {
                a.push_back(v[i] ^ v[i-1] ^ (-1));
            }
        }
        if (a.empty()) {
            cout << 0 << ' ' << 0 << '\n';
        }
        else {
            int mx = *max_element(a.begin(), a.end());
            int mn = *min_element(a.begin(), a.end());
            int ans = max(diff, (mx - mn + 1) / 2);
            cout << ans << ' ' << (mx + mn) / 2 << '\n';
        }
    }
    return 0;
}

 

 

C. Ayoub's function

Problem - C - Codeforces

Problem - C - Codeforces

\(s\)가 binary string일 때, \(f(s)\)는 \(s\)의 substring 중 적어도 하나의 \(1\)을 포함하는 substring의 개수이다.

\(s\)의 길이와 \(s\)에 포함된 \(1\)의 개수가 주어졌을 때, \(f(s)\)의 최댓값을 구하는 문제이다.

 

\(s\)의 전체 substring 개수에서 \(0\)으로만 이루어진 substring들의 개수를 빼면 된다. (여사건)

참고: 길이 \(n\)인 문자열의 substring 개수 = \(\frac{n(n+1)}{2}\) (단, substring이 empty string인 경우 제외)

 

\(f(s)\) 최대가 되려면 \(0\)이 최대한 골고루 퍼져 있어야 한다.

\(\iff\) \(0\)으로만 이루어진 구간의 최대 길이가 최소가 되어야 한다.

ex) \(0\)이 5개, \(1\)이 2개인 경우: \(0010010\)

 

pf) \(\frac{n(n+1)}{2} + \frac{m(m+1)}{2} < \frac{(n+m)(n+m+1)}{2}\)

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
 
ll f(ll k) {
    return k * (k + 1) / 2;
}
 
int main(void) {
    int t; cin >> t;
    while (t--) {
        ll n, m;
        cin >> n >> m;
        ll q = (n - m) / (m + 1);
        ll r = (n - m) % (m + 1);
        cout << f(n) - f(q+1) * r - f(q) * (m + 1 - r) << '\n';
    }
    return 0;
}

 

 

D. Time to Run

Problem - D - Codeforces

Problem - D - Codeforces

간선을 최대 한 번씩만 사용하면서 \(k\)킬로미터를 이동할 수 있는지 묻는 문제이다.

\(k \gt 4nm - 2n - 2m\)이면 이동이 불가능하다.

\(k \le 4nm - 2n - 2m\)이면 아래 그림과 같은 방법으로 \(k\)킬로미터를 이동할 수 있다.

 

#include <bits/stdc++.h>
using namespace std;
 
int main(void) {
    int n, m, k, f;
    cin >> n >> m >> k;
 
    if (k > 4*n*m - 2*n - 2*m) {
        cout << "NO\n";
        return 0;
    }
    else {
        cout << "YES\n";
    }
    
    n--; m--;
    if (m == 0) {
        cout << (n >= k ? 1 : 2) << '\n';
        cout << min(n, k) << " D\n";
        k -= min(n, k);
        if (!k) return 0;
        cout << min(n, k) << " U\n";
        return 0;
    }
 
    vector<pair<int, string> > v;
    v.reserve(3002);
 
    // R -> L
    v.push_back({min(k, m), "R"});
    k -= min(k, m);
 
    if (!k) goto ed;
    v.push_back({min(k, m), "L"});
    k -= min(k, m);
 
    // D -> R -> UDL
    while (n-- && k) {
        if (!k) goto ed;
        v.push_back({1, "D"});
        k--;
 
        if (!k) goto ed;
        v.push_back({min(k, m), "R"});
        k -= min(k, m);
 
        if (!k) goto ed;
        if (min(k/3, m)) {
            v.push_back({min(k/3, m), "UDL"});
            k -= min(k/3, m) * 3;
        }
        else {
            string s = "UDL";
            v.push_back({1, s.substr(0, k)});
            k = 0;
        }
    }
 
    // U
    if (!k) goto ed;
    v.push_back({k, "U"});
 
    ed:
    cout << v.size() << '\n';
    for (const auto& [num, path]: v) {
        cout << num << ' ' << path << '\n';
    }
    return 0;
}

 

 

E. Nanosoft

Problem - E - Codeforces

Problem - E - Codeforces

 

 

 

F. Super Jaber

Problem - F - Codeforces

Problem - F - Codeforces