AtCoder Beginner Contest 281
結果
A - Count Down:AC(1:23)
B - Sandwich Number:AC(8:57)
C - Circular Playlist:AC(18:35)
D - Max Multiple:WA
A - Count Down
$${N}$$以下の非負整数を大きい順に全て出力する問題
自分の回答
int main(){
int N;
cin >> N;
for(int i = N; i > -1; i--){
printf("%d\n", i);
}
}
そのまま
公式解説
省略
B - Sandwich Number
英大文字と数字からなる文字列$${S}$$が与えられ、それが
・一文字の英大文字
・100000以上999999以下の整数
・一文字の英大文字
の順番で連結した文字列であるかを判定する問題
自分の回答
int main(){
string S;
cin >> S;
if(S.size() != 8){
printf("No\n");
return 0;
}
for(int i = 0; i < 8; i++){
if(i == 0 || i == 7){
if(!isupper(S[i])){
printf("No\n");
return 0;
}
}
else{
if(!isdigit(S[i])){
printf("No\n");
return 0;
}
else if(i == 1 && S[i] == '0'){
printf("No\n");
return 0;
}
}
}
printf("Yes\n");
}
条件を満たす文字列は8文字になるためまずそこを判定
そしたら1文字目と8文字目が英大文字か、2~8文字目が数字か、その上で2文字目は0でないかを判定
正直もっときれいに判定できないもんかなとは思った
公式解説
fun main() {
val S = readLine()!!
println(if (Regex("^[A-Z][1-9][0-9]{5}[A-Z]$").matches(S)) "Yes" else "No")
}
https://atcoder.jp/contests/abc281/editorial/5388より
コードはKotlinのもの
正規表現で判定することができるのか
なるほど
C - Circular Playlist
$${N}$$曲からなるプレイリストがあり、曲には1から$${N}$$の番号が付けられていて曲$${i}$$は$${A_{i}}$$秒である
プレイリストを再生すると曲は番号順に再生され、曲$${N}$$が終わると曲1から再び再生される
プレイリストを再生してから$${T}$$秒後に流れている曲は何番か、またその曲が再生されてから何秒かを求める問題
自分の回答
int main(){
int64_t N, T;
cin >> N >> T;
vector<int64_t> A(N);
int64_t sum = 0, a;
for(int i = 0; i < N;i++){
cin >> a;
sum += a;
A[i] = a;
}
T %= sum;
for(int i = 0; i < N; i++){
if(T <= A[i]){
printf("%d %d\n", i + 1, T);
return 0;
}
else{
T -= A[i];
}
}
}
まず$${T}$$をプレイリスト全体の秒数で割った余りにして$${N}$$の最後まで再生される回をカット
後は曲1から順番に最後まで流れるかを判定、流れるならその秒数を$${T}$$から減らす、流れないならばその番号と$${T}$$の残り秒数を出力
公式解説
省略
D - Max Multiple
非負整数列$${A=(A_{1},A_{2},…,A_{N})}$$が与えられ、$${A}$$から$${K}$$項取り出した和の集合を$${S}$$とする
$${S}$$の中で$${D}$$の倍数であるものの最大値を求める問題
自分の回答
$${A}$$の要素数が100なら深さ優先探索で全調査いけるかなと思ったけどTLEした
それなら動的計画法かなと思ったけど求めるのが$${D}$$の倍数な所をどう処理すればいいのかわからなかった
公式解説
int main() {
int N,K,D;
cin>>N>>K>>D;
vector<int> a(N);
for(int i=0;i<N;i++)cin>>a[i];
vector dp(N+1,vector(K+1,vector<long long>(D,-1)));
dp[0][0][0] = 0;
for(int i=0;i<N;i++){
for(int j=0;j<K+1;j++){
for(int k=0;k<D;k++){
if(dp[i][j][k]==-1)continue;
//a_i を選ばない場合の遷移
dp[i+1][j][k] = max(dp[i+1][j][k],dp[i][j][k]);
//a_i を選ぶ場合の遷移
if(j!=K){
dp[i+1][j+1][(k+a[i])%D] = max(dp[i+1][j+1][(k+a[i])%D],dp[i][j][k] + a[i]);
}
}
}
}
cout<<dp[N][K][0]<<endl;
return 0;
}
https://atcoder.jp/contests/abc281/editorial/5366より
3次元配列にして余りも入れるのか
なるほど
この記事が気に入ったらサポートをしてみませんか?