Educational Codeforces Round 105 (Div.2)

A. ABC String

문자열 s는 A, B, C로 이루어져 있고, 각 문자열은 '(' 또는 ')'로 치환 될 수 있다. 이때, "()", "(()())" 처럼 정상적인 괄호 표현식으로 나타낼 수 있는지 확인하는 문제

문자 A, B, C에 대해 '(' 와 ')'를 완전탐색 해야 문제를 해결할 수 있다.

정규 괄호식 테스트하는 함수 test()는 a,b,c 인자를 받게 되는데 0이면 '(', 0이 아니면 ')'로 작동하도록 했습니다.

완전탐색의 경우 1부터 6까지 비트마스크를 이용하여 탐색을 진행했습니다.

#include <iostream>
#include <vector>
#include <algorithm>
#define endl '\n'
#define ll long long
#define pii pair<int,int>
using namespace std;

bool test(string s, int a, int b, int c) {
  int remain=0;
  for(char C : s) {
    if(remain<0) return false;
    if(C=='A') {
      !a ? remain++ : remain--;
    }
    else if(C=='B') {
      !b ? remain++ : remain--;
    }
    else {
      !c ? remain++ : remain--;
    }
  }
  if(remain==0) return true;
  return false;
}

void solve() {
  string s;
  cin>>s;
  for(int i=1;i<8;i++) {
    if(test(s,i&1,i&2,i&4)) {
      cout<<"YES"<<endl;
      return;
    }
  }
  cout<<"NO"<<endl;
  return;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  //freopen("input.txt","r",stdin);
  int t;
  cin>>t;
  while(t--) {
    solve();
  }
  return 0;
}

---

B. Berland Crossword

n$\times$n 배열에 U, R, D, L 만큼 모서리에 색칠을 할 수 있는지 확인하는 문제

먼저, 이 문제의 경우 두 가지 경우를 생각해야 한다.

1. U, R, D, L이 n개의 셀을 색칠해야 할 때
2. U, R, D, L이 0개의 셀을 색칠해야 할 때

위 두 가지 경우는 모두 인접 모서리에 영향을 준다.

즉, 4개의 모서리 양 끝을 체크하면서 한 모서리당 남은 n-2개의 셀에 나머지를 색칠할 수 있는가 확인해야 한다.

총 4개의 꼭지점 부분을 비트마스킹하면서 색을 칠할 수 있는지 완전탐색 한다.

여기 등장하는 u, r, d, l은 이미 칠해진 수이다.

• mask가 1110 이라면, (1,n), (n,1), (n,n)이 칠해진 경우이다.

이미 칠해진 개수 u, r, d, l은 칠해야 하는 개수 U, R, D, L의 수를 넘을 수 없다.

또한, 이미 칠해진 개수 u, r, d, l과 양쪽 끝을 제외한 남은 모서리 공간 n-2개를 더한 값이 칠해야 하는 개수 U, R, D, L보다 적어서는 안된다.

#include <iostream>
#include <vector>
#include <algorithm>
#define endl '\n'
#define ll long long
#define pii pair<int,int>
using namespace std;

void solve() {
  int n;
  cin>>n;
  int U,R,D,L;
  cin>>U>>R>>D>>L;
  for(int mask=0;mask<16;mask++) {
    bool check=true;

    int u=0, r=0, d=0, l=0;
    if(mask&1) u++, l++;
    if(mask&2) d++, l++;
    if(mask&4) d++, r++;
    if(mask&8) r++, u++;

    if(u>U || u+(n-2)<U) check=false;
    if(r>R || r+(n-2)<R) check=false;
    if(d>D || d+(n-2)<D) check=false;
    if(l>L || l+(n-2)<L) check=false;

    if(check) {
      cout<<"YES"<<endl;
      return;
    }
  }  
  cout<<"NO"<<endl;
  return;
}

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0); cout.tie(0);
  //freopen("input.txt","r",stdin);
  int t;
  cin>>t;
  while(t--) {
    solve();
  }
  return 0;
}

---

C. 1D Sokoban

---

D. Dogeforces