AtCoder Beginner Contest 281

AtCoder Beginner Contest 281 - AtCoder

結果

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次元配列にして余りも入れるのか

なるほど