AtCoder abc307 参加メモ

Tokio Marine & Nichido Fire Insurance Programming Contest 2023（AtCoder Beginner Contest 307) - AtCoder

B - racecar

全探索

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'

int main() {
  int n; cin >> n;
  vector<string> s(n);
  REP(i,n) cin >> s[i];

  auto f = [](string s) {
    string t = s;
    reverse(t.begin(),t.end());
    return t == s;
  };

  bool ok = false;
  REP(i,n) REP(j,n) if (i != j && f(s[i]+s[j])) ok = true;
  cout << (ok ? "Yes" : "No") << endl;
  return 0;
}

C - Ideal Sheet

10 x 10 マスという制約のため、シート A, B の平行移動を全探索しても間に合う。

透明マスは関係ないので、黒マスだけを比較すれば良い。A, B の黒マスの集合が X の黒マス集合と一致すれば Yes。

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'
using P = pair<int,int>;

int main() {
  vector b(3,vector<P>());
  REP(i,3) {
    int h,w; cin >> h >> w;
    REP(j,h) {
      string s; cin >> s;
      REP(k,w) if (s[k] == '#') b[i].emplace_back(j,k);
    }
  }

  set<P> ideal;
  for(auto [x,y]: b[2]) ideal.emplace(x,y);

  REP(i,20) REP(j,20) REP(k,20) REP(l,20) {
    set<P> st;
    for(auto [x,y]: b[0]) st.emplace(x+i-10,y+j-10);
    for(auto [x,y]: b[1]) st.emplace(x+k-10,y+l-10);
    if (st == ideal) { cout << "Yes" << endl; return 0; }
  }
  cout << "No" << endl;
  return 0;
}

D - Mismatched Parentheses

stack で括弧マッチングを管理する。 括弧が閉じていたら開始と終了位置メモしておき、最終的に累積和で括弧が閉じている範囲を集計する。

#include <bits/stdc++.h>
using namespace std;
#define REP(i,n) for(int i=0;i<n;i++)
#define endl '\n'
using P = pair<char,int>;

int main() {
  int n; cin >> n;
  string s; cin >> s;

  stack<P> st;
  vector<int> sum(n+1);
  REP(i,n) {
    if (s[i] == '(') st.emplace('(',i);
    if (s[i] == ')' && st.size()) {
      auto [c,idx] = st.top();
      if (c == '(') {
        st.pop();
        sum[idx]++;
        sum[i+1]--;
      }
    }
  }

  REP(i,n) sum[i+1] += sum[i];
  REP(i,n) if (sum[i] == 0) cout << s[i];
  return 0;
}