AtCoder Beginner Contest 322

2023年10月2日 15:17

結果

A - First ABC 2 : AC(3:13)
B - Prefix and Suffix : AC(11:49)
C - Festival : AC(17:45)
D - Polyomino : AC(65:47)
E - Product Development : 提出無し

A - First ABC 2

「A」「B」「C」からなる長さ$${N}$$の文字列$${S}$$が与えられ、その中で「ABC」が部分文字列として現れる最初の位置を求める問題

自分の回答

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

  int ans = S.find("ABC");

  printf(ans == string::npos ? "-1\n" : "%d\n", ans + 1);
}

そのまま

公式解説

省略

B - Prefix and Suffix

英小文字からなる文字列$${S,T}$$が与えられ、$${S}$$の長さは$${N}$$、$${T}$$の長さは$${M}$$である
$${T}$$の先頭$${N}$$文字が$${S}$$と等しいとき$${S}$$は$${T}$$の接頭辞であるとし、後ろ$${N}$$文字が等しいとき接尾辞であるとする
$${S}$$が$${T}$$の接頭辞かつ接尾辞である場合は$${0}$$を、接頭辞であるが接尾辞でない場合は$${1}$$を、接頭辞でないが接尾辞である場合は$${2}$$を、接頭辞でも接尾辞でもない場合は$${3}$$を出力する問題

自分の回答

int main(){
  int N, M;
  string S, T;
  cin >> N >> M >> S >> T;

  bitset<2> ans(00);
  for(int i = 0; i < N; i++){
    if(S[i] != T[i]){
      ans[1] = 1;
    }
    if(S[N - i - 1] != T[M - i - 1]){
      ans[0] = 1;
    }
  }

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

判定自体はそのまま
答えをbitで持って判定でいじってそのまま出力できるようにした

公式解説

省略

C - Festival

$${N}$$日間のお祭りが開催され、そのうち$${A_{1},A_{2},…A_{M}}$$日目の$${M}$$日花火が上がる
ただしお祭りの最終日には花火が上がることが保証されている
全ての日数に対して何日後に花火が上がるか求める問題

自分の回答

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

  vector<int> ans(N + 1, 0);
  int j = M - 1;
  for(int i = N; i > 0; i--){
    if(i == A[j]){
      j--;
      continue;
    }
    else{
      ans[i] = ans[i + 1] + 1;
    }
  }

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

後ろから見て行ってその日に花火が上がるなら0、そうでないなら前(日付的には次の日)+1
これで計算量がNで行ける

公式解説

省略

D - Polyomino

$${4×4}$$のグリッドに収まる大きさのピースが$${3}$$つあり、そのピースを回転、移動を用いて全て使って$${4×4}$$のグリッドをはみ出しや重複無く埋めることができるか判定する問題

自分の回答

int main(){
  vector<set<pair<int, int>>> P(3);
  for(int i = 0; i < 3; i++){
    for(int j = 0; j < 4; j++){
      for(int k = 0; k < 4; k++){
        char c;
        cin >> c;
        if(c == '#'){
          P[i].insert({j, k});
        }
      }
    }
  }

  for(int _ = 0; _ < 4; _++){
    set<pair<int, int>> pr0;
    for(auto [pi, pj] : P[0]){
      pr0.insert({3 - pj, pi});
    }
    P[0] = pr0;
    for(int ci0 = -3; ci0 < 4; ci0++){
      for(int cj0 = -3; cj0 < 4; cj0++){
        set<pair<int, int>> c0;
        bool in = true;
        for(auto [i, j] : P[0]){
          int ci = i + ci0, cj = j + cj0;
          if(ci < 0 || ci > 3 || cj < 0 || cj > 3){
            in = false;
            break;
          }
          c0.insert({ci, cj});
        }
        if(in == false){
          continue;
        }

        for(int __ = 0; __ < 4; __++){
          set<pair<int, int>> pr1;
          for(auto [pi, pj] : P[1]){
          pr1.insert({3 - pj, pi});
          }
          P[1] = pr1;
          for(int ci1 = -3 ; ci1 < 4; ci1++){
            for(int cj1 = -3 ; cj1 < 4; cj1++){
              set<pair<int, int>> c1;
              in = true;
              for(auto [i, j] : P[1]){
                int ci = i + ci1, cj = j + cj1;
                if(ci < 0 || ci > 3 || cj < 0 || cj > 3){
                  in = false;
                  break;
                }
                c1.insert({ci, cj});
              }
              if(in == false){
                continue;
              }

              for(int ___ = 0; ___ < 4; ___++){
                set<pair<int, int>> pr2;
                for(auto [pi, pj] : P[2]){
                pr2.insert({3 - pj, pi});
                }
                P[2] = pr2;
                for(int ci2 = -3; ci2 < 4; ci2++){
                  for(int cj2 = -3; cj2 < 4; cj2++){
                    set<pair<int, int>> c2;
                    in = true;
                    for(auto [i, j] : P[2]){
                      int ci = i + ci2, cj = j + cj2;
                      if(ci < 0 || ci > 3 || cj < 0 || cj > 3){
                        in = false;
                        break;
                      }
                      c2.insert({ci, cj});
                    }
                    if(in == false){
                      continue;
                    }

                    set<pair<int, int>> gri;
                    bool d = false;
                    for(auto p : c0){
                      if(gri.count(p)){
                        d = true;
                      }
                      gri.insert(p);
                    }
                    for(auto p : c1){
                      if(gri.count(p)){
                        d = true;
                      }
                      gri.insert(p);
                    }
                    for(auto p : c2){
                      if(gri.count(p)){
                        d = true;
                      }
                      gri.insert(p);
                    }
                    if(d){
                      continue;
                    }

                    if(gri.size() == 16){
                      printf("Yes\n");
                      return 0;
                    }
                  }
                }
              }
            }
          }
        }
      }
    }
  }
  printf("No\n");
}

総当たり

関数を作れば多少はきれいになるだろうけどそれでも書くのすごい重いしいい方法無いもんかね

公式解説

def I():
    inp = [input().replace(".", "0").replace("#", "1") for _ in range(4)]
    a = sum([int(inp[i][::-1], 2) << 5 * i for i in range(4)])
    b = sum([int(inp[i], 2) << 5 * (3 - i) for i in range(4)])
    c = sum([int(inp[i], 32) << i for i in range(4)])
    d = sum([int(inp[i][::-1], 32) << 3 - i for i in range(4)])
    for x in (a, b, c, d):
        x //= x & -x
        for i in range(20):
            yield x << i

A, B, C = list(I()), list(I()), list(I())
for a in A:
    for b in B:
        for c in C:
            if 0 == a & b == a & c == b & c and a | b | c == 507375:
                print("Yes")
                exit()
print("No")

https://atcoder.jp/contests/abc322/editorial/7310より
コードはPyPy3によるもの

bitを使って判定
そんなやり方があるのか

なるほど

E - Product Development

ある商品には$${K}$$個のパラメーターがあり、現段階では全てのパラメーターは$${0}$$である
$${N}$$個の開発案があり、$${i}$$個めの開発案で$${j}$$番目のパラメーターは$${A_{i,j}}$$上がり、コストは$${C_{i}}$$かかる
同じ開発案を複数回行うことはできない
全てのパラメーターを$${P}$$以上にするのに必要な最小コストはいくらか求める問題

自分の回答

同じ開発案の縛りが無ければ全てのパラメーターで動的計画法出来たんだけどその部分をどうするか思いつかなかった

公式解説

https://atcoder.jp/contests/abc322/editorial/7305より

そこにi番目の開発案まででを加えればよかっただけか…

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