AtCoder Beginner Contest 358

AtCoder Beginner Contest 358 - AtCoder

結果

A - Welcome to AtCoder Land : AC(1:16)
B - Ticket Counter : AC(5:18)
C - Popcorn : AC(17:34)
D - Souvenirs : AC(56:11)(2ペナ)
E - Alphabet Tiles : 提出無し

A - Welcome to AtCoder Land

文字列$${S,T}$$が与えられるため、$${S}$$が「AtCoder」かつ$${T}$$が「Land」か判定する問題

自分の回答

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

  if(S == "AtCoder" && T == "Land"){
    printf("Yes\n");
  }
  else{
    printf("No\n");
  }
}

そのまま

公式解説

省略

B - Ticket Counter

チケット売り場があり、そこではチケットの購入に一人当たり$${A}$$秒かかる
そのチケット売り場に$${N}$$人の人が今から$${T_{i}}$$秒後にチケットを買いに来る
チケットを買いに来たとき、前の人がチケットを買い終えていない場合はその人の後ろに並ぶ
それぞれの人がチケットを買い終えるのは今から何秒後か求める問題

自分の回答

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

  int nowt = 0;
  for(int i = 0; i < N; i++){
    int t;
    cin >> t;
    if(nowt < t){
      nowt = t;
    }
    nowt += A;

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

前の人がチケットを買い終えた時間と来た時間の遅い方からA秒後がチケットを買い終える時間のためそれをそのまま

公式解説

省略

C - Popcorn

$${N}$$個のポップコーン売り場があり、全部合わせて$${M}$$種類のポップコーンが売られている
各売り場の品ぞろえが与えられるため、最小いくつの売り場で全てのポップコーンを購入できるか求める問題

自分の回答

int main() {
  int N, M;
  cin >> N >> M;
  vector<bitset<10>> S(10);
  for(int i = 0; i < N; i++){
    string s;
    cin >> s;
    for(int j = 0; j < M; j++){
      if(s[j] == 'o'){
        S[i].set(j);
      }
    }
  }

  int ans = 10;
  for(int i = 0; i < (1 << N); i++){
    bitset<10> bit = i, cb;
    for(int j = 0; j < N; j++){
      if(bit[j]){
        cb |= S[j];
      }
    }
    if(cb.count() == M){
      ans = min(ans, (int)bit.count());
    }
  }

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

bit全探索

公式解説

省略

D - Souvenirs

$${N}$$個のお土産が売られており、それぞれ$${A_{i}}$$個のお菓子が入っていて値段も同じであり、在庫は$${1}$$つである
$${M}$$人の人にそれぞれ$${B_{i}}$$個入り以上のお土産を買った時最小の値段はいくらか求める問題

自分の回答

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

  int64_t ans = 0;
  for(int i = 0; i < M; i++){
    int64_t b;
    cin >> b;
    if(ans == -1){
      continue;
    }
    auto ite = A.lower_bound(b);
    if(!A.count(*ite)){
      ans = -1;
      continue;
    }
    ans += *ite;
    A.erase(ite);
  }

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

multisetを使ってlower_boundで求めてはそれを消していく
イテレータの仕様を微妙にわかっていなくて時間がかかった

最初vectorで削除が計算量怪しいなと思いながら提出して予想通りTLE
multisetに切り替えた後ミスがあってRE

公式解説

省略

E - Alphabet Tiles

英大文字がそれぞれ$${C_{i}}$$個以下であり、長さ$${1}$$以上$${K}$$以下の英大文字からなる文字列の個数を$${998244353}$$で割った余りを求める問題

自分の回答

動的計画法っぽいことしかわからず軸も見えなかった

公式解説

https://atcoder.jp/contests/abc358/editorial/10224より

Aまでで出来るi文字の文字列の数→Bまでで出来るj文字の文字列の数→…
としていって、前の文字列に文字を入れるパターンは$${{}_j C_{j-i}}$$で求められるからそれで動的計画法が組めるってことかな？

なるほど