AtCoder Beginner Contest 353

2024年5月13日 15:38

結果

A - Buildings : AC(1:57)
B - AtCoder Amusement Park : AC(6:32)
C - Sigma Problem : AC(6:32)
D - Another Sigma Problem : AC(81:41)(5ペナ)

A - Buildings

$${N}$$個のビルが並んでいて高さはそれぞれ$${H_{i}}$$である
$${1}$$番目のビルより高いビルのうち最も番号が小さいビルを求める問題

自分の回答

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

  for(int i = 1; i < N; i++){
    if(H[0] < H[i]){
      printf("%d\n", i + 1);
      return 0;
    }
  }
  printf("-1\n");
}

そのまま

公式解説

省略

B - AtCoder Amusement Park

遊園地に$${K}$$人乗りのアトラクションがある
このアトラクションには$${N}$$グループが並んでいてそれぞれ$${A_{i}}$$人である
先頭のグループから順番にアトラクションに乗せていき、次のグループを乗せると人数超過する場合アトラクションを出発させる
最終的に何回アトラクションを出発させるか求める問題

自分の回答

int main() {
  int N, K;
  cin >> N >> K;
  queue<int> A;
  for(int i = 0; i < N; i++){
    int a;
    cin >> a;
    A.push(a);
  }

  int ans = 1, now = 0;
  while(!A.empty()){
    if(now + A.front() > K){
      now = 0;
      ans++;
    }
    now += A.front();
    A.pop();
  }

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

そのまま

公式解説

省略

C - Sigma Problem

長さ$${N}$$の整数列$${A=(A_{1},A_{2},…,A_{N})}$$がある
この数列から$${2}$$つの値$${(x,y)}$$を選び$${x+y}$$を$${10^8}$$で割った余りを$${z}$$とする
$${A}$$の全ての組み合わせにおける$${z}$$の総和を求める問題

自分の回答

int main() {
  int N;
  cin >> N;
  vector<int64_t> A(N);
  int64_t sum = 0;
  for(int i = 0; i < N; i++){
    cin >> A[i];
    sum += A[i];
  }

  sort(A.begin(), A.end());
  int64_t ans = 0;
  int j = N - 1;
  for(int i = 0; i < N - 1; i++){
    int64_t up = 100000000 - A[i];
    sum -= A[i];
    while(j >= 0 && A[j] >= up){
      j--;
    }
    int64_t ind = min(N - j - 1, N - i - 1);
    ans += A[i] * (N - i - 1) + sum - 100000000 * ind;
  }

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

制約から10^8で割った数が2以上となることは無いため昇順にソートして先頭から値を見ていき、その値と足したら10^8を超える値がどこにあるかを調べる
そうすれば
今見ている値*自分より先にある値の個数+自分より先にある値の総和-和が10^8を超える数*10^8
が今見ている値におけるzの総和になるためそれを全ての値で行う
これならその部分の計算量はNで終わるため問題ない

公式解説

省略

D - Another Sigma Problem

長さ$${N}$$の整数列$${A=(A_{1},A_{2},…,A_{N})}$$がある
この数列から$${2}$$つの値$${(A_{i},A_{i+j})}$$を選びこれをその順番のまま文字列として結合した値を$${z}$$とする
$${A}$$の全ての組み合わせにおける$${z}$$の総和を$${998244353}$$で割った余りを求める問題

自分の回答

#include <atcoder/all>
using namespace atcoder;

int main() {
  int64_t mod = 998244353;
  int N;
  cin >> N;
  vector<int64_t> A(N), digcou(10, 0);
  map<int64_t, int64_t> mapA;
  for(int i = 0; i < N; i++){
    int64_t a;
    cin >> a;
    A[i] = a;
    mapA[log10(a) + 1] += a;
    digcou[log10(a) + 1]++;
  }

  modint998244353 ans = 0;
  for(int i = 0; i < N - 1; i++){
    mapA[log10(A[i]) + 1] -= A[i];
    digcou[log10(A[i]) + 1]--;
    for(auto [d, sum] : mapA){
      int64_t dig = 1, dc = digcou[d];
      for(int _ = 0; _ < d; _++){
        dig *= 10;
      }
      modint998244353 s = A[i];
      s *= dig;
      s *= dc;
      s += sum;
      ans += s;
    }
  }

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

C問題におけるyとその総和を桁数ごとにまとめてやる感じ
間違いなくもっといい方法はあると思う

ansとsの部分をint64_tでやっていてオーバーフローでWA
色々試したけどうまく回避できずACLのmodintを使ったら行けた

公式解説

#include <bits/stdc++.h>
#include "atcoder/modint"

using namespace std;
using ll = long long;
using mint = atcoder::modint998244353;

int main() {
  int n;
  cin >> n;
  vector<int> a(n);
  for(auto &v : a) cin >> v;
  vector<int> d(11);
  for(int i = 0; i < n; i++) {
    d[to_string(a[i]).size()]++;
  }
  mint res = 0;
  vector<mint> p10(11, 1);
  for(int i = 1; i <= 10; i++) p10[i] = p10[i - 1] * 10;
  for(int i = 0; i < n; i++) {
    res += mint(a[i]) * i;
    d[to_string(a[i]).size()]--;
    for(int j = 1; j <= 10; j++) {
      res += p10[j] * a[i] * d[j];
    }
  }
  cout << res.val() << endl;
}

https://atcoder.jp/contests/abc353/editorial/9958より

色々と違う所はあるけど根本的な考え方はだいぶ近い？

E - Yet Another Sigma Problem

英小文字からなる$${N}$$個の文字列$${(S_{1},S_{2},…,S_{N})}$$がある
そこから$${2}$$つ選んだ全ての組み合わせにおける最長共通接頭辞の長さの総和を求める問題

自分の回答

とりあえずソートするところが始まりなのはわかるがその先が一切わからん
近い物どうしでどれだけ近いかを見ていくいい方法あるのかな…

公式解説

#include <bits/stdc++.h>
using namespace std;

struct trie {
  using ar = array<int, 26>;
  vector<ar> pos;
  ar def;
  int now_sz;
  long long ans;
  vector<int> cnt;
  trie() = default;
  trie(int len) {
    pos.reserve(len + 1);
    cnt.reserve(len + 1);
    def.fill(-1);
    now_sz = ans = 0;
    make_node();
  }
  int make_node() {
    pos.push_back(def);
    cnt.push_back(0);
    return now_sz++;
  }
  void add(string &s) {
    int now = 0;
    for(int i = 0; i < (int)s.size(); i++) {
      int d = s[i] - 'a';
      int &nx = pos[now][d];
      if(nx == -1)
        nx = make_node();
      now = nx;
      ans += cnt[now]++;
    }
  }
};

int main() {
  int n;
  cin >> n;
  trie tr(300000);
  for(int i = 0; i < n; i++) {
    string s;
    cin >> s;
    tr.add(s);
  }
  cout << tr.ans << endl;
}

https://atcoder.jp/contests/abc353/editorial/9969より

深さがi文字目、分岐がS[i]の文字な探索木(trie木)を作って文字列を入れていきその時に各分岐に作成時を除いて今まで何回通ったかの総和？

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