AtCoder Beginner Contest 324

Japan Registry Services (JPRS) Programming Contest 2023 (AtCoder Beginner Contest 324) - AtCoder

結果

A - Same : AC(1:29)
B - 3-smooth Numbers : AC(8:27)
C - Error Correction : AC(93:04)(3ペナ)
D - Square Permutation : AC(70:21)(1ペナ)

A - Same

$${N}$$個の整数が与えられ、それが全て等しいか判定する問題

自分の回答

int main(){
  int N;
  cin >> N;
  set<int> A;
  for(int i = 0; i < N; i++){
    int a;
    cin >> a;
    A.insert(a);
  }

  printf(A.size() == 1 ? "Yes\n" : "No\n");
}

そのまま

公式解説

省略

B - 3-smooth Numbers

正整数$${N}$$が与えられ、$${N=2^x3^y}$$となる整数$${x,y}$$が存在するか求める問題

自分の回答

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

  while(N % 2 == 0 || N % 3 == 0){
    if(N % 2 == 0){
      N /= 2;
    }
    else{
      N /= 3;
    }
  }

  printf(N == 1 ? "Yes\n" : "No\n");
}

2と3で可能な限り割っていって1になるか

公式解説

省略

C - Error Correction

高橋君が英小文字からなる文字列$${T}$$を送信した結果、青木君は英小文字からなる文字列$${T'}$$を受信した
$${T'}$$は$${T}$$から変更されてしまっている可能性があり、以下の$${4}$$つのうちちょうど$${1}$$つが成り立つ
・$${T'}$$は$${T}$$と等しい
・$${T'}$$は$${T}$$のいずれか$${1}$$つの位置に英小文字を$${1}$$つ挿入して得られる文字列である
・$${T'}$$は$${T}$$から$${1}$$文字を削除して得られる文字列である
・$${T'}$$は$${T}$$のある$${1}$$文字を別の英小文字に変更して得られる文字列である
青木君が受信した文字列$${T'}$$と英小文字からなる文字列が$${N}$$個与えられるため、その中で$${T}$$と等しい可能性のあるものを全て求める問題

自分の回答

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

  vector<int> ans;
  int cou = 0;
  for(int i = 1; i <= N; i++){
    string s;
    cin >> s;
    int ts = TP.size(), ss = s.size();
    int k = 0, l = 0, c = 0;
    if(ts == ss){
      while(k < ts){
        if(c >= 2){
          break;
        }
        if(TP[k] != s[l]){
          c++;
        }
        k++;
        l++;
      }
    }
    else if(ts == ss + 1){
      while(k < ts){
        if(c >= 2){
          break;
        }
        if(TP[k] != s[l]){
          k++;
          c++;
          continue;
        }
        k++;
        l++;
      }
    }
    else if(ts == ss - 1){
      while(k < ts){
        if(c >= 2){
          break;
        }
        if(TP[k] != s[l]){
          l++;
          c++;
          continue;
        }
        k++;
        l++;
      }
    }
    else{
      c = 10;
    }
    if(c <= 1){
      cou++;
      ans.push_back(i);
    }
  }

  printf("%d\n", cou);
  for(int x : ans){
    printf("%d ", x);
  }
}

文字列の違いの数を文字列の長さの違いごとに調べて違いが1以下ならokなんだけどもっときれいにできるはず

分けないでやろうとしたらダメで3ペナ

公式解説

typedef long long ll;

ll n;
string s[500001], t2;
ll a[500001], b[500001];

ll calc(const string &s, const string &t)
{
  for(int i = 0; i < (int)t.size(); i++){
    if(i >= s.size()) return s.size();
    if(s[i] != t[i]) return i;
  }
  return t.size();
}

int main(void){
  cin >> n >> t2;
  for(int i = 1; i <= n; i++) cin >> s[i];

  for(int i = 1; i <= n; i++) a[i] = calc(s[i], t2);
  reverse(t2.begin(), t2.end());
  for(int i = 1; i <= n; i++){
    reverse(s[i].begin(), s[i].end());
    b[i] = calc(s[i], t2);
  }
  
  vector<ll> ans;
  for(int i = 1; i <= n; i++){
    const string &t = s[i];
    bool flag = false;
    if(a[i] == t.size() && t.size() == t2.size()) flag = true;
    if(a[i]+b[i] >= t.size() && t.size()+1 == t2.size()) flag = true;
    if(a[i]+b[i] >= t.size()-1 && t.size()-1 == t2.size()) flag = true;
    if(a[i]+b[i] == t.size()-1 && t.size() == t2.size()) flag = true;
    if(flag) ans.push_back(i);
  }
  
  cout << ans.size() << endl;
  for(auto x : ans) cout << x << " ";
  cout << endl;
  
  return 0;
}

https://atcoder.jp/contests/abc324/editorial/7411より

前後からそれぞれ何文字等しいかを見てそれとT'とTの文字数を比較していくのか

なるほど

D - Square Permutation

数字のみからなる長さ$${N}$$の文字列$${S}$$が与えられ、それを並び替えたものを$${10}$$進数の数字として解釈したものが平方数であるものの数がいくつあるか求める問題

自分の回答

int main(){
  int N;
  string S;
  cin >> N >> S;
  map<char, int> C;
  int zero = 0;
  for(char c : S){
    if(c == '0'){
      zero++;
      continue;
    }
    C[c]++;
  }

  int ans = 0;
  for(int64_t i = 0; i * i < pow(10, N); i++){
    int64_t sq = i * i;
    map<char, int> nsq;
    int sqz = 0;
    for(char c : to_string(sq)){
      if(c == '0'){
        sqz++;
        continue;
      }
      nsq[c]++;
    }
    if(sqz <= zero && C == nsq){
      ans++;
    }
  }

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

平方数を総当たりして各文字が何回出てくるかが等しいかで可能か判定
0は別で持って文字列の0の数>=平方数の0の数ならok

0が平方数な認識が無くて1ペナ