AtCoder Beginner Contest 329

Ｓｋｙ Inc, Programming Contest 2023（AtCoder Beginner Contest 329） - AtCoder

結果

A - Spread : AC(1:26)
B - Next : AC(3:47)
C - Count xxx : AC(8:12)
D - Election Quick Report : AC(13:51)
E - Stamp : 提出無し

A - Spread

英大文字からなる文字列$${S}$$が与えられるため、各文字の間に「 」を入れて出力する問題

自分の回答

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

  for(int i = 0; i < S.size(); i++){
    printf("%c", S[i]);
    printf(i == S.size() - 1 ? "\n" : " ");
  }
}

そのまま

公式解説

省略

B - Next

$${N}$$個の整数が与えられるため、その中で最大でない中で最大の値を求める問題

自分の回答

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

  S.erase(*rbegin(S));
  printf("%d\n", *rbegin(S));
}

setに入れて最大値を消して最大値を出力

公式解説

省略

C - Count xxx

英小文字からなる長さ$${N}$$の文字列$${S}$$が与えられ、$${1}$$種類の文字からなる$${S}$$の部分文字列が何種類あるか求める問題

自分の回答

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

  int ans = 0;
  for(int c = 'a'; c <= 'z'; c++){
    int nma = 0, ma = 0;
    for(int i = 0; i < N; i++){
      if(S[i] == c){
        nma++;
      }
      else{
        ma = max(ma, nma);
        nma = 0;
      }
    }
    ans += max(nma, ma);
  }

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

各文字ごとに最大何連続かを求めてその和

公式解説

int main() {
    int n;
    string s;
    cin >> n >> s;
    vector<int> mx(26);
    int l = 0;
    while (l < n) {
        int r = l + 1;
        while (r < n and s[l] == s[r]) ++r;
        int c = s[l] - 'a';
        mx[c] = max(mx[c], r - l);
        l = r;
    }
    int ans = 0;
    for (int i = 0; i < 26; i++) {
        ans += mx[i];
    }
    cout << ans << endl;
}

https://atcoder.jp/contests/abc329/editorial/7719より

そうかわざわざaからzまででやらなくても隣接してるのが同じかで連続数数えられるか
この方が計算量少ないし

なるほど

D - Election Quick Report

$${N}$$人の候補者から当選者を$${1}$$人選ぶ選挙が行われ、$${M}$$票の投票があった
最も得票数の多い人が当選となり、得票数が最も多い人が複数いる場合はその中で最も番号の小さい人が当選となる
$${1}$$票ごとにその時点で開票が終了した場合の当選者を求める問題

自分の回答

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

  vector<int> A(N + 1, 0);
  int tv = 0, th = 0;
  for(int i = 0; i < M; i++){
    int a;
    cin >> a;
    A[a]++;
    if(A[a] > tv){
      tv = A[a];
      th = a;
    }
    else if(A[a] == tv && a < th){
      th = a;
    }

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

現在の各候補者の得票数と一つ前での当選者とその票数を持っておいてそれを比較

公式解説

省略

E - Stamp

英大文字からなる長さ$${N}$$の文字列$${S}$$と長さ$${M}$$の文字列$${T}$$がある
「#」からなる長さ$${N}$$の文字列$${X}$$があり、その中から連続する$${M}$$文字を$${T}$$に書き換える操作を任意の回数することで$${S}$$と一致させることが可能か判定する問題

自分の回答

判定は思いつきはしたけどアルゴリズムにするのに微妙な気がしたし実際ぐちゃぐちゃになって書けなかった
けど他にいい方法も思いつかなかった

公式解説

int main() {
    int n, m;
    string s, t;
    cin >> n >> m >> s >> t;
    vector<bool> used(n - m + 1);
    queue<int> q;
    auto check = [&](int i) {
        if (used[i]) return;
        bool ok = true;
        for (int j = 0; j < m; j++) {
            ok &= (s[i + j] == '#' or s[i + j] == t[j]);
        }
        if (ok) {
            used[i] = true;
            q.push(i);
        }
    };
    for (int i = 0; i < n - m + 1; i++) check(i);
    while (!q.empty()) {
        int i = q.front();
        q.pop();
        for (int j = 0; j < m; j++) s[i + j] = '#';
        for (int j = max(i - m + 1, 0); j <= min(i + m - 1, n - m); j++) {
            check(j);
        }
    }
    cout << (s == string(n, '#') ? "Yes" : "No") << endl;
}

https://atcoder.jp/contests/abc329/editorial/7724より

#をワイルドカードとしてTと完全一致する部分を消し(#に置き換え)たらその前後M文字を調べるを繰り返すのか

なるほど