コードのマクロ定義とフレームワークの約束

#include <bits/stdc++.h>
using namespace std;
#define FASTIO ios::sync_with_stdio(false); cin.tie(nullptr);
#define ENDL '\n'
#define RANGE(_x, _y) (_x).begin(), (_x).end()
#define LOOP(_i, _s, _e) for (int _i = _s; _i < _e; ++_i)
typedef long long ll;
const int MAXN = 200010;

signed main() {
    FASTIO;
    int test_cases = 1;
    // cin >> test_cases;
    while (test_cases--) solve();
    return 0;
}

アナグラム検索

問題の概要

文字列 \(S\) と \(T\) が似ているとは、\(S\) を並べ替えることで \(T\) にできる場合を指す。与えられた文字列 \(A\) と \(B\) について、\(A\) のどの部分文字列（連続した部分）が \(B\) に似ているかを求めよ。

また、\(A\) には任意の文字に置き換えられる ? 文字が含まれる。

解法の考え

この問題では、スライディングウィンドウを使用する。文字列 \(A\) の中で、長さが \(len(B)\) のウィンドウを維持し、その中の各文字の出現数をカウントして \(B\) と比較する。

void solve() {
    string S, T;
    cin >> S >> T;
    vector<int> countB(26), windowCount(26);
    int result = 0;
    for (char c : T) countB[c - 'a']++;
    for (int i = 0; i < S.size(); ++i) {
        if (S[i] != '?') windowCount[S[i] - 'a']++;
        if (i >= T.size() && S[i - T.size()] != '?') windowCount[S[i - T.size()] - 'a']--;
        if (i >= T.size() - 1) {
            bool match = true;
            for (int j = 0; j < 26; ++j) {
                if (windowCount[j] > countB[j]) {
                    match = false;
                    break;
                }
            }
            result += match;
        }
    }
    cout << result << ENDL;
}

区間内の最大差

問題の概要

長さ \(n\) のシーケンスから、要素間の差が最大でも \(k\) である最長の部分シーケンスを見つける。

解法の考察

この問題は二分探索とセグメントツリーを用いる。まず、元のシーケンスに対してセグメントツリーを構築し、区間内の最大値と最小値を管理する。次に、各起点から開始し、二分探索を用いて最適な終点を見つけ、条件を満たすかどうかを確認する。

struct SegmentTreeNode {
    int left, right, maxVal, minVal;
} segTree[MAXN * 4];

void update(int node) {
    segTree[node].maxVal = max(segTree[node * 2].maxVal, segTree[node * 2 + 1].maxVal);
    segTree[node].minVal = min(segTree[node * 2].minVal, segTree[node * 2 + 1].minVal);
}

void buildSegTree(int node, int l, int r, const vector<int>& arr) {
    segTree[node] = {l, r, arr[r], arr[r]};
    if (l == r) return;
    int mid = (l + r) / 2;
    buildSegTree(node * 2, l, mid, arr);
    buildSegTree(node * 2 + 1, mid + 1, r, arr);
    update(node);
}

SegmentTreeNode querySegTree(int node, int l, int r) {
    if (segTree[node].left >= l && segTree[node].right <= r) return segTree[node];
    int mid = (segTree[node].left + segTree[node].right) / 2;
    if (r <= mid) return querySegTree(node * 2, l, r);
    else if (l > mid) return querySegTree(node * 2 + 1, l, r);
    else {
        auto L = querySegTree(node * 2, l, r);
        auto R = querySegTree(node * 2 + 1, l, r);
        SegmentTreeNode res = {l, r, max(L.maxVal, R.maxVal), min(L.minVal, R.minVal)};
        return res;
    }
}

車内での音楽再生

問題の概要

2つの長さ \(n\) のシーケンス \(A_i\) と \(B_i\) が与えられ、それぞれ要素の貢献度とコストを表す。\(w\) 回の操作を行い、総コスト \(K\) 以下で最大の貢献度を得る。

解法の考察

この問題では、貪欲法とデータ構造を組み合わせて解決する。双方向ポインタと平衡木（multiset）を用いて、操作後のコストを効率的に管理する。

void solve() {
    int n, w, k;
    cin >> n >> w >> k;
    vector<int> a(n + 1), b(n + 1);
    LOOP(i, 1, n + 1) cin >> a[i];
    LOOP(i, 1, n + 1) cin >> b[i];
    int l = 1, totalCost = 0, totalContribution = 0, bestAns = 0;
    multiset<int> originalSet, discountedSet;
    LOOP(i, 1, n + 1) {
        discountedSet.insert(b[i]);
        totalCost += (b[i] + 1) / 2;
        totalContribution += a[i];
        if (discountedSet.size() > w) {
            originalSet.insert(*discountedSet.begin());
            totalCost += *discountedSet.begin();
            totalCost -= (*discountedSet.begin() + 1) / 2;
            discountedSet.erase(discountedSet.begin());
        }
        while (totalCost > k) {
            if (b[l] >= *discountedSet.begin()) {
                totalCost -= (b[l] + 1) / 2;
                discountedSet.erase(discountedSet.find(b[l]));
                if (!originalSet.empty()) {
                    discountedSet.insert(*originalSet.rbegin());
                    totalCost -= *originalSet.rbegin();
                    totalCost += (*originalSet.rbegin() + 1) / 2;
                    originalSet.erase(originalSet.find(*originalSet.rbegin()));
                }
            } else {
                totalCost -= b[l];
                originalSet.erase(originalSet.find(b[l]));
            }
            totalContribution -= a[l];
            l++;
        }
        bestAns = max(bestAns, totalContribution);
    }
    cout << bestAns << ENDL;
}

旅行カードの選択

問題の概要

バスに乗るために以下のチケットが提供されている：

• 単程券：20円
• 90分以内自由乗車券：50円
• 1440分以内自由乗車券：120円

\(n\) 回のバス利用計画において、最小の金額を求める。

解法の考察

これは典型的な動的計画法問題であり、各利用回数における最小コストを計算する。

void solve() {
    int n;
    cin >> n;
    vector<int> times(n + 1), dp(n + 1);
    LOOP(i, 1, n + 1) cin >> times[i];
    LOOP(i, 1, n + 1) {
        dp[i] = dp[i - 1] + 20;
        int idx = lower_bound(RANGE(times, 1, i + 1), times[i] - 89) - times.begin() - 1;
        if (idx >= 1) dp[i] = min(dp[i], dp[idx] + 50);
        idx = lower_bound(RANGE(times, 1, i + 1), times[i] - 1439) - times.begin() - 1;
        if (idx >= 1) dp[i] = min(dp[i], dp[idx] + 120);
    }
    LOOP(i, 1, n + 1) cout << dp[i] - dp[i - 1] << ENDL;
}