AtCoder Beginner Contest 312

UNIQUE VISION Programming Contest 2023 Summer(AtCoder Beginner Contest 312) - AtCoder

結果

A - Chord: AC(2:27)
B - TaK Code : AC(10:44)
C - Invisible Hand : AC(83:06)(3ペナ)
D - Count Bracket Sequences : 提出無し

A - Chord

英大文字からなる長さ$${3}$$の文字列$${S}$$が与えられ、それが「ACE」「BDF」「CEG」「DFA」「EGB」「FAC」「GBD」のいずれかと等しいか求める問題

自分の回答

int main(){
  string S;
  cin >> S;

  vector<string> C = {"ACE", "BDF", "CEG", "DFA", "EGB", "FAC", "GBD"};
  for(string s : C){
    if(s == S){
      printf("Yes\n");
      return 0;
    }
  }
  printf("No\n");
}

そのまま

公式解説

省略

B - TaK Code

縦$${N}$$マス横$${M}$$マスのグリッドがあり、各マスは「#」か「.」である
グリッド内において以下の条件を満たす箇所を全て求める問題
・$${9 × 9}$$の領域である
・左上と右下の$${3 × 3}$$の領域は全て「#」である
・上記の範囲の周囲$${1}$$マスは全て「.」である

自分の回答

int main(){
  int N, M;
  cin >> N >> M;
  vector<string> S(N);
  for(int i = 0; i < N; i++){
    cin >> S[i];
  }

  vector<string> C = {"###.-----",
                      "###.-----",
                      "###.-----",
                      "....-----",
                      "---------",
                      "-----....",
                      "-----.###",
                      "-----.###",
                      "-----.###"};
  for(int i = 0; i <= N - 9; i++){
    for(int j = 0; j <= M - 9; j++){
      bool cord = true;
      for(int k = 0; k < 9; k++){
        for(int l = 0; l < 9; l++){
          if(C[k][l] == '-'){
            continue;
          }
          if(S[i + k][j + l] != C[k][l]){
            cord = false;
          }
        }
      }
      if(cord){
        printf("%d %d\n", i + 1, j + 1);
      }
    }
  }
}

条件のサイズと形が固定だからそれを作って総当たり

公式解説

省略

C - Invisible Hand

りんごの売り手が$${N}$$人と買い手が$${M}$$人存在し、それぞれ売り手は$${A_{i}}$$円以上でなら売っていいと考え、買い手は$${B_{i}}$$円以下なら買っていいと考える
りんごを売っていいと考える人数が買っていいと考える人数以上となる値段の最低値を求める問題

自分の回答

int main(){
  int N, M;
  cin >> N >> M;
  vector<int> A(N), B(M);
  for(int i = 0; i < N; i++){
    cin >> A[i];
  }
  for(int i = 0; i < M; i++){
    cin >> B[i];
  }

  sort(A.begin(),A.end());
  sort(B.begin(),B.end(), greater<int>());
  int L = 0,R = 1000000001;
  while(L < R){
    int mid = L + (R - L) / 2;
    auto csi = upper_bound(A.begin(), A.end(), mid), cbi = upper_bound(B.begin(), B.end(), mid, greater<int>());
    int cs = csi - A.begin(), cb = cbi - B.begin();
    if(cs >= cb){
      R = mid;
    }
    else{
      L = mid + 1;
    }
  }

  printf("%d\n", R);
}

最初は値段の低い方からABを見て行ってみる方法で書いたけどWAだらけだったしTLEも出たから根本的に違うと思って二分探索に変更

Rを1000000000スタートにして1回WA

公式解説

省略

D - Count Bracket Sequences

「 ( 」「 ) 」「?」からなる文字列$${S}$$が与えられ、「?」を「 ( 」か「 ) 」に置き換えてできた文字列が括弧列(「 ( ) 」を消去していくと空文字列となる文字列)となるような置き換え方の数を$${998244353}$$で割った余りで求める問題

自分の回答

動的計画法っぽいし前に似たような問題を見た気がするけど細部を思いつかなかったし思いついても書ききれてなかったと思う

公式解説

#include <atcoder/modint>
using mint = atcoder::static_modint<998244353>;

int main() {
	string s;
	cin >> s;
	int n = s.size();
	vector<vector<mint>> dp(n + 1, vector<mint>(n + 1));
	dp[0][0] = 1;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < n; j++) {
			if (s[i] != ')') dp[i + 1][j + 1] += dp[i][j];
			if (j != 0 && s[i] != '(') dp[i + 1][j - 1] += dp[i][j];
		}
	}
	cout << dp[n][0].val() << '\n';
}

https://atcoder.jp/contests/abc312/editorial/6852より

i文字目までで(の個数-)の個数をjとしたら?の置き換え含めてi文字目が(の時i+1,j+1へ、)の時i+1,j-1へ現在地の値を追加か
そして答えはN,0

なるほど