AtCoder Beginner Contest 308

AtCoder Beginner Contest 308 - AtCoder

結果

A - New Scheme : AC(3:40)
B - Default Price : AC(12:35)
C - Standings : AC(49:48)(1ペナ)
D - Snuke Maze : AC(76:42)(1ペナ)
E - MEX : 提出無し

A - New Scheme

$${8}$$個の整数からなる数列が与えられ、それが広義単調増加であり、全ての項が$${100}$$以上$${675}$$以下かつ$${25}$$の倍数であるかを判定する問題

自分の回答

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

  bool y = true;
  for(int i = 1; i < 8; i++){
    if(S[i - 1] > S[i]){
      y = false;
    }
  }
  for(int i = 0; i < 8; i++){
    if(S[i] % 25 != 0 || S[i] < 100 || S[i] > 675){
      y = false;
    }
  }

  printf(y ? "Yes\n" : "No\n");
}

そのまま

公式解説

省略

B - Default Price

高橋君が回転寿司で$${N}$$皿食べ、食べた料理の皿の色$${C_{i}}$$が与えられる
料理の価格は皿の色と対応し、$${D_{i}}$$色の皿の値段は$${P_{i}}$$円であり、ここで示されていない色の皿は$${P_{0}}$$円である
高橋君が食べた料理の価格の総和を求める問題

自分の回答

int main(){
  int N, M;
  cin >> N >> M;
  vector<string> C(N);
  map<string, int> D;
  vector<int> P(M);
  int p0;
  for(int i = 0; i < N; i++){
    cin >> C[i];
  }
  for(int i = 0; i < M; i++){
    string s;
    cin >> s;
    D[s] = i;
  }
  for(int i = -1; i < M; i++){
    int n;
    cin >> n;
    if(i == -1){
      p0 = n;
    }
    else{
      P[i] = n;
    }
  }

  int ans = 0;
  for(string s : C){
    if(D.count(s)){
      ans += P[D[s]];
    }
    else{
      ans += p0;
    }
  }

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

色とそのインデックスを持つmapから価格を入れたvectorにアクセス

公式解説

省略

C - Standings

$${N}$$人がコイントスを何回かし、人$${i}$$は$${A_{i}}$$回表を出し$${B_{i}}$$回裏を出した
コイントスの成功率$${(\frac{A_{i}}{A_{i}+B_{i}})}$$の高い順に、成功率が同じ場合は番号の小さい順に並び替える問題

自分の回答

int main(){
  int N;
  cin >> N;
  vector<tuple<int, int, int>> pro(N);
  for(int i = 1; i <= N; i++){
    int a, b;
    cin >> a >> b;
    pro[i - 1]={a, b, i};
  }

  auto cmp=[](const tuple<int, int, int> &x, const tuple<int, int, int> &y){
    int64_t a1 = get<0>(x), b1 = get<1>(x), a2 = get<0>(y), b2 = get<1>(y);
    if(a2 * (a1 + b1) == a1 * (a2 + b2)){
      return get<2>(x) < get<2>(y);
    }
    else if(a1 * (a2 + b2) < a2 * (a1 + b1)){
      return false;
    }
    else{
      return true;
    }
  };

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

  for(auto [a, b, i] : pro){
    printf("%d ", i);
  }
  printf("\n");
}

小数を出さないようにして比較関数を作成

最初確率そのままでやってWA

公式解説

省略

D - Snuke Maze

$${H}$$行$${W}$$列のグリッドがあり、各マスには英小文字が書かれている
辺で隣接するマスに移動することを繰り返して$${(1,1)}$$から$${(H,W)}$$まで移動した時、通ったマスに書かれていた文字がs→n→u→k→e→s→…である経路が存在するかを求める問題

自分の回答

int main(){
  int H, W;
  cin >> H >> W;
  vector<vector<char>> M(H + 2, vector<char>(W + 2, '#'));
  for(int i = 1; i <= H; i++){
    for(int j = 1; j <= W; j++){
      cin >> M[i][j];
    }
  }

  queue<tuple<int, int, char>> bfs;
  vector<int> goi = {0, 1, 0, -1}, goj = {1, 0, -1, 0};
  bfs.push({1, 1, M[1][1]});
  M[1][1] = '#';
  while(!bfs.empty()){
    int nowi = get<0>(bfs.front()), nowj = get<1>(bfs.front());
    char nowc = get<2>(bfs.front());
    bfs.pop();
    for(int i = 0; i < 4; i++){
      int nexti = nowi + goi[i], nextj = nowj + goj[i];
      if((nowc == 's' && M[nexti][nextj] == 'n') || (nowc == 'n' && M[nexti][nextj] == 'u') || (nowc == 'u' && M[nexti][nextj] == 'k') || (nowc == 'k' && M[nexti][nextj] == 'e') || (nowc == 'e' && M[nexti][nextj] == 's')){
        bfs.push({nexti, nextj, M[nexti][nextj]});
        M[nexti][nextj] = '#';
      }
    }
  }

  printf(M[H][W] == '#' ? "Yes\n" : "No\n");
}

今いるマスの文字を持っておいて幅優先探索

到達マスの更新タイミングを間違えてTLE

公式解説

省略

E - MEX

$${0,1,2}$$からなる長さ$${N}$$の数列$${A=(A_{1},A_{2},…A_{N})}$$と「M」「E」「X」からなる長さ$${N}$$の文字列$${S}$$が与えられる
$${\text{mex}(a,b,c)}$$を$${a,b,c}$$のいずれとも一致しない最小の非負整数とし
$${1 \leqq i \leqq j \leqq k \leqq N}$$かつ$${S_{i}S_{j}S_{k}=}$$MEXを満たす整数の組$${(i,j,k)}$$すべてにおける$${\text{mex}(A_{i},A_{j},A_{k})}$$の総和を求める問題

自分の回答

計算量削減の方法が一切思いつかなかった

公式解説

using ll = long long;

int mex(int x, int y, int z) {
    for (int i = 0; i < 3; i++) {
        if (x != i and y != i and z != i) return i;
    }
    return 3;
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    for (int &i: a) cin >> i;
    string s;
    cin >> s;
    
    vector cnt_l(n + 1, vector<int>(3));
    vector cnt_r(n + 1, vector<int>(3));
    for (int i = 0; i < n; i++) {
        cnt_l[i + 1] = cnt_l[i];
        if (s[i] == 'M') ++cnt_l[i + 1][a[i]];
    }
    for (int i = n - 1; i >= 0; i--) {
        cnt_r[i] = cnt_r[i + 1];
        if (s[i] == 'X') ++cnt_r[i][a[i]];
    }
    
    ll ans = 0;
    for (int i = 0; i < n; i++) {
        if (s[i] != 'E') continue;
        for (int j = 0; j < 3; j++) {
            for (int k = 0; k < 3; k++) {
                ans += (ll) cnt_l[i][j] * cnt_r[i + 1][k] * mex(j, a[i], k);
            }
        }
    }
    cout << ans << endl;
}

https://atcoder.jp/contests/abc308/editorial/6708より

Eが出てきた時にそこ以前のMの数×以降のXの数がそのEを使ってできるMEXの数だからM,Eを数字毎に何回出たかを記録することでmexと掛けたものを足していくのか

なるほど