A: 閾値以下の合計

数値リストから指定された閾値以下の要素の合計を算出します。

#include <iostream>
#include <vector>
using namespace std;

int main() {
  int num, threshold;
  cin >> num >> threshold;
  vector<int> values(num);
  
  int total = 0;
  for (int &val : values) {
    cin >> val;
    if (val <= threshold) total += val;
  }
  
  cout << total << endl;
  return 0;
}

B: ゾロ目の日数

月と日が同じ数字で構成される日（例：11/11）の総数を計算します。

#include <iostream>
#include <vector>
using namespace std;

int main() {
  int months;
  cin >> months;
  vector<int> days(months + 1);
  
  int count = 0;
  for (int i = 1; i <= months; i++) {
    cin >> days[i];
    int base = i % 10;
    
    if (i < 10) {
      int current = base;
      while (current <= days[i]) {
        count++;
        current = current * 10 + base;
      }
    } else if (i % 11 == 0) {
      int current = base;
      while (current <= days[i]) {
        count++;
        current = current * 10 + base;
      }
    }
  }
  
  cout << count << endl;
  return 0;
}

C: 連続文字のカウント

隣接する同一文字の出現回数を前処理し、累積和を用いてクエリに回答します。

#include <iostream>
#include <vector>
using namespace std;

int main() {
  int len, queryCount;
  string str;
  cin >> len >> queryCount >> str;
  
  vector<int> prefix(len + 1, 0);
  for (int i = 1; i < len; i++) {
    prefix[i+1] = prefix[i] + (str[i] == str[i-1] ? 1 : 0);
  }
  
  while (queryCount--) {
    int left, right;
    cin >> left >> right;
    cout << prefix[right] - prefix[left] << '\n';
  }
  
  return 0;
}

D: ABC削除処理

スタックを用いて文字列から連続する"ABC"を効率的に削除します。

#include <iostream>
#include <stack>
#include <string>
using namespace std;

int main() {
  string input;
  cin >> input;
  stack<char> charStack;
  
  for (char c : input) {
    charStack.push(c);
    if (charStack.size() >= 3) {
      char c3 = charStack.top(); charStack.pop();
      char c2 = charStack.top(); charStack.pop();
      char c1 = charStack.top(); charStack.pop();
      
      if (c1 != 'A' || c2 != 'B' || c3 != 'C') {
        charStack.push(c1);
        charStack.push(c2);
        charStack.push(c3);
      }
    }
  }
  
  string result;
  while (!charStack.empty()) {
    result = charStack.top() + result;
    charStack.pop();
  }
  
  cout << result << endl;
  return 0;
}

E: モジュロ最小全域木

辺の組み合わせを全探索し、Union-Findで木を判定しながらモジュロ最小コストを求めます。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct Edge {
  int from, to, weight;
};

struct UnionFind {
  vector<int> parent;
  UnionFind(int size) {
    parent.resize(size);
    for (int i = 0; i < size; i++) parent[i] = i;
  }
  
  int find(int x) {
    return (x == parent[x]) ? x : (parent[x] = find(parent[x]));
  }
  
  bool unite(int x, int y) {
    x = find(x);
    y = find(y);
    if (x == y) return false;
    parent[y] = x;
    return true;
  }
};

int main() {
  int nodes, edges, mod;
  cin >> nodes >> edges >> mod;
  
  vector<Edge> edgeList(edges);
  for (int i = 0; i < edges; i++) {
    cin >> edgeList[i].from >> edgeList[i].to >> edgeList[i].weight;
    edgeList[i].weight %= mod;
  }
  
  vector<int> selection(edges, 0);
  fill(selection.end() - (nodes - 1), selection.end(), 1);
  
  int minCost = mod;
  do {
    UnionFind uf(nodes);
    int sum = 0, count = 0;
    
    for (int i = 0; i < edges; i++) {
      if (selection[i]) {
        if (!uf.unite(edgeList[i].from - 1, edgeList[i].to - 1)) break;
        sum = (sum + edgeList[i].weight) % mod;
        count++;
      }
    }
    
    if (count == nodes - 1) 
      minCost = min(minCost, sum);
      
  } while (next_permutation(selection.begin(), selection.end()));
  
  cout << minCost << endl;
  return 0;
}