AtCoder Beginner Contest 300

UNIQUE VISION Programming Contest 2023 Spring(AtCoder Beginner Contest 300) - AtCoder

結果

A - N-choice question : AC(1:44)
B - Same Map in the RPG World : AC(13:33)
C - Cross : AC(27:24)
D - AABCC : WA

A - N-choice question

整数$${A,B}$$と$${N}$$個の選択肢$${C_{i}}$$が与えられ、$${A+B}$$である$${C}$$が何番目かを求める問題

自分の回答

int main(){
  int N, A, B;
  cin >> N >> A >> B;

  int c;
  for(int i = 1; i <= N; i++){
    cin >> c;
    if(c == A + B){
      printf("%d\n", i);
      return 0;
    }
  }
}

そのまま

公式解説

省略

B - Same Map in the RPG World

縦$${H}$$行横$${W}$$列の「#」「.」からなるグリッド$${A,B}$$があり、グリッド$${A}$$を縦横に任意の回数シフトすることで$${B}$$と一致させることができるか判定する問題

自分の回答

int main(){
  int H, W;
  cin >> H >> W;
  vector<vector<char>> A(H, vector<char>(W)), B(H, vector<char>(W));
  for(int i = 0; i < H; i++){
    for(int j = 0; j < W; j++){
      cin >> A[i][j];
    }
  }
  for(int i = 0; i < H; i++){
    for(int j = 0; j < W; j++){
      cin >> B[i][j];
    }
  }

  for(int k = 1; k <= H; k++){
    for(int l = 1; l <= W; l++){
      bool match = true;
      for(int i = 0; i < H; i++){
        for(int j = 0; j < W; j++){
          int si = i - k, sj = j - l;
          if(si < 0){
            si += H;
          }
          if(sj < 0){
            sj += W;
          }
          if(B[i][j] != A[si][sj]){
            match = false;
          }
        }
      }
      if(match){
        printf("Yes\n");
        return 0;
      }
    }
  }
  printf("No\n");
}

実際にシフトすると総当たりがめんどそうだったからシフトするとどの座標に行くかを計算して調べる

公式解説

省略

C - Cross

縦$${H}$$行横$${W}$$列の「#」「.」からなるグリッドがあり、「#」がXの形になっているものがサイズごとにいくつあるか求める問題

自分の回答

int main(){
  int H, W;
  cin >> H >> W;
  vector<vector<char>> C(H + 2, vector<char>(W + 2, '.'));
  for(int i = 1; i <= H; i++){
    for(int j = 1; j <= W; j++){
      cin >> C[i][j];
    }
  }

  int smin = min(H, W);
  vector<int> ans(smin + 1, 0);
  for(int i = 1; i <= H; i++){
    for(int j = 1; j <= W; j++){
      if(C[i][j] == '.'){
        continue;
      }
      int x = 0, k = 1;
      while(C[i + k][j + k] == '#' && C[i - k][j + k] == '#' && C[i + k][j - k] == '#' && C[i - k][j - k] == '#'){
        x++;
        k++;
      }
      ans[x]++;
    }
  }

  for(int i = 1; i <= smin; i++){
    printf("%d", ans[i]);
    printf(i == smin ? "\n" : " ");
  }
}

全ての#でXができているか、サイズはいくつかをそのまま調べて終わり

公式解説

省略

D - AABCC

$${N}$$以下の正整数のうち、$${a < b < c}$$である素数$${a,b,c}$$を用いて$${a^2×b×c^2}$$と表せるものがいくつあるか求める問題

自分の回答

必要な範囲の素数の数え上げはできたけどその先の組み合わせを数えるとなんか増える
シンプルなループと判定だから増えようがないはずなんだけどなぁ…

公式解説

#define MAXP 300005

vector<long long> sieve(){
  vector<long long> res;
  vector<int> mem(MAXP,0);
  for(int i=2;i<MAXP;i++){
    if(mem[i]){continue;}
    res.push_back(i);
    for(int j=i;j<MAXP;j+=i){mem[j]=1;}
  }
  return res;
}

int main(){
  vector<long long> p=sieve();
  long long n;
  cin >> n;
  int sz=p.size();
  int res=0;
  for(int i=0;i<sz;i++){
    for(int j=i+1;j<sz;j++){
      for(int k=j+1;k<sz;k++){
        long long v=p[i]*p[i]*p[j];
        if(v>n){break;}
        v*=p[k];
        if(v>n){break;}
        v*=p[k];
        if(v>n){break;}
        res++;
      }
    }
  }
  cout << res << "\n";
  return 0;
}

https://atcoder.jp/contests/abc300/editorial/6273より

オーバーフローしてたかそうか
しないと思って対策してなかった…