Codeforces Round #685 (Div. 2)

A - Subtract or Divide

Problem - A - Codeforces

\(n\)이 주어진다.

최소한의 연산횟수로 \(n\)을 \(1\)로 만들어야 한다. 사용할 수 있는 연산은 다음과 같다.

 

1. \(n\)의 진약수로 \(n\)을 나눈다.

2. 1을 뺀다.

 

 

\(n\)이 짝수라면, \(\frac n2\)로 나누어 2로 만든 다음 1을 빼면 된다.

\(n\)이 홀수라면, 1을 빼서 짝수로 만든다음 짝수에서 쓰는 방법을 사용하면 된다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        ll n; cin >> n;
        if (n == 1) cout << "0\n";
        else if (n == 2) cout << "1\n";
        else if (n == 3) cout << "2\n";
        else if (n % 2 == 0) cout << "2\n";
        else cout << "3\n";
    }
}

---

B - Non-Substring Subsequence

Problem - B - Codeforces

\(n\)길이의 문자열 \(s\)가 주어진다.

 

각 쿼리마다 \(s\)에 다음을 만족하는 부분수열이 존재하는지 여부를 알아내야 한다.

1. 이 부분수열과 부분문자열 \(s[l..r]\)이 동일하다.

2. 이 부분수열은 연속이 아니다.

 

 

위를 만족하는 부분수열이 존재하고, 이 부분수열의 맨 앞 인덱스를 \(i\), 맨 뒤 인덱스를 \(j\)라고 하자.

그러면 \(i < l\) 또는 \(r < j\)를 만족해야 한다는 사실을 알 수 있다.

 

따라서 인덱스 \(l\) 왼쪽에 \(s[l]\)과 같은 문자가 존재하는지,

또는 인덱스 \(r\) 오른쪽에 \(s[r]\)과 같은 문자가 존재하는지 확인하면 된다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
int n, q;
string s;
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n >> q;
        cin >> s;
 
        while (q--)
        {
            bool ans = false;
            int l, r; cin >> l >> r; l--, r--;
            for (int i = 0; i < l; i++) if (s[i] == s[l]) ans = true;
            for (int i = r + 1; i < n; i++) if (s[i] == s[r]) ans = true;
 
            if (ans) cout << "YES\n";
            else cout << "NO\n";
        }
    }
}

---

C - String Equality

Problem - C - Codeforces

\(n\)길이의 두 문자열 \(a,b\)가 주어지고, 정수 \(k\)가 주어진다.

 

\(a\)에 다음과 같은 연산을 사용해 \(b\)로 만들 수 있는지 알아내야 한다.

 

1. \(a_i\)와 \(a_{i+1}\)을 바꾼다.

2. \(k\)길이의 부분 문자열이 모두 같은 문자 \(c\)로 이루어져 있다면, 이를 모두 \(c+1\)로 바꾼다.

 

 

1번 연산은 우리가 \(a\)에 있는 문자를 원하는 대로 재배열할수 있음을 말한다.

따라서 \(a\)와 \(b\)를 정렬한다음, \(a\)를 2번 연산을 이용해 \(b\)로 바꿀 수 있는지 확인하면 된다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
int n, k;
string a, b;
 
int cnta[27], cntb[27];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n >> k;
        cin >> a >> b;
 
        bool ans = true;
 
        memset(cnta, 0, sizeof cnta);
        memset(cntb, 0, sizeof cntb);
 
        for (char c : a) cnta[c - 'a']++;
        for (char c : b) cntb[c - 'a']++;
 
        for (int i = 0; i < 26; i++)
        {
            if (cntb[i] > cnta[i])
            {
                ans = false;
                break;
            }
 
            int d = cnta[i] - cntb[i];
            if (d % k)
            {
                ans = false;
                break;
            }
 
            cnta[i] -= d;
            cnta[i + 1] += d;
        }
 
        if (ans) cout << "Yes\n";
        else cout << "No\n";
    }
}

---

D - Circle Game

Problem - D - Codeforces

두 사람이 좌표평면 위에서 게임을 하려고 한다.

좌표 \((0,0)\)에 점이 있고, 두 사람은 자신의 차례에 x좌표가 증가하는 방향 또는 y좌표가 증가하는 방향으로 \(k\)만큼 이동해야 한다.

