Codeforces Round #648 (Div. 2) A ~ D 풀이

A. Matrix Game (1100)

n x m 크기의 행렬이 주어졌을 때 각 칸마다 0은 unclaimed, 1은 claimed 칸을 나타내며

unclaimed 한 칸을 claimed 하기 위해서는 그 칸의 행과 열에 claimed 칸이 존재하지 않아야한다.

이 때 Ashish와 Vivek이 Ashish가 먼저 claim을 시작 할 때 어떤 칸도 claimed 할 수 없게 되었을 경우 패배한다.

두 플레이어가 최적의 선택을 번갈아가며 했을 때 누가 승리하는지 출력하는 문제였다.

 

A번부터 게임이론이 나왔다.

우선 쉽게 관찰할 수 있는 부분은 claim 가능한 칸의 갯수가 홀수면 Ashish가 승리하며 짝수면 Vivek이 승리한다는 것.

따라서 우리는 모든 칸에 대해 그 칸의 행과 열 중 1이 존재하는지 확인하고 존재하지않다면

claim 가능하다고 확인하고 칸의 갯수를 증가시켜주고 그 칸을 1로 바꾸어주면 되겠다.

 

n과 m의 제한이 50이기 때문에 완전탐색으로 충분하다.

 

#include <bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define mp make_pair
#define MOD 1000000007
#define cont continue
#define rep(i, n) for(int i = 0 ; i < (n) ; i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF = 987654321;
int T;

int main() {
  cin.tie(NULL);
  ios_base::sync_with_stdio(false); 

  cin >> T;

  for(int i = 0 ; i < T ; i++) {
    int n, m;
    cin >> n >> m;
    int cnt = 0;
    int board[n + 1][m + 1] = {};
    memset(board, -1, sizeof(board));
    for(int j = 1 ;  j <= n ; j++) {
      for(int k = 1 ; k <= m ; k++) {
        cin >> board[j][k];
      }
    }

    for(int j = 1 ; j <= n ; j++) {
      for(int k = 1 ; k <= m ; k++) {
        bool flag = true;
        for(int l = 1 ; l <= n ; l++) {
          if(board[l][k] == 1) flag = false;
        }
        for(int l = 1 ; l <= m ; l++) {
          if(board[j][l] == 1) flag = false;
        }

        if(flag) {
          board[j][k] = 1;
          cnt++;
        }
      }
    }
    if(cnt % 2 == 0) {
      cout << "Vivek" << endl; 
    }
    else {
      cout << "Ashish" << endl;
    }
  }
}

 

B. Trouble Sort (1300)

https://atcoder.jp/contests/arc097/tasks/arc097_b

D - Equals

앳코더의 이 문제와 비슷한 느낌의 문제이다.

 

배열 A와 그에 대응되는 배열 B가 주어진다.

배열 B는 0과 1로만 이루어져있다.

배열 A를 스왑하는데 배열 B의 수가 서로 다른경우에만 스왑할 수 있다.

이 경우 배열 A를 비내림차순으로 만들 수 있는가?

 

위 앳코더 문제를 풀어본 경험이있어서 빠르게 풀 수 있었다.

0만 존재할 경우에는 스왑이 불가능하다.

1만 존재할 경우에는 스왑이 불가능하다.

하지만 0과 1이 모두 존재한다면?

배열을 어떻게든 원하는 대로 배치할 수 있게된다. 나머지가 모두 0이고 1이 하나만 존재한다해도

그 1을 이용해서 모든 수를 원하는 위치로 이동시킬 수 있게되기 때문이다.

 

그렇다면 우리는 0과 1만 존재할 경우만 따로 처리를 해주면 되는데

똑같은 배열을 하나 준비해서 정렬된 배열과 같은지 확인해주도록하자.

 

#include <bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define mp make_pair
#define MOD 1000000007
#define cont continue
#define rep(i, n) for(int i = 0 ; i < (n) ; i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF = 987654321;
int T;

int main() {
  cin.tie(NULL);
  ios_base::sync_with_stdio(false); 

  cin >> T;

  for(int i = 0 ; i < T ; i++) {
    int n;
    cin >> n;
    bool one = false;
    bool zero = false;
    vector<int> arr;
    vector<int> tmp;
    for(int j = 0 ; j < n ; j++) {
      int x;
      cin >> x;
      arr.pb(x);
    }
    tmp = arr;
    for(int j = 0 ; j < n ; j++) {
      int x;
      cin >> x;
      if(x == 1) one = true;
      if(x == 0) zero = true;
    }
    sort(arr.begin(), arr.end());
    bool flag = true;
    if(one == false || zero == false) {
      if(tmp == arr) {
        flag = true;
      }
      else {
        flag = false;
      }
    }
    else {
      flag = true;
    }
    if(flag) cout << "Yes" << endl;
    else cout << "No" << endl;
  }
}

 

C. Rotation Matching (1400)

배열 A, B 가 주어지고 배열을 왼쪽 쉬프트, 혹은 오른쪽 쉬프트를 할 수 있을 때에

가장 많이 겹치는 요소의 수를 구하는 문제.

 

배열 A에서 B까지의 거리가 같은 경우 쉬프트 연산을 어떻게든 하였을 때 겹칠 수 있다는 것을 확인했다.

하지만  1 2 3 4 5

           2 3 4 5 1 과 같은 배열을 보았을 때 2, 3, 4, 5 는 각 거리의 차이가 1이므로 겹치지만

 

1의 경우에는 방향이 반대이기 때문에 거리가 달라서 어떻게 처리해주어야 할지 고민했다.

 

