AtCoder Beginner Contest 311

OKU

結果

A - First ABC : AC(2:26)
B - Vacation Together : AC(6:53)
C - Find it! : AC(31:10)
D - Grid Ice Floor : AC(56:46)
E - Defect-free Squares : 提出無し

A - First ABC

「A」「B」「C」からなる文字列$${S}$$が与えられ、左から見て行って「A」「B」「C」が全て$${1}$$回以上出てくるのは何文字目か求める問題

自分の回答

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

  bool A = false, B = false, C = false;
  for(int i = 0; i < N; i++){
    if(S[i] == 'A'){
      A = true;
    }
    else if(S[i] == 'B'){
      B = true;
    }
    else if(S[i] == 'C'){
      C = true;
    }
    if(A && B && C){
      printf("%d\n", i + 1);
      return 0;
    }
  }
}

前から見て行ってそれぞれ出てきたか管理

公式解説

省略

B - Vacation Together

$${N}$$人の人の今後$${D}$$日間の予定($${j}$$文字目が「o」ならば暇、「x」ならばそうでない)が与えられる
全員が暇である日が連続して最大何日あるか求める問題

自分の回答

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

  int ans = 0, now = 0;
  for(int j = 0; j < D; j++){
    bool y = true;
    for(int i = 0; i < N; i++){
      if(S[i][j] == 'x'){
        y = false;
      }
    }
    if(y){
      now++;
    }
    else{
      ans = max(ans, now);
      now = 0;
    }
  }
  ans = max(ans, now);

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

そのまま

公式解説

省略

C - Find it!

$${N}$$頂点$${N}$$辺の有向グラフがあり、全ての頂点からは$${1}$$つ辺が伸びている
同一頂点を含まない有効閉路を$${1}$$つ求める問題

自分の回答

int main(){
  int N;
  cin >> N;
  vector<int> G(N + 1);
  for(int i = 1; i <= N; i++){
    cin >> G[i];
  }

  vector<int> seen(N + 1, -1);
  stack<int> ans;
  bool end = false;
  for(int i = 1; i <= N; i++){
    if(seen[i] != -1){
      continue;
    }

    queue<int> bfs;
    bfs.push(i);
    seen[i] = 0;
    while(!bfs.empty()){
      int now = bfs.front();
      bfs.pop();
      int go = G[now];
      if(seen[go] == -1){
        bfs.push(go);
        seen[go] = now;
      }
      else{
        ans.push(now);
        while(seen[ans.top()] != go){
          ans.push(seen[ans.top()]);
        }
        ans.push(go);
        end = true;
      }
      if(end){
        break;
      }
    }
    if(end){
      break;
    }
  }

  printf("%d\n", ans.size());
  while(!ans.empty()){
    printf("%d ", ans.top());
    ans.pop();
  }
  printf("\n");
}

幅優先探索ですでに通った頂点に行こうとしたらそれが閉路になっているため、通ったかの判定にどの頂点から来たかを記録しておいて遡っていく

思えばそこからもう1周した方が楽だったかな

公式解説

    N = int(input())
    A = list(map(int, ("0 " + input()).split()))
    now = 1
    for _ in range(N): now = A[now] # 予めN回移動する
    B = [now]
    while B[0] != A[now]:
    	now = A[now]
    	B.append(now)
    print(len(B))
    print(*B)

https://atcoder.jp/contests/abc311/editorial/6830より
Pythonによるもの

そうかグラフの性質的に任意の頂点からN回移動すれば閉路内にいるのか

なるほど

D - Grid Ice Floor

$${N × M}$$のグリッドがあり、各マスには氷か岩がある
プレイヤーは立っているマスから上下左右に移動でき、移動を始めると岩のマスにぶつかるまでその方向に移動を続ける
プレイヤーの初期位置が$${(2,2)}$$であるとき、移動を何回でも行ってプレイヤーが触れることのできる氷のマスは何マスあるか求める問題

