AtCoder Beginner Contest 314

2023年8月14日 15:53

結果

A - 3.14 : AC(2:21)
B - Roulette : AC(15:02)(1ペナ)
C - Rotate Colored Subsequence : AC(27:52)
D - LOWER : AC(55:50)
E - Roulettes : 提出無し

A - 3.14

$${1}$$以上$${100}$$以下の整数$${N}$$が与えられ、円周率を小数第$${N}$$位まで出力する問題

自分の回答

int main(){
  int N;
  cin >> N;
 
  string Pi = "3.1415926535897932384626433832795028841971693993751058209749445923078164062862089986280348253421170679";
  for(int i = 0; i < N + 2; i++){
    printf("%c", Pi[i]);
  }
}

そのまま

公式解説

省略

B - Roulette

$${N}$$人の人がルーレットに参加し、それぞれ$${C_{i}}$$個の目$${A_{i,1},A_{i,2},…,A_{i,C_{i}}}$$に賭け、ルーレットの出目は$${X}$$だった
$${X}$$に賭けた人のうち、賭けた目の数が最も少ない人の数とその番号を昇順に出力する問題

自分の回答

int main(){
  int N;
  cin >> N;
  vector<vector<vector<int>>> R(37, vector<vector<int>>(38));
  for(int i = 1; i <= N; i++){
    int c;
    cin >> c;
    for(int j = 0; j < c; j++){
      int a;
      cin >> a;
      R[a][c].push_back(i);
    }
  }
  int X;
  cin >> X;

  for(int i = 0; i < 38; i++){
    if(R[X][i].empty()){
      continue;
    }
    printf("%d\n", R[X][i].size());
    for(int x : R[X][i]){
      printf("%d ", x);
    }
    return 0;
  }
  printf("0\n");
}

iに賭けた人が何個の目に賭けているかをjにした三次元配列RでR[i]を下から見て行って要素が入っているのが来たらそれを全て出力

jを一つ少なくしてRE

公式解説

省略

C - Rotate Colored Subsequence

英小文字からなる長さ$${N}$$の文字列$${S}$$与えられ、$${i}$$文字目は色$${C_{i}}$$で塗られている
色ごとに右に$${1}$$つ巡回シフトを全ての色で$${1}$$回ずつ行った後の文字列$${S}$$を求める問題

自分の回答

int main(){
  int N, M;
  string S;
  cin >> N >> M >> S;
  vector<int> C(N);
  vector<deque<char>> SC(M + 1);
  int j = 0;
  for(int i = 0;i < N; i++){
    cin >> C[i];
    SC[C[i]].push_back(S[j]);
    j++;
  }

  for(int i = 1; i <= M; i++){
    SC[i].push_front(SC[i].back());
    SC[i].pop_back();
  }

  for(int i = 0; i < N; i++){
    printf("%c", SC[C[i]].front());
    SC[C[i]].pop_front();
  }
  printf("\n");
}

色ごとに分けてdequeに入れて巡回シフト
その後は色情報からdequeの先頭を持ってくる

公式解説

int n, m;
string s;
int c[200000];
vector<int> p[200001];

int main(void)
{
    cin >> n >> m;
    cin >> s;
    for(int i = 0; i < n; i++) cin >> c[i];
    for(int i = 0; i < n; i++) p[c[i]].push_back(i);
    
    string t(n, '?');
    for(int i = 1; i <= m; i++){
        int k = p[i].size();
        for(int j = 0; j < k; j++) t[p[i][(j+1)%k]] = s[p[i][j]];
    }
    cout << t << endl;
    
    return 0;
}

https://atcoder.jp/contests/abc314/editorial/6950より

そうか色ごとに分けて(j+1)%p[i].size()でいいのか

なるほど

D - LOWER

英大文字及び英小文字からなる文字列$${S}$$が与えられ、その文字列に対して$${Q}$$回の操作を行う
操作は整数$${2}$$つと文字$${1}$$つからなる組$${(t_{i},x_{i},c_{i})}$$で表され
・$${t_{i}}$$が$${1}$$のとき$${S}$$の$${x}$$文字目を$${c}$$にする
・$${t_{i}}$$が$${2}$$のとき$${S}$$に含まれる大文字全てを小文字にする
・$${t_{i}}$$が$${3}$$のとき$${S}$$に含まれる小文字全てを大文字にする
である
$${Q}$$回の操作が終わった後の文字列を求める問題

自分の回答

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

  vector<int> sc(N,0);
  bool U = false;
  int C = 0;
  int Q;
  cin >> Q;
  for(int i = 0; i < Q; i++){
    int t, x;
    char c;
    cin >> t >> x >> c;
    if(t == 1){
      S[x - 1] = c;
      sc[x - 1] = i;
    }
    else if(t == 2){
      U = false;
      C = i;
    }
    else{
      U = true;
      C = i;
    }
  }

  for(int i = 0; i < N; i++){
    if(C <= sc[i]){
      printf("%c", S[i]);
    }
    else{
      printf("%c", U ? toupper(S[i]) : tolower(S[i]));
    }
  }
  printf("\n");
}

まず操作2,3が行われたら全ての文字がそっちになるからboolで今どっちかを管理
そして操作2,3の後に操作1によって変わった文字はその操作の影響を受けないため2,3が最後にいつ行われたか、1によってその文字がいつ変わったかを記録して1の操作が後ならそのまま出力、そうでないなら大文字小文字に変換して出力

公式解説

省略

E - Roulettes

$${N}$$台のルーレットがあり、$${i}$$番目のルーレットには$${P_{i}}$$個の整数が書かれていて$${C_{i}}$$円を払うことで$${1}$$回プレイできる
ルーレットをプレイするとそれで出た数字の分のポイントを得られる
ポイントを$${M}$$以上獲得するために支払う金額の期待値を求める問題

自分の回答

手も足も出ない

公式解説

int main() {
    using namespace std;

    unsigned N, M;
    cin >> N >> M;

    vector<tuple<double, unsigned, vector<unsigned>>> roulette(N);
    for (auto&&[C, P, S] : roulette) {
        cin >> C >> P;
        S = vector<unsigned>(P);
        for (auto &&s : S)cin >> s;
    }

    // 0 ポイントが出ないように調整
    for (auto&&[C, P, S] : roulette) {
        C *= P;
        erase(S, 0);
        P = size(S);
        C /= P;
    }

    vector<double> e(M, 10000 * M); // e[i] := 現在 i ポイントの状態からかかる金額の期待値
    for (const auto i : ranges::views::iota(0U, M) | ranges::views::reverse) // i の降順に計算
        for (const auto&[C, P, S] : roulette) {
            double expected = 0;
            for (const auto s : S | ranges::views::filter([i, M](auto s) { return i + s < M; }))
                expected += e[i + s]; // ルーレットをプレイしたあとにかかる金額の期待値

            e[i] = min(e[i], C + expected / P); // C + 1 / P ∑ e[i + s] の最小値が求める e[i]
        }

    cout << e[0] << endl; // e[0] が答え
    return 0;
}

https://atcoder.jp/contests/abc314/editorial/6956より

Mポイントまでの残りポイントで0から動的計画法する感じなのかな
それでルーレットごとの期待値は全ての出目における(行き先の期待値*その数値が出る確率)の総和+回すための金額
それを全てのルーレットで見てminで埋めていく
こんな感じ？

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