Codeforces Round #663 (Div. 2)

A - Suborrays

Problem - A - Codeforces

다음을 만족하는 \(n\)길이의 순열 \(p\)를 알아내야 한다.

- 모든 인덱스 쌍 \(i,j\) \((i \le j)\)에 대해, \((p_i\) OR \(p_{i+1}\) OR \(\cdots\) OR \(p_{j-1}\) OR \(p_j) \ge j-i+1\)

 

\(a, b\)를 bitwise OR 한 결과는 \(\max(a,b)\)보다 작아지지 않는다.

모든 순열에 대해서, \(n\)개의 연속한 수 중에 \(n\)보다 크거나 같은 수가 항상 존재하므로,

모든 순열은 위를 만족한다.

 

#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 ans[101];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        int n; cin >> n;
        int c = n;
        for (int i = 1; i <= n; i += 2) ans[i] = c--;
        for (int i = n % 2 == 0 ? n : n - 1; i >= 1; i -= 2) ans[i] = c--;
 
        for (int i = 1; i <= n; i++) cout << ans[i] << ' ';
        cout << '\n';
    }
}

---

B - Fix You

Problem - B - Codeforces

\(n \times m\)크기의 컨베이어 벨트가 있다. 이 컨베이어 벨트는 'R' 또는 'D'로만 이루어져 있다.

'R' 컨베이어 벨트는 현재 위치의 물건을 오른쪽으로, 'D' 컨베이어 벨트는 아래쪽으로 보낸다.

 

어떤 위치에 물건을 놓더라도 \((n,m)\)에 물건이 도착할 수 있기 위해 교체해야 하는 컨베이어 벨트의 최소값을 알아내야 한다.

 

맨 오른쪽에 있는 컨베이어 벨트는 모두 'D', 맨 아래쪽에 있는 컨베이어 벨트는 모두 '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, m;
string cb[101];
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n >> m;
        for (int i = 0; i < n; i++) cin >> cb[i];
 
        int ans = 0;
        for (int i = 0; i < n - 1; i++) if (cb[i][m - 1] == 'R') ans++;
        for (int i = 0; i < m - 1; i++) if (cb[n - 1][i] == 'D') ans++;
        cout << ans << '\n';
    }
}

---

C - Cyclic Permutations

Problem - C - Codeforces

다음 조건을 만족하는 \(n\) 길이의 순열의 개수를 구해야 한다.

 

다음 규칙에 따라 그래프를 그린다.

1. 모든 인덱스 \(i\)에 대해, \(1 \le j \lt i\)이고 \(p_j > p_i\)인 가장 큰 \(j\)가 존재한다면 정점 \(i, j\)를 잇는 간선을 그린다.

2. 모든 인덱스 \(i\)에 대해, \(i \lt j \le n\)이고 \(p_j > p_i\)인 가장 작은 \(j\)가 존재한다면 정점 \(i, j\)를 잇는 간선을 그린다.

 

이 그래프에 사이클이 적어도 1개 이상 존재해야 한다.

 

 

위의 그래프가 사이클이 없기 위해서는, 일자로 연결된 그래프여야 한다.

 

\(n\)은 가장 큰 수이기 때문에 여기에서 나가는 간선은 존재하지 않는다.

\(n\)을 기준으로, 모든 수들을 \(n\)의 왼쪽 또는 오른쪽에 놓아보자.

각 경우에 대해, \(n\)의 왼쪽에 있는 수들은 오름차순, 오른쪽에 있는 수들은 내림차순으로 정렬하는 것이 사이클이 없는 유일한 방법임을 알 수 있다.

 

따라서 모든 순열의 수에서, \(2^{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; }
 
ll n;
const ll MOD = 1e9 + 7;
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n;
    ll ans = 1;
    for (ll i = 1; i <= n; i++) ans = ans * i % MOD;
 
    ll minus = 1;
    for (int i = 0; i < n - 1; i++) minus = minus * 2 % MOD;
 
    ans = (ans + MOD - minus) % MOD;
    cout << ans;
}

---

D - 505

Problem - D - Codeforces

\(n \times m\) 크기의 이진 행렬이 주어진다.

이 행렬의 모든 짝수 크기의 정사각형 부분 행렬에 포함된 1의 개수가 홀수가 되도록 하려고 한다.

이 때 가능한지 여부를 알아내야 한다. 가능하다면 바꿔야 하는 칸의 최소 개수를 알아내야 한다.

 

먼저, \(\min(n,m) \ge 4\) 라면 해가 없음을 알 수 있다.

\(4 \times 4\)크기의 부분행렬 안에 1이 홀수개 존재하는데, 이를 4등분 한 각 \(2 \times 2\)크기의 부분 행렬 안에 모두 1이 홀수개 존재할 수는 없기 때문이다.

 

따라서, \(n, m\)중 하나는 3 이하이고, 편의를 위해 이를 \(n\)으로 설정하자.

\(n\)이 1이라면 답은 무조건 0이므로 역시 계산할 필요가 없다.

 

따라서 \(n\)은 2 또는 3이다.

이제 간단한 DP또는 그리디로 문제를 쉽게 해결할 수 있다.

 

#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, m;
int board[3][1000001];
 
