AtCoder Beginner Contest 326

2023年10月30日 15:31

結果

A - 2UP3DOWN : AC(3:04)
B - 326-like Numbers : AC(7:13)
C - Peak : AC(17:02)
D - ABC Puzzle : AC(92:47)

A - 2UP3DOWN

$${100}$$階建てのビルがあり、$${2}$$階までの上りと$${3}$$階までの下りでは階段を使い、それ以外ではエレベーターを使う
$${X}$$階から$${Y}$$階の移動に階段を使うか求める問題

自分の回答

int main(){
  int X, Y;
  cin >> X >> Y;

  if(Y >= X - 3 && Y <= X + 2){
    printf("Yes\n");
  }
  else{
    printf("No\n");
  }
}

そのまま

公式解説

省略

B - 326-like Numbers

$${3}$$桁の整数であって百の位の数×十の位の数=一の位の数である数を326-like numberとする
整数$${N}$$が与えられ、それ以上で最小の326-like numberを求める問題

自分の回答

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

  int d1 = N % 10, d2 = N / 10 % 10, d3 = N / 100;
  while(true){
    if(d1 == d2 * d3){
      printf("%d%d%d\n", d3, d2, d1);
      return 0;
    }

    d1++;
    if(d1 == 10){
      d1 = 0;
      d2++;
    }
    if(d2 == 10){
      d2 = 0;
      d3++;
    }
  }
}

そのまま
だけど位の分割は判定時にした方が良かったか

公式解説

省略

C - Peak

数直線上に$${N}$$個のプレゼントが置かれており、各座標は$${A_{i}}$$である
数直線上の長さ$${N}$$の半開区間を選び、その範囲のプレゼントを全て得ることができる
最大でいくつプレゼントを得られるか求める問題

自分の回答

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

  sort(A.begin(), A.end());
  queue<int> sec;
  int now = 0, ans = 0;
  for(int i = 0;i < N; i++){
    sec.push(A[i]);
    now++;
    while(A[i] - sec.front() >= M){
      sec.pop();
      now--;
    }
    ans = max(ans, now);
  }

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

ソートして尺取り法

公式解説

省略

D - ABC Puzzle

整数$${N}$$と「A」「B」「C」からなる長さ$${N}$$の文字列$${R,C}$$が与えられる
$${N×N}$$のマス目があり、各マスは「A」「B」「C」の一文字もしくは空白を入れられる
以下の条件を全て満たすことが可能か、また、可能ならばそのパターンを$${1}$$つ求める問題
・各行、列には「A」「B」「C」がちょうど$${1}$$つ含まれる
・$${i}$$行目にある文字の中で一番左にある文字は$${R}$$の$${i}$$文字目と一致する
・$${i}$$列目にある文字の中で一番上にある文字は$${C}$$の$${i}$$文字目と一致する

自分の回答

bool RC(vector<char> &S, int N, int d, char r){
  bool f = true, n = true;
  int c = 0;
  for(int i = 0; i < N; i++){
    if(S[i] == '.'){
      continue;
    }
    c++;
    if(f){
      if(S[i] != r){
        return false;
      }
      f = false;
    }
  }
  return c == 3 ? true : false;
}

bool EC(vector<vector<char>> &S, string C, int N){
  for(int j = 0; j < N; j++){
    bool f = true;
    int a = 0, b = 0, c = 0;
    for(int i = 0; i < N; i++){
      if(S[i][j] == '.'){
        continue;
      }
      if(f){
        if(S[i][j] != C[j]){
          return false;
        }
        f = false;
      }
      if(S[i][j] == 'A'){
        a++;
      }
      else if(S[i][j] == 'B'){
        b++;
      }
      else{
        c++;
      }
    }
    if(a != 1 || b != 1 || c != 1){
      return false;
    }
  }
  return true;
}

void pri(vector<vector<char>> &S, int N){
  printf("Yes\n");
  for(int i = 0; i < N; i++){
    for(int j = 0; j < N; j++){
      printf("%c",S[i][j]);
    }
    printf("\n");
  }
  return;
}

int main(){
  int N;
  string R, C;
  cin >> N >> R >> C;
  vector<vector<char>> S(5,vector<char>(5, '.'));
  for(int i = 0; i < N; i++){
    S[i][2] = 'A';
    S[i][3] = 'B';
    S[i][4] = 'C';
  }

  bool can = false;
  vector<bool> li(N, false);
  do{
    if(RC(S[0], N, 0, R[0]) == false){
      continue;
    }

    do{
      if(RC(S[1], N, 1, R[1]) == false){
        continue;
      }

      do{
        if(RC(S[2], N, 2, R[2]) == false){
          continue;
        }
        if(N == 3){
          if(EC(S, C, N) == false){
            continue;
          }
          pri(S, N);
          return 0;
        }

        do{
          if(RC(S[3], N, 3, R[3]) == false){
            continue;
          }
          if(N == 4){
            if(EC(S, C, N) == false){
              continue;
            }
            pri(S, N);
            return 0;
          }

          do{
            if(RC(S[4], N, 4, R[4]) == false){
              continue;
            }
            if(EC(S, C, N)){
              pri(S, N);
              return 0;
            }
          }while(next_permutation(S[4].begin(), S[4].end()));
        }while(next_permutation(S[3].begin(), S[3].end()));
      }while(next_permutation(S[2].begin(), S[2].end()));
    }while(next_permutation(S[1].begin(), S[1].end()));
  }while(next_permutation(S[0].begin(), S[0].end()));

  printf("No\n");
}

最初から最大の5×5としてnext_permutationで総当たりのごり押し
60^5通りになってそのままだとTLEするけど各行でR[i]と先頭の文字の一致とか範囲内に文字が全て入っているかを見てカットすれば大丈夫

もっときれいな方法は間違いなくある

公式解説

vector<vector<string>> row(3);
bool fnd=false;
int n;
string r,c;
vector<string> grid;

void dfs(int i,int fl){
  if(fnd){return;}
  if(i==n){
    if(fl==0){
      cout << "Yes\n";
      for(auto &nx : grid){cout << nx << "\n";}
      fnd=true;
    }
    return;
  }
  for(auto &nx : row[r[i]-'A']){
    grid.push_back(nx);

    int ufl=fl;
    bool und=true;
    for(int j=0;j<n;j++){
      if(nx[j]=='.'){continue;}
      int kind=(nx[j]-'A');
      if((fl&(1<<(4*j+kind)))==0){und=false;break;}
      ufl^=(1<<(4*j+kind));
      if((fl&(1<<(4*j+3)))!=0){
        if(nx[j]!=c[j]){und=false;break;}
        ufl^=(1<<(4*j+3));
      }
    }

    if(und){dfs(i+1,ufl);}
    grid.pop_back();
  }
}

int main(){
  cin >> n >> r >> c;
  string abc="ABC";
  while(abc.size()<n){abc.push_back('.');}
  sort(abc.begin(),abc.end());
  do{
    char tg='.';
    for(auto &nx : abc){
      if(nx!='.'){tg=nx;break;}
    }
    row[tg-'A'].push_back(abc);
  }while(next_permutation(abc.begin(),abc.end()));

  dfs(0,(1<<(4*n))-1);
  if(!fnd){cout << "No\n";}
  return 0;
}

https://atcoder.jp/contests/abc326/editorial/7539より

コードのスマートさは圧倒的だけどやってることはおおよそ同じなのか

なるほどね…

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