AtCoder Beginner Contest 301

パナソニックグループプログラミングコンテスト2023（AtCoder Beginner Contest 301） - AtCoder

結果

A - Overall Winner : AC(3:44)
B - Fill the Gaps : AC(12:55)
C - AtCoder Cards : AC(25:50)
D - Bitmask : WA

A - Overall Winner

高橋君と青木君が$${N}$$回の試合を行い、その結果を表す長さ$${N}$$の文字列$${S}$$が与えられる
$${i}$$文字目が「T」ならば高橋君が、「A」ならば青木君が$${i}$$試合目に勝ったことを表す
勝利回数の多い方を総合勝者とし、同数であるならば先にその回数勝った方を総合勝者とする
どちらが総合勝者であるか判定する問題

自分の回答

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

  if(count(S.begin(), S.end(), 'T') > count(S.begin(), S.end(), 'A')){
    printf("T\n");
  }
  else if(count(S.begin(), S.end(), 'T') < count(S.begin(), S.end(), 'A')){
    printf("A\n");
  }
  else{
    if(S[N - 1] == 'T'){
      printf("A\n");
    }
    else{
      printf("T\n");
    }
  }
}

そのままTとAの数を比較
同数なら最後の文字でない方

forで一周した方が綺麗だったかな

公式解説

https://atcoder.jp/contests/abc301/editorial/6354より

そうかN/2勝したらそこで出力すればいいのか

B - Fill the Gaps

正整数からなる長さ$${N}$$の数列$${A}$$が与えられ、全ての隣接する2項の差の絶対値が$${1}$$になるよう数を挿入した結果の数列を求める問題

自分の回答

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

  printf("%d ", A[0]);
  for(int i = 1; i < N; i++){
    if(A[i - 1] < A[i]){
      for(int j = A[i - 1] + 1; j < A[i]; j++){
        printf("%d ", j);
      }
    }
    else{
      for(int j = A[i - 1] - 1; j > A[i]; j--){
        printf("%d ", j);
      }
    }
    printf("%d ", A[i]);
  }
  printf("\n");
}

そのまま

公式解説

省略

C - AtCoder Cards

英小文字1文字か「@」が書かれたカードが十分多くある
カードを同じ枚数づつ2列に並べ、「@」のカードを「a」「t」「c」「o」「d」「e」「r」のいずれかのカードと置き換えて2列が一致していれば勝ちというゲームをする
並べた時点での列を表す文字列$${S,T}$$が与えられ、カードを置き換える時に列内のカードを自由に並び替えるイカサマをしても良いとき、勝利できるかを判定する問題

自分の回答

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

  vector<int> Sc(123, 0), Tc(123, 0);
  int at = 0;
  for(char c : S){
    if(c == '@'){
      at++;
    }
    else{
      Sc[c]++;
    }
  }
  for(char c : T){
    if(c == '@'){
      at++;
    }
    else{
      Tc[c]++;
    }
  }

  bool can = true;
  for(int i = 97; i <= 122; i++){
    if(i == 'a' || i == 't' || i == 'c' || i == 'o' || i == 'd' || i == 'e' || i == 'r'){
      at -= abs(Sc[i] - Tc[i]);
    }
    else{
      if(Sc[i] != Tc[i]){
        can = false;
      }
    }
  }
  if(can && at >= 0){
    printf("Yes\n");
  }
  else{
    printf("No\n");
  }
}

STそれぞれ各文字が何回出てくるかを調べ、atcoder以外は@で作ることができないため共に一致するかを調べる
atcoderは@の回数を残機として回数の差を残機を消費して埋め合わせる
最後にatcoder以外が一致し、残機が残っているならばOK

公式解説

省略

D - Bitmask

「0」「1」「?」からなる文字列$${S}$$と整数$${N}$$が与えられ、$${S}$$に含まれる「?」を「0」か「1」に置き換えて2進数として見た時にできるの値の集合を$${T}$$とする
$${T}$$の中で$${N}$$以下のうち最大の値を求める問題、ただし存在しないならば-1とする

自分の回答

Nも2進数にしてSの全ての桁においてそれ以上の桁で出てきた1の数がS<Nとなるように?を上から1にすればいいのはわかったけどすでにある1との兼ね合いとかの部分が作れなかった

後から思えば?を総当たりしても多分時間は足りるから上から総当たりでもいいのかも

公式解説

    S, N = list(reversed(input())), int(input())
    s = 0
    for i in range(len(S)):
        s |= (S[i] == '1') << i
    if s > N:
        print(-1)
    else:
        for i in reversed(range(len(S))):
            if S[i] == '?' and (s | 1 << i) <= N:
                s |= 1 << i
        print(s)

Pythonによるもの
https://atcoder.jp/contests/abc301/editorial/6347より

まず?を全て0にしても超えるなら-1、そうでないなら?を上から1にしてみて超えないなら保持、超えるなら0にして次へ

なるほど