int dp[1000001][8];
int solve(int idx, int st)
{
    if (idx == m) return 0;
 
    int& ret = dp[idx][st];
    if (ret != -1) return ret;
 
    ret = 987654321;
 
    for (int bs = 0; bs < (1 << n); bs++)
    {
        int cnt = 0;
        for (int i = 0; i < n; i++)
        {
            if (bs & (1 << i))
            {
                board[i][idx] = 1 - board[i][idx];
                cnt++;
            }
        }
 
        bool flag = true;
        for (int i = 0; i < n - 1; i++)
        {
            int one = board[i][idx - 1] + board[i][idx]
                + board[i + 1][idx - 1] + board[i + 1][idx];
 
            if (one % 2 == 0) flag = false;
        }
 
        if (flag)
        {
            int res = solve(idx + 1, bs) + cnt;
            ret = min(ret, res);
        }
 
        for (int i = 0; i < n; i++)
        {
            if (bs & (1 << i))
            {
                board[i][idx] = 1 - board[i][idx];
            }
        }
    }
 
    return ret;
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    cin >> n >> m;
 
    if (min(n, m) >= 4)
    {
        cout << -1;
        return 0;
    }
 
    if (min(n, m) == 1)
    {
        cout << 0;
        return 0;
    }
 
    // now 2 or 3
 
    if (n < m)
    {
        for (int i = 0; i < n; i++)
        {
            string tmp; cin >> tmp;
            for (int j = 0; j < m; j++) board[i][j] = tmp[j] - '0';
        }
    }
    else
    {
        for (int i = 0; i < n; i++)
        {
            string tmp; cin >> tmp;
            for (int j = 0; j < m; j++) board[j][i] = tmp[j] - '0';
        }
 
        swap(n, m);
    }
 
    memset(dp, -1, sizeof dp);
 
    int ans = 987654321;
    for (int bs = 0; bs < (1 << n); bs++)
    {
        int cnt = 0;
        for (int i = 0; i < n; i++)
        {
            if (bs & (1 << i))
            {
                board[i][0] = 1 - board[i][0];
                cnt++;
            }
        }
 
        int res = solve(1, bs) + cnt;
        ans = min(ans, res);
 
        for (int i = 0; i < n; i++)
        {
            if (bs & (1 << i))
            {
                board[i][0] = 1 - board[i][0];
            }
        }
    }
 
    cout << ans;
}

---

E - Pairs of Pairs

Problem - E - Codeforces

\(n\)개의 정점, \(m\)개의 간선으로 이루어진 단순 연결 무방향 그래프가 주어진다.

 

이 그래프에서 둘 중 하나를 찾아 출력해야 한다.

1. \(\lceil \frac n2 \rceil\)개 이상의 노드로 이루어진 단순 경로
2. \(\lceil \frac n2 \rceil\)개 이상의 노드로 이루어진 valid pairing

 

\(n\)개 노드의 부분 집합에 대해, 이 집합에 속한 노드들을 둘씩 pair로 짝지은 것을 pairing이라고 하자.

pairing은 어떤 두 pair \((a,b), (c,d)\)를 고르더라도, 이 4개의 정점 사이에 간선이 2개 이하라면 valid하다고 한다.

 

그래프를 DFS로 탐색하면서 DFS 스패닝 트리를 만들자.

이 트리의 깊이가 \(\lceil \frac n2 \rceil\) 이상이라면, 단순 경로를 만들면 된다.

 

그렇지 않다면, 각 노드의 깊이를 저장하자.

같은 깊이를 가진 노드 끼리는 간선이 존재하지 않으므로, 같은 깊이를 가진 노드 2개를 pair로 짝지어 주는 것을 반복하자.

 

깊이는 \(\lceil \frac n2 \rceil\)보다 작고, 각 깊이에 대해 많아도 1개의 노드가 pairing에 속하지 않게 되므로,
\(\lceil \frac n2 \rceil\)개 이상의 노드가 pairing에 포함되게 된다.

 

#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, m;
vector <int> graph[500001];
int cache[500001];
int par[500001];
vector <int> lv[500001];
bool isPath;
 
void PATH(int v)
{
    isPath = 1;
    cout << "PATH\n";
    vector <int> ans;
    while (v)
    {
        ans.push_back(v);
        v = par[v];
    }
 
    cout << ans.size() << '\n';
    for (int cv : ans) cout << cv << ' ';
    cout << '\n';
}
 
void DFS(int v, int p, int l)
{
    par[v] = p;
    cache[v] = 1;
    lv[l].push_back(v);
 
    if (!isPath && l >= (n + 1) / 2)
    {
        PATH(v);
    }
 
    for (int nv : graph[v])
    {
        if (cache[nv]) continue;
        DFS(nv, v, l + 1);
    }
}
 
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
 
    int t; cin >> t;
    while (t--)
    {
        cin >> n >> m;
        for (int i = 1; i <= n; i++)
        {
            graph[i].clear();
            lv[i].clear();
            cache[i] = 0;
        }
 
        isPath = 0;
 
        for (int i = 0; i < m; i++)
        {
            int u, v; cin >> u >> v;
            graph[u].push_back(v);
            graph[v].push_back(u);
        }
 
        DFS(1, 0, 1);
 
        if (isPath) continue;
 
        cout << "PAIRING\n";
        vector <pii> ans;
        for (int i = 1; i <= n; i++)
        {
            for (int j = 0; j + 1 < lv[i].size(); j += 2)
                ans.push_back({ lv[i][j], lv[i][j + 1] });
        }
 
        cout << ans.size() << '\n';
        for (pii it : ans) cout << it.first << ' ' << it.second << '\n';
    }
}