AtCoder Beginner Contest 323

OKU

A - Weak Beats : AC(5:25)
B - Round-Robin Tournament : AC(12:20)
C - World Tour Finals : AC(28:14)
D - Merge Slimes : AC(46:46)
E - Playlist : 提出無し

A - Weak Beats

「0」と「1」からなる長さ$${16}$$の文字列$${S}$$が与えられ、その偶数文字目が全て「0」ならば「Yes」を、そうでないならば「No」を出力する問題

自分の回答

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

  for(int i = 1; i < S.size(); i += 2){
    if(S[i] == '1'){
      printf("No\n");
      return 0;
    }
  }
  printf("Yes\n");
}

そのまま

公式解説

省略

B - Round-Robin Tournament

$${1}$$から$${N}$$までの番号のついた人が総当たり戦を行った
勝った数の多い方が順位が上であり、等しい場合は番号の小さい方が上となる
順位の高い順にその人の番号を出力する問題

自分の回答

int main(){
  int N;
  cin >> N;
  vector<string> S(N);
  for(int i = 0; i < N; i++){
    cin >> S[i];
  }

  vector<pair<int, int>> W;
  for(int i = 0; i < N; i++){
    W.push_back({count(S[i].begin(), S[i].end(), 'o'), i});
  }

  auto cmp = [](const pair<int, int> &x, const pair<int, int> &y){
    if(x.first == y.first){
      return x.second < y.second;
    }
    return x.first > y.first;
  };

  sort(W.begin(), W.end(), cmp);

  for(int i = 0; i < N; i++){
    printf("%d ", W[i].second + 1);
  }
  printf("\n");
}

勝ち数降順、番号昇順でソートする関数を作って終わり

公式解説

int main() {
	int n;
	cin >> n;
	vector<int> win(n), p(n);
	iota(p.begin(), p.end(), 0);
	for(int i = 0; i < n; i++) {
		string s;
		cin >> s;
		win[i] = count(s.begin(), s.end(), 'o');
	}
	auto cmp = [&](int i, int j) {
		return win[i] > win[j];
	};
	stable_sort(p.begin(), p.end(), cmp);
	for(int i = 0; i < n; i++) cout << p[i] + 1 << " \n"[i == n - 1];
}

https://atcoder.jp/contests/abc323/editorial/7350より

stable_sortってのがあるのか
値が等しいなら元の順のままだから勝ち数降順の関数を入れるだけでOK

なるほど

C - World Tour Finals

$${N}$$人のプレイヤーが参加するコンテストが行われている
問題は$${M}$$問でそれぞれ$${A_{i}}$$点である
各プレイヤーが今の段階でどの問題を解いたかを表す文字列$${S_{i}}$$が与えられ、プレイヤー$${i}$$の得点は解いた問題の点数の合計とボーナス点$${i}$$の合計である
全てのプレイヤーにおいて、そのプレイヤーが最低何問解けば他のプレイヤーの現在の得点を上回れるか求める問題

自分の回答

int main(){
  int N, M;
  cin >> N >> M;
  vector<pair<int, int>> A(M);
  for(int i = 0; i < M; i++){
    int a;
    cin >> a;
    A[i] = {a, i};
  }
  vector<int> P(N);
  vector<string> S(N);
  int ma = 0, t;
  for(int i = 0; i < N; i++){
    cin >> S[i];
    int sum = i + 1;
    for(int j = 0; j < M; j++){
      if(S[i][j] == 'o'){
        sum += A[j].first;
      }
    }
    P[i] = sum;
    if(sum > ma){
      ma = sum;
      t = i;
    }
  }

  sort(A.begin(), A.end(), greater<pair<int, int>>());
  for(int i = 0; i < N; i++){
    int ans = 0;
    for(int j = 0; j < M; j++){
      if(i == t || P[i] > ma){
        break;
      }
      if(S[i][A[j].second] == 'o'){
        continue;
      }
      P[i] += A[j].first;
      ans++;
    }
    printf("%d\n", ans);
  }
}

解いてない問題の中から点数の高い順に取っていってトップになれるか見て行って終わり
点数の高い順に見るのを早く終わらせるために点数とそのインデックスのpairを降順ソートしたものを作る

Nが100まであるからP[i]>=maだとダメかと思って初期トップを持つtを作ったけど人0がいないから大丈夫だったか

公式解説

省略

D - Merge Slimes

$${N}$$種類のスライムがいて、サイズは$${S_{i}}$$が$${C_{i}}$$匹である
同じサイズのスライム$${2}$$匹を合成し、元のサイズの倍のサイズのスライム$${1}$$匹にすることができる
スライムを最小何匹にすることができるか求める問題

自分の回答

int main(){
  int N;
  cin >> N;
  map<int64_t, int64_t> S;
  for(int i = 0; i < N; i++){
    int64_t s, c;
    cin >> s >> c;
    S[s] = c;
  }

  int64_t ans = 0;
  for(auto [s, c] : S){
    if(c / 2 >= 1){
      S[s * 2] += c / 2;
    }
    ans += c % 2;
  }

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

小さい方から可能な限り合成していけばいいからそうして終わり

計算量削減する方法ありそうだけどどうすればいいんだろ

公式解説

ちょっと理解しきれなかった

E - Playlist

$${N}$$曲からなるプレイリストがあり、曲の長さは$${T_{i}}$$秒である
$${N}$$曲の中から等確率で$${1}$$曲選び、その曲を最後まで流すことが繰り返されるランダム再生を開始してから$${X+0.5}$$秒後に曲$${1}$$が再生されている確率を$${mod998244353}$$で求める問題

自分の回答

動的計画法をするのはわかるんだけどその先がわからなかった

公式解説

using mint = modint998244353;

int main(void) {
	int n,x;
	mint r,ans;
	
	cin>>n>>x;
	vector<int>t(n);
	for(int i=0;i<n;i++)cin>>t[i];

	vector<mint>p(x+1);
	r=((mint)1)/((mint)n);
	p[0]=1;
	if(t[0]>x)ans+=p[0]/((mint)n);
	for(int i=1;i<=x;i++){
		for(int j=0;j<n;j++)if(t[j]<=i)p[i]+=p[i-t[j]];
		p[i]*=r;
		if(i+t[0]>x)ans+=p[i]*r;
	}

	cout<<ans.val()<<endl;
	return 0;
}

https://atcoder.jp/contests/abc323/editorial/7357より

時刻iにおいて曲が切り替わる確率を求めて、そこから曲1が流れたら時刻xでも流れている範囲になったらその確率×曲1が流れる確率の和か

なるほど

この記事が気に入ったらサポートをしてみませんか？