AtCoder abc312 参加メモ

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

B - TaK Code

制約が小さいので、すべての (i,j) から 9x9 マスを条件に沿っているか全探索すればいい。

#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,m; cin >> n >> m;
  vector<string> s(n);
  REP(i,n) cin >> s[i];

  // 座標(x,y) から 3x3マスの領域がすべて黒 かつ 8方位隣接マスが全て白か？
  auto f = [&](int x, int y, vector<vector<int>> v) -> bool {
    REP(i,5) REP(j,5) {
      int nx = x-1+i, ny = y-1+j;
      if (nx < 0 || ny < 0 || nx >= 9 || ny >= 9) continue;
      // 3x3の外
      if (nx < x || ny < y || nx > x+2 || ny > y+2) {
        if (v[nx][ny] == '#')  return false;
      } else {
        if (v[nx][ny] == '.')  return false;
      }
    }
    return true;
  };

  REP(i,n-8) REP(j,m-8) {
    vector v(9, vector<int>(9));
    REP(k,9) REP(l,9) v[k][l] = s[i+k][j+l];
    if (f(0,0,v) && f(6,6,v)) cout << i+1 << " " << j+1 << endl;
  }
  return 0;
}

C - Invisible Hand

単調性があるため二分探索できる。 金額が x のときの売り手、買い手の数を求め方に注意する。

#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,m; cin >> n >> m;
  vector<int> a(n),b(m);
  REP(i,n) cin >> a[i];
  REP(i,m) cin >> b[i];
  sort(a.begin(),a.end());
  sort(b.begin(),b.end());

  int ok = 1e9+5, ng = 0;
  while(abs(ok - ng) > 1) {
    int mid = (ok+ng)/2;
    int seller = upper_bound(a.begin(),a.end(),mid) - a.begin();
    int buyer = m - (lower_bound(b.begin(),b.end(),mid) - b.begin());
    if (seller >= buyer) ok = mid;
    else ng = mid;
  }
  cout << ok << endl;
  return 0;
}

D - Count Bracket Sequences

DP がうまく書けず、ACできず。悔しすぎる。

成績

緑落ち

tic40さんのユニークビジョンプログラミングコンテスト2023 夏 (AtCoder Beginner Contest 312)での成績：3502位
パフォーマンス：840相当
レーティング：1207→1175 (-32) :(
#AtCoder #ユニークビジョンプログラミングコンテスト2023夏(ABC312) https://atcoder.jp/users/tic40/history/share/abc312?lang=ja