AtCoder abc311 参加メモ

AtCoder

Toyota Programming Contest 2023#4（AtCoder Beginner Contest 311） - AtCoder

B - Vacation Together

全探索。d 日目まで見ていき、全員が暇ならカウント+1, 一人でも暇でなければカウントリセットする。 カウントが最大の値が答え

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

  int ans = 0, now = 0;
  REP(i,d) {
    bool ok = true;
    REP(j,n) if (s[j][i] == 'x') ok = false;
    if (ok) now++;
    else now = 0;
    ans = max(ans,now);
  }
  cout << ans << endl;
  return 0;
}

C - Find it!

強連結成分分解で解いた。 dfs を 2 回行うことで閉路のグループに分解できる( 参考: https://manabitimes.jp/math/1250 )

ちなみに ACL にも SCC ライブラリがあるが、得られる頂点の順序がバラバラなため順序は正しく出力する必要がある。

#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<vector<int>> g(n),gr(n);
  REP(i,n) {
    int a; cin >> a; a--;
    g[i].push_back(a);
    gr[a].push_back(i);
  }

  vector<int> dir;
  vector<bool> used(n);
  auto dfs = [&](auto self, int i) -> void {
    if (used[i]) return;
    used[i] = true;
    for(auto v: g[i]) self(self,v);
    dir.push_back(i);
  };

  REP(i,n) dfs(dfs,i);
  auto dir1 = dir;
  reverse(dir1.begin(), dir1.end());

  swap(g,gr);
  used = vector<bool>(n);
  for(int i: dir1) {
    dir = vector<int>();
    dfs(dfs,i);
    if (dir.size() == 1) continue;
    cout << dir.size() << endl;
    for(auto v: dir) cout << v+1 << " ";
    break;
  }
  return 0;
}

D - Grid Ice Floor

dfs で到達可能なすべてのマス x 4 方向への移動 を調べる。通常の dfs に 4 方向の移動を拡張した形。

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

const vector<pair<int,int>> moves = { {-1,0}, {0,1}, {1,0}, {0,-1} };

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

  // [i][j][k] := i,j マスで k 方向 への移動を試したかどうか
  vector seen(n,vector(m,vector<bool>(4)));
  // [i][j] := i,j マスを通過したかどうか
  vector visited(n,vector<int>(m));

  auto dfs = [&](auto self, int x, int y) -> void {
    REP(k,4) {
      if (seen[x][y][k]) continue;
      seen[x][y][k] = true;
      auto [dx,dy] = moves[k];
      int nx = x, ny = y;
      // 岩にぶつかるまで進む
      while(s[nx+dx][ny+dy] == '.') {
        nx += dx; ny += dy;
        visited[nx][ny] = 1;
      }
      self(self,nx,ny);
    }
  };

  visited[1][1] = true;
  dfs(dfs,1,1);
  int ans = 0;
  REP(i,n) REP(j,m) ans += visited[i][j];
  cout << ans << endl;
  return 0;
}

E - Defect-free Squares

DP。 dp[i][j] := i,j マスまでで、i,j マスを含んで作れる穴のない正方形の総数。 i,j マスが穴でない場合、左、左上、上のマスで min を取ったもの + 1(i,jマスのみで正方形を作る分) となる。

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

int main() {
  int h,w,n; cin >> h >> w >> n;
  vector g(h,vector<bool>(w));
  REP(i,n) {
    int a,b; cin >> a >> b;
    a--; b--;
    g[a][b] = true;
  }

  // dp[i][j] := i,j マスまでで、i,j を含んで作れる穴のない正方形の総数
  vector dp(h,vector<ll>(w));
  REP(i,h) REP(j,w) {
    if (g[i][j]) continue;
    dp[i][j] = 1;
    if (i-1 >= 0 && j-1 >= 0) dp[i][j] += min({ dp[i-1][j-1], dp[i-1][j], dp[i][j-1] });
  }

  ll ans = 0;
  REP(i,h) REP(j,w) ans += dp[i][j];
  cout << ans << endl;
  return 0;
}

今回の成績

tic40さんのトヨタ自動車プログラミングコンテスト2023#4(AtCoder Beginner Contest 311)での成績：1472位
パフォーマンス：1357相当
レーティング：1189→1207 (+18) :)
Highestを更新し、4 級になりました！
#AtCoder #トヨタ自動車プログラミングコンテスト2023#4(ABC311) https://atcoder.jp/users/tic40/history/share/abc311?lang=ja