결국에는 원순열과 같은 느낌이기 때문에 배열 A를 한번 더 넣어주어 ↙ 방향의 거리만 생각해주었다.

 

이런식으로 하면 거리가 1인 요소의 갯수가 5개, 그 외 거리들의 요소의 갯수는 1개이므로 정답은 5가 된다.

STL map을 사용하여 처리해 주었다.

 

#include <bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define mp make_pair
#define MOD 1000000007
#define cont continue
#define rep(i, n) for(int i = 0 ; i < (n) ; i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF = 987654321;
int T;

int main() {
  cin.tie(NULL);
  ios_base::sync_with_stdio(false); 

    int n;
    cin >> n;

    vector< vector<int> > pos(200001);
    vector< vector<int> > pos2(200001);
    map<int, int> m;

    int ans = 0;
    for(int i = 0 ; i < n ; i++) {
      int x;
      cin >> x;
      pos[x].pb(i);
      pos[x].pb(i + n);
    }
    for(int i = 0 ; i < n ; i++) {
      int x;
      cin >> x;
      pos2[x].pb(i);
    }
    for(int i = 1 ; i <= n ; i++) {
      m[pos[i][0] - pos2[i][0]]++;
      m[pos[i][1] - pos2[i][0]]++;
      ans = max(ans, m[pos[i][1] - pos2[i][0]]);
      ans = max(ans, m[pos[i][0] - pos2[i][0]]);
    }
    cout << ans << endl;
}

 

D. Solve The Maze (1700,  업솔빙)

. 위치에 #을 세워 G는 (n, m)으로 보내고 B는 못가게끔 막을 수 있는가를 묻는 문제

우선 쉽게 관측할 수 있는 부분은 G와 B가 인접 할 경우에는 불가능하다.

B의 상하좌우에 .이 존재 할 경우 #을 세워주고 남은 G들에 대해서 (n, m) 으로 도달 가능한지의 여부를 확인하면 된다.

대회 당시에는 DFS를 통해 모든 G에 대해 (n, m)으로 갈 수 있는 지에 대한 여부를 확인해버려서 TLE가 났다.

모든 G에 대해 그래프 순회를 하는 것이 아닌 반대로 (n, m)부터 시작해 갈 수 있는 칸을 확인해 주어 도달하지 못한 G가 있는지 확인하는 방법으로 풀었다. 모든 G에 도달 했을 경우 Yes, 아닐 경우 No.

#include <bits/stdc++.h>
#define endl '\n'
#define pb push_back
#define mp make_pair
#define MOD 1000000007
#define cont continue
#define rep(i, n) for(int i = 0 ; i < (n) ; i++)
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
const ll INF = 987654321;
int T;
int n, m;
char board[55][55] = {};
int dy[4] = {-1, 1, 0, 0};
int dx[4] = {0, 0, -1, 1};
bool visit[55][55] = {};
int chk = 0;

bool isRange(int y, int x) {
  if(y > n || y <= 0 || x > m || x <= 0) return false;
  else return true;
}

int main() {
  cin.tie(NULL);
  ios_base::sync_with_stdio(false); 

  cin >> T;

  for(int i = 0 ; i < T ; i++) {
    cin >> n >> m;
    bool flag = true;
    memset(visit, false, sizeof(visit));
    set<pii> st;
    for(int j = 0 ; j <= 51 ; j++) {
      for(int k = 0 ; k <= 51 ; k++) {
        board[j][k] = ' ';
      }
    }
    for(int j = 1 ; j <= n ; j++) {
      for(int k = 1 ; k <= m ; k++) {
        cin >> board[j][k];
      }
    }
    for(int j = 1 ; j <= n ; j++) {
      for(int k = 1 ; k <= m ; k++) {
        if(board[j][k] == 'G') {
          st.insert(mp(j, k));
          if(board[j - 1][k] == 'B' || board[j + 1][k] == 'B' || board[j][k + 1] == 'B' || board[j][k - 1] == 'B') {
            flag = false;
          }
        }
        if(board[j][k] == 'B') {
            if(board[j - 1][k] == '.')
              board[j - 1][k] = '#';
            if(board[j + 1][k] == '.')
            board[j + 1][k] = '#';
            if(board[j][k + 1] == '.')
            board[j][k + 1] = '#';
            if(board[j][k - 1] == '.')
            board[j][k - 1] = '#';
        }
      }
    }
    if(st.size() == 0) {
      cout << "Yes" << endl;
      continue;
    }
    if(!flag || board[n][m] == '#') {
      cout << "No" << endl;
      continue;
    }
    queue<pii> q;
    q.push(mp(n, m));
    visit[n][m] = true;
    if(st.find(mp(n, m)) != st.end()) {
      st.erase(st.find(mp(n, m)));
    }
    while(!q.empty()) {
      int cur_y = q.front().first;
      int cur_x = q.front().second;
      q.pop();
      if(st.find(mp(cur_y, cur_x)) != st.end()) {
        st.erase(st.find(mp(cur_y, cur_x)));
      }
      for(int i = 0 ; i < 4 ; i++) {
        int ny = cur_y + dy[i];
        int nx = cur_x + dx[i];
        if(isRange(ny, nx) && !visit[ny][nx] && board[ny][nx] != '#') {
          visit[ny][nx] = true;
          q.push(mp(ny, nx));
        }
      }
    }
    if(st.size() == 0) {
      cout << "Yes" << endl;
    }
    else {
      cout << "No" << endl;
    }
  }
}