自分の回答

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

  queue<pair<int, int>> sear;
  sear.push({1, 1});
  S[1][1] = '-';
  vector<int> di = {0, 1, 0, -1}, dj = {1, 0, -1, 0};
  while(!sear.empty()){
    for(int i = 0; i < 4; i++){
      int k = 1;
      auto [si, sj] = sear.front();
      while(true){
        if(S[si + di[i]][sj + dj[i]] == '#'){
          if(S[si][sj] == '.'){
            sear.push({si, sj});
          }
          S[si][sj] = '-';
          break;
        }
        else{
          S[si][sj] = '-';
          si += di[i];
          sj += dj[i];
        }
      }
    }
    sear.pop();
  }

  int ans = 0;
  for(int i = 0; i < N; i++){
    for(int j = 0; j < M; j++){
      if(S[i][j] == '-'){
        ans++;
      }
    }
  }
  printf("%d\n", ans);
}

すでに触れたマスからはどの方向に移動しても触れたマスしかないため、幅優先探索みたいに触れてないマスに止まったらそこから各方向に移動を繰り返す

公式解説

int dx4[4]={1,-1,0,0};
int dy4[4]={0,0,1,-1};

int main(){
  int n,m;
  cin >> n >> m;
  vector<string> s(n);
  for(auto &nx : s){cin >> nx;}

  vector<int> fl(5*n*m,0);
  queue<int> q;
  fl[5*(m+1)+4]=1;
  q.push(5*(m+1)+4);
  while(!q.empty()){
    int od=q.front();q.pop();
    int x=(od/5)/m;
    int y=(od/5)%m;
    int d=od%5;

    if(d==4){
      // stop
      for(int i=0;i<4;i++){
        int nx=x+dx4[i];
        int ny=y+dy4[i];
        int nd=i;
        if(s[nx][ny]=='.'){
          int nid=5*(nx*m+ny)+nd;
          if(fl[nid]==0){
            fl[nid]=1;
            q.push(nid);
          }
        }
      }
    }
    else{
      // keep the direction
      int nx=x+dx4[d];
      int ny=y+dy4[d];
      int nd=d;
      if(s[nx][ny]=='.'){
        int nid=5*(nx*m+ny)+nd;
        if(fl[nid]==0){
          fl[nid]=1;
          q.push(nid);
        }
      }
      else{
        // hit a rock
        int nid=5*(x*m+y)+4;
        if(fl[nid]==0){
          fl[nid]=1;
          q.push(nid);
        }
      }
    }
  }

  int res=0;
  for(int i=0;i<n*m;i++){
    res+=max({fl[5*i],fl[5*i+1],fl[5*i+2],fl[5*i+3],fl[5*i+4]});
  }
  cout << res << "\n";
  return 0;
}

https://atcoder.jp/contests/abc311/editorial/6821より

やろうとしてることはわかるんだけどコードが理解できてない…

E - Defect-free Squares

$${H}$$行$${W}$$列のグリッドがあり、$${N}$$マス穴が開いている
グリッド内で穴の開いていない正方形がいくつあるか求める問題

自分の回答

計算量削減の方法が一切思いつかなかった

公式解説

constexpr int nmax = 3030;
int hole[nmax][nmax];
int dp[nmax][nmax];

int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(nullptr);
  int H, W, N;
  cin >> H >> W >> N;
  for (int i = 0, a, b; i < N; i++) {
    cin >> a >> b, hole[a][b] = 1;
  }
  long long ans = 0;
  for (int i = 1; i <= H; i++) {
    for (int j = 1; j <= W; j++) {
      if (hole[i][j]) continue;
      dp[i][j] = min({dp[i - 1][j - 1], dp[i][j - 1], dp[i - 1][j]}) + 1;
      ans += dp[i][j];
    }
  }
  cout << ans << "\n";
}

https://atcoder.jp/contests/abc311/editorial/6819より

それぞれのマスを正方形の右下としたらその状態で作れる正方形の数はmin(左上,上,左)+1だから動的計画法ができて答えはその総和か

なるほど

この記事が気に入ったらサポートをしてみませんか？