AtCoder Beginner Contest 356

AtCoder Beginner Contest 356 - AtCoder

結果

A - Subsegment Reverse : AC(3:23)
B - Nutrients : AC(7:26)
C - Keys : AC(29:42)
D - Masked Popcount : AC(54:50)
E - Max/Min : 提出無し

A - Subsegment Reverse

長さ$${N}$$の数列$${A=(1,2,…,N)}$$の$${L}$$番目から$${R}$$番目までを反転した数列を出力する問題

自分の回答

int main() {
  int N, L, R;
  cin >> N >> L >> R;

  vector<int> A(N);
  for(int i = 0; i < N; i++){
    A[i] = i + 1;
  }
  reverse(A.begin() + L - 1, A.begin() + R);

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

そのまま

公式解説

省略

B - Nutrients

$${M}$$種類の栄養素についてそれぞれ$${1}$$日$${A_{i}}$$以上摂取することが目標である
今日$${N}$$品を食べ、それぞれ栄養素を$${X_{i,j}}$$摂取した
全ての栄養素において目標を達成しているか判定する問題

自分の回答

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

  vector<int> X(M, 0);
  for(int i = 0; i < N; i++){
    for(int j = 0; j < M; j++){
      int x;
      cin >> x;
      X[j] += x;
    }
  }
  for(int i = 0; i < M; i++){
    if(X[i] < A[i]){
      printf("No\n");
      return 0;
    }
  }
  printf("Yes\n");
}

そのまま

公式解説

省略

C - Keys

$${1}$$から$${N}$$までの番号が付けられた鍵がある
このうち何本かは正しい鍵で、それ以外は偽の鍵である
正しい鍵を$${K}$$本以上挿したとき開く扉があり、挿しこんだ鍵の番号とその結果を$${M}$$個与えられる
全ての結果に矛盾しない鍵の真偽の組み合わせが何通りあるか求める問題

自分の回答

int main() {
  int N, M, K;
  cin >> N >> M >> K;
  vector<pair<vector<int>, bool>> A(M);
  for(int i = 0; i < M; i++){
    int c;
    cin >> c;
    for(int j = 0; j < c; j++){
      int a;
      cin >> a;
      A[i].first.push_back(a - 1);
    }
    char r;
    cin >> r;
    if(r == 'o'){
      A[i].second = true;
    }
    else{
      A[i].second = false;
    }
  }

  int ans = 0;
  for(int i = 0; i < (1 << N); i++){
    bitset<15> bit = i;
    bool con = false;
    for(int j = 0; j < M; j++){
      auto [a, r] = A[j];
      int tk = 0;
      for(int x : a){
        if(bit[x]){
          tk++;
        }
      }
      bool res = tk >= K ? true : false;
      if(r != res){
        con = true;
        break;
      }
    }
    if(!con){
      ans++;
    }
  }

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

制約的に総当たりして判定しても問題なさそうだったからbit全探索

公式解説

省略

D - Masked Popcount

整数$${N,M}$$が与えられるため、$${i}$$と$${M}$$を$${2}$$進数でand演算した時に出る$${1}$$の個数を求める演算を$${i}$$が$${0}$$から$${N}$$まで行った総和を求める問題

自分の回答

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

  bitset<60> Mbit = M;
  int64_t ans = 0, dig = 1;
  for(int i = 0; i < 60; i++){
    dig *= 2;
    if(!Mbit[i]){
      continue;
    }
    int64_t nd = N / dig * (dig / 2) + max(0l, N % dig - dig / 2);
    ans += nd;
    ans %= 998244353;
  }

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

桁ごとに1の表れ方はパターンがあるためNまでにその桁には何回1が出るかを求めてMもその桁が1ならそれを足していく

公式解説

やり方はいろいろあるけど根本は同じっぽいかな

E - Max/Min

長さ$${N}$$の数列$${A=(A_{1},A_{2},…,A_{N})}$$が与えられるため、全てのペアにおける$${\frac{値の大きい方}{値の小さい方}}$$を小数点以下切り捨てした値の総和を求める問題

自分の回答

ソートして下から見ていけばそれは分子確定になるからその値を1倍2倍…としていってupper_boundで位置を見てみたいなことは考えたけど流石に計算量もっと減らす必要がありそうだなと
だけど他にいい方法は思いつかなかった

公式解説

Editorial - AtCoder Beginner Contest 356

ん？これ方法こそ違うけど根本の考えは一緒か？
upper_boundの部分を値の出てくる回数で累積和してる感じか

なるほど