コンテスト名
CodeQUEEN 2024 予選 (AtCoder Beginner Contest 358)
コンテストURL
開催日
2024/06/15 21:00-22:40
A: Welcome to AtCoder Land
解法
- 文字列を比較して判定する
ABC358A.cpp
#include <iostream>
#include <string>
using namespace std;
int main(){
string s, t;
cin >> s >> t;
if(s=="AtCoder" && t=="Land"){
cout << "Yes" << endl;
}else{
cout << "No" << endl;
}
return 0;
}
B: Ticket Counter
解法
- $i$ 番目に並んだ人について、 $i-1$ 番目の人がチケットを購入し終わった時間 $F_{i-1}$ で場合分けする
- $i-1$ 番目の人がチケットを購入し終わった時間 $F_{i-1}$ が $T_i$ より遅ければ、 $F_{i-1}$ から購入手続きを開始する
- $i-1$ 番目の人がチケットを購入し終わった時間が $T_i$ より早ければ、 $T_i$ から購入手続きを開始する
ABC358B.cpp
#include <iostream>
using namespace std;
int main(){
int n, a;
cin >> n >> a;
int time = 0, t;
for(int i=0; i<n; i++){
cin >> t;
if(time>=t){
time += a;
}else{
time = t + a;
}
cout << time << '\n';
}
return 0;
}
C: Popcorn
解法
- bit 全探索
- 順列全探索でも解けるが、 $O(2^N) < O(N!)$ であるため bit 全探索のほうが高速
- どのポップコーン売り場を訪れるかを bit 全探索する
-
unordered_set<int>で購入した味を記録する
ABC358C.cpp
#include <iostream>
#include <vector>
#include <string>
#include <algorithm>
#include <unordered_set>
using namespace std;
int main(){
int n, m;
cin >> n >> m;
vector<string> S(n);
for(int i=0; i<n; i++){
cin >> S[i];
}
int minv = n;
for(int i=0; i<(1<<n); i++){
unordered_set<int> St;
int cnt = 0;
for(int j=0; j<n; j++){
if(i&(1<<j)){
cnt++;
for(int l=0; l<m; l++){
if(S[j][l]=='o'){
St.insert(l);
}
}
}
}
if(St.size()==m){
minv = min(minv, cnt);
}
}
cout << minv << endl;
return 0;
}
D: Souvenirs
解法
- ソートしてから二分探索
- 箱と人の順番は関係ないため、昇順にソートする
- $B_i$ 個以上のお菓子が入った箱のうち、最小個数の箱を二分探索で求める
- すでにほかの人に渡した箱は選択できないことに注意する
ABC358D.cpp
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
int n, m;
cin >> n >> m;
vector<int> A(n), B(m);
for(int i=0; i<n; i++){
cin >> A[i];
}
for(int i=0; i<m; i++){
cin >> B[i];
}
sort(A.begin(), A.end());
sort(B.begin(), B.end());
int boxnum = 0, pre = -1;
long long int sum = 0;
for(int i=0; i<m; i++){
boxnum = lower_bound(A.begin(), A.end(), B[i]) - A.begin();
if(pre>=boxnum){
boxnum = pre + 1;
}
if(boxnum>=n){
cout << -1 << endl;
return 0;
}
sum += A[boxnum];
pre = boxnum;
}
cout << sum << endl;
return 0;
}
E: Alphabet Tiles
解法
- 動的計画法と二項係数
- $\text{dp}[i][j]$ := $i$ 番目までの文字を使って長さ $j$ の文字列を作る組み合わせ数とおく
- $\text{dp}[i][j] \gets \text{dp}[i][j] + \text{dp}[i-1][j-l] \times {}_{j-l+1} \mathrm{H}_l$
- $i-1$ 番目の文字まで使った長さ $j-l$ の文字列に $i$ 番目の文字を $l$ 個挿入することを考える
- 挿入場所は重複組み合わせ ${}_{j-l+1} \mathrm{H}_l = \binom{j}{l}$ 通り
- 二項係数の値も $\binom{n}{r} = \binom{n-1}{r} + \binom{n-1}{r-1}$ より動的計画法で求められる
ABC358E.cpp
#include <iostream>
#include <vector>
using namespace std;
int main(){
const int MOD = 998244353;
int k;
cin >> k;
vector<int> C(26);
for(int i=0; i<26; i++){
cin >> C[i];
}
vector<vector<long long int>> dp(26+1, vector<long long int>(k+1));
for(int i=0; i<=26; i++){
dp[i][0] = 1;
}
vector<vector<int>> Com(k+1, vector<int>(k+1));
Com[0][0] = 1;
for(int i=1; i<=k; i++){
Com[i][0] = 1;
for(int j=1; j<=k; j++){
Com[i][j] = (Com[i-1][j] + Com[i-1][j-1]) % MOD;
}
}
for(int i=1; i<=26; i++){
for(int j=1; j<=k; j++){
for(int l=0; l<=min(j, C[i-1]); l++){
dp[i][j] += (dp[i-1][j-l]%MOD * Com[j][l]) % MOD;
dp[i][j] %= MOD;
}
}
}
long long int sum = 0;
for(int i=1; i<=k; i++){
sum += dp[26][i];
sum %= MOD;
}
cout << sum << endl;
return 0;
}