AtCoder Beginner Contest 328

2023年11月13日 15:14

結果

A - Not Too Hard : AC(1:29)
B - 11/11 : AC(6:58)
C - Consecutive : AC(11:43)
D - Take ABC : AC(25:45)
E - Modulo MST : 提出無し

A - Not Too Hard

$${N}$$問の問題が出題されるプログラミングコンテストがあり、各問の配点は$${S_{i}}$$である
配点が$${X}$$以下の点数である問題全ての配点の合計を求める問題

自分の回答

int main(){
  int N, X;
  cin >> N >> X;

  int ans = 0;
  for(int i = 0; i < N; i++){
    int s;
    cin >> s;
    if(s <= X){
      ans += s;
    }
  }

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

そのまま

公式解説

省略

B - 11/11

ある国では$${1}$$年が$${N}$$ヶ月である暦を使っていて各月は$${D_{i}}$$日である
その国において日付がゾロ目となる日が何日あるか求める問題

自分の回答

int main(){
  int N;
  cin >> N;

  int ans = 0;
  for(int i = 1; i <= N; i++){
    int d;
    cin >> d;
    if(i > 9 && i % 11 != 0){
      continue;
    }
    int n = i % 10;
    if(d >= n){
      ans++;
    }
    if(d >= 10 * n + n){
      ans++;
    }
  }

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

月、日共に100までのため、まず月が一桁もしくは11の倍数であるかでその月ゾロ目が発生するかを判定
月がゾロ目ならmod10でその数が何かを取って日がそれを超えるかとその数字×11の日付を超えるかカウント

公式解説

省略

C - Consecutive

英小文字のみからなる長さ$${N}$$の文字列$${S}$$が与えられる
$${S}$$の$${l}$$文字目から$${r}$$文字目までの部分文字列で同じ文字が隣接する箇所が何個あるか求める質問が$${Q}$$個与えられるためそれらすべてに答える問題

自分の回答

int main(){
  int N, Q;
  string S;
  cin >> N >> Q >> S;

  vector<int> sum(N, 0);
  for(int i = 1; i < N; i++){
    sum[i] = sum[i - 1];
    if(S[i] == S[i - 1]){
      sum[i]++;
    }
  }

  for(int i = 0; i < Q; i++){
    int l, r;
    cin >> l >> r;
    l--;
    r--;
    printf("%d\n", sum[r] - sum[l]);
  }
}

頭からi文字目までで何回あるかの累積和

公式解説

省略

D - Take ABC

「A」「B」「C」からなる文字列$${S}$$が与えられ、$${S}$$のうち最も左にある「ABC」を消していく操作を繰り返していった結果の文字列を求める問題

自分の回答

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

  stack<char> st;
  char mid = 'e';
  for(char c : S){
    if(mid == 'e'){
      mid = c;
      continue;
    }
    if(st.empty()){
      st.push(mid);
      mid = c;
      continue;
    }
    if(st.top() == 'A' && mid == 'B' && c == 'C'){
      st.pop();
      if(st.empty()){
        mid = 'e';
        continue;
      }
      mid = st.top();
      st.pop();
    }
    else{
      st.push(mid);
      mid = c;
    }
  }
  if(mid != 'e'){
    st.push(mid);
  }

  string ans;
  while(!st.empty()){
    ans += st.top();
    st.pop();
  }
  reverse(ans.begin(), ans.end());
  printf("%s\n", ans.c_str());
}

頭から見て行ってstackに積んでABCが出たらそれを消すのを繰り返す
もっときれいにできるはず

公式解説

int main(void)
{
  string s, ans;
  cin >> s;
  
  for(auto c : s){
    ans += c;
    if(ans.size() >= 3 && ans.substr(ans.size()-3) == "ABC") ans.erase(ans.end()-3, ans.end());
  }
  cout << ans << endl;
  
  return 0;
}

https://atcoder.jp/contests/abc328/editorial/7655より

そうかstackを使わなくてもstringに入れてって後ろ3文字がABCならそれを消すでいいのか

なるほど

E - Modulo MST

$${N}$$頂点$${M}$$辺の重み付き単純連結無向グラフと正整数$${K}$$が与えられる
辺はそれぞれ頂点$${u_{i}}$$と$${v_{i}}$$を結んでいて、重みは$${w_{i}}$$である
このグラフの全域木$${T}$$において、そのコストは$${T}$$に含まれる辺の重みの総和を$${K}$$で割った余りとする
このグラフの全域木におけるコストの最小値を求める問題

自分の回答

調べたら最小の全域木はクラスカル法ってので求められるのはわかったけど今回においては総和の余りだからそれだとダメ
頂点と辺の数の上限からして全域木を総当たりしそうな感じはするけどそれをどうしたらできるか思いつかなかった

公式解説

int main() {
    using namespace std;
    unsigned N, M;
    unsigned long K;
    cin >> N >> M >> K;
    vector<tuple<unsigned, unsigned, unsigned long>> edges(M);
    for (auto&&[u, v, cost] : edges){
        cin >> u >> v >> cost;
        --u;
        --v;
    }
    basic_string<bool> use_edges(M, false); // M 本の辺のうち
    ranges::fill(use_edges | views::take(N - 1), true); // N - 1 本を使う
    ranges::reverse(use_edges);
    // 全域木になっているか判定するために Union-Find を使う
    vector<unsigned> uf(N), sz(N, 1);
    const auto find{[&uf](auto i) {
        while (i != uf[i])i = uf[i] = uf[uf[i]];
        return i;
    }};
    const auto unite{[&uf, &sz, find](auto i, auto j) -> bool {
        i = find(i);
        j = find(j);
        if (i == j)return false;
        if (sz[i] < sz[j])swap(i, j);
        sz[i] += sz[j];
        uf[j] = i;
        return true;
    }};
    unsigned long ans{K};
    const auto chmin{[](auto &&x, const auto &y) {
        if (x > y)x = y;
        return x;
    }};
    do
        chmin(ans, [&] {
            // Union-Find の初期化
            iota(begin(uf), end(uf), 0U);
            ranges::fill(sz, 1U);
            unsigned long cost_sum{};
            for (const auto i : views::iota(0U, M))
                if (use_edges[i]) {
                    const auto&[u, v, cost]{edges[i]};
                    if (!unite(u, v)) // 閉路ができたら
                        return K; // 十分大きい値を返す
                    cost_sum += cost;
                }
            // 全域木なら
            return cost_sum % K; // コストを返す
        }());
    while (ranges::next_permutation(use_edges).found);
    cout << ans << endl;
    return 0;
}

https://atcoder.jp/contests/abc328/editorial/7645より

辺をN-1個の組み合わせの総当たりはギリギリダメだと思ったけどできるのか
それで後はその辺で探索してか
とりあえず書くだけはしてみるものだね…
あとUnion-Findも自分で書くのはやっといてみないといけないな

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