단, 원점에서부터의 거리가 \(d\)보다 먼 점으로는 이동할 수 없다.

 

\(d, k\)가 주어지고, 더 이상 점을 이동시킬 수 없는 사람이 패배한다고 할 때 누가 이길지 알아내야 한다.

 

 

두 사람 모두 상대편의 선택을 반대로 선택함으로써, 최대한 정 대각선 방향으로 점을 이동시킬 수 있음을 알 수 있다.

이 때 최종 위치를 \((s, s)\)라고 하자.

이 위치에서 더 이상 갈 곳이 없으면 후공이, 그렇지 않으면 선공이 승리한다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
ll d, k;
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> d >> k;
 
        ll a = ((ll)(double(d) / sqrt(2))) / k;
        ll b = ((ll)sqrt(d * d - a * k * a * k)) / k;
 
        if ((a + b) % 2) cout << "Ashish\n";
        else cout << "Utkarsh\n";
    }
}

---

E - Bitwise Queries (Hard Version)

Problem - E2 - Codeforces

\(n\)길이의 배열 \(a\)가 주어진다.

배열의 각 원소가 \(0 \le a_i \le n-1\)를 만족한다고 할 때, \(n+1\)개의 쿼리를 이용해 배열을 복원해 내야 한다.

 

사용할 수 있는 쿼리는 다음과 같다.

 

1. AND i j : \(a_i\) AND \(a_j\)를 반환한다. 
2. OR i j : \(a_i\) OR \(a_j\)를 반환한다. 
3. XOR i j : \(a_i\) XOR \(a_j\)를 반환한다.

먼저 \(n-1\)개의 쿼리를 이용해, \(a_i\) XOR \(a_{i+1}\)를 계산해 놓자.

그러면 다음과 같은 2가지 상황으로 나눌 수 있다.

1. 서로 같은 두 원소 \(a_i\)와 \(a_j\)가 존재한다.
그러면 AND 또는 OR 쿼리로 \(a_i\)의 값을 알아낼 수 있고, 나머지 원소는 계산해놓은 XOR값을 이용해 알 수 있다.

2. 서로 같은 두 원소가 존재하지 않는다.
그러면 이 배열에 \(a_i\) XOR \(a_j\) = \(n-1\)을 만족하는 두 원소가 무조건 존재함을 알 수 있다.

 

(\(a_k\) AND \(a_i\)) OR (\(a_k\) AND \(a_j\))을 계산함으로써 \(a_k\)의 값을 알아낼 수 있고, 나머지 원소는 역시 계산해놓은 XOR값을 이용해 알 수 있다.

 

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
 
ll gcd(ll a, ll b) { for (; b; a %= b, swap(a, b)); return a; }
 
int n;
int a[65537];
 
map<int, vector<int> > mp;
 
int query(string s, int i, int j)
{
    cout << s << ' ' << i << ' ' << j << endl;
    int res; cin >> res;
    return res;
}
 
int main()
{
    ios::sync_with_stdio(0);
    //cin.tie(0), cout.tie(0);
 
    cin >> n;
 
    mp[0].push_back(1);
 
    for (int i = 1; i < n; i++)
    {
        int res = query("XOR", i, i + 1);
        a[i + 1] = a[i] ^ res;
        mp[a[i + 1]].push_back(i + 1);
    }
 
    bool hasAns = false;
    for (auto& it : mp)
    {
        if (it.second.size() > 1)
        {
            int i = it.second[0];
            int j = it.second[1];
 
            int res = query("OR", i, j);
            int d = a[i] ^ res;
 
            cout << "!";
            for (int i = 1; i <= n; i++) cout << ' ' << (a[i] ^ d);
            cout << endl;
 
            hasAns = true;
            break;
        }
    }
 
    if (hasAns) return 0;
 
    int i = 1;
    int j = mp[n - 1][0];
 
    int k = 2;
    if (j == 2) k = 3;
 
    int r1 = query("AND", i, k);
    int r2 = query("AND", j, k);
 
    int d = a[k] ^ (r1 | r2);
 
    cout << "!";
    for (int i = 1; i <= n; i++) cout << ' ' << (a[i] ^ d);
    cout << endl;
}

---

F - Nullify The Matrix

Problem - F - Codeforces

추가 예정