文字列包含範囲の抽出

与えられた文字列から、特定の部分文字列を全て含む最小の連続部分を抽出するアルゴリズム。左から右へ探索して部分文字列の最後の文字位置を特定し、次に右から左へ探索して部分文字列の最初の文字位置を特定することで最小範囲を決定する。

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

void extractMinimalSubstring() {
    string source, target;
    cin >> source >> target;
    
    int left = 0, right = source.length() - 1;
    int current = 0;
    
    for(int i = 0; i < source.length(); i++) {
        if(source[i] == target[current]) {
            current++;
        }
        if(current == target.length()) {
            right = i;
            break;
        }
    }
    
    current = target.length() - 1;
    for(int i = right; i >= 0; i--) {
        if(source[i] == target[current]) {
            current--;
        }
        if(current < 0) {
            left = i;
            break;
        }
    }
    
    cout << source.substr(left, right - left + 1) << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int testCases;
    cin >> testCases;
    while(testCases--) {
        extractMinimalSubstring();
    }
    return 0;
}

ダメージ計算の検証

ゲームにおけるダメージ計算の妥当性チェック。攻撃回数と時間制限に基づいて、目標ダメージが達成可能かどうかを判定する。

#include <iostream>
using namespace std;

void validateDamage() {
    int baseDamage, attackRate, targetDamage, timeLimit;
    cin >> baseDamage >> attackRate >> targetDamage >> timeLimit;
    
    if(baseDamage == 0 || attackRate == 0) {
        if(targetDamage > 0) {
            cout << "fail!" << endl;
        } else {
            cout << "success" << endl;
        }
        return;
    }
    
    int requiredHits = (targetDamage + baseDamage - 1) / baseDamage;
    int possibleHits = attackRate * timeLimit / 60 + 1;
    
    if(requiredHits <= possibleHits) {
        cout << "success" << endl;
    } else {
        cout << "fail!" << endl;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int testCases;
    cin >> testCases;
    while(testCases--) {
        validateDamage();
    }
    return 0;
}

塗りつぶし操作の最小回数計算

環状配列の塗りつぶしに必要な最小操作回数を求めるアルゴリズム。同じ色の連続区間を検出し、各区間の長さと操作単位に基づいて必要回数を計算する。

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

void calculatePaintingOperations() {
    int length, colors, operationSize;
    cin >> length >> colors >> operationSize;
    
    vector<int> sequence(length);
    vector<int> segments;
    
    for(int i = 0; i < length; i++) {
        cin >> sequence[i];
    }
    
    int segmentCount = 0;
    for(int i = 0; i < length; i++) {
        if(i == 0 || sequence[i] != sequence[i - 1]) {
            segments.push_back(1);
            segmentCount++;
        } else {
            segments[segmentCount - 1]++;
        }
    }
    
    if(sequence[0] == sequence[length - 1] && segmentCount > 1) {
        segments[0] += segments[segmentCount - 1];
        segmentCount--;
    }
    
    bool valid = false;
    int totalOperations = 0;
    
    for(int i = 0; i < segmentCount; i++) {
        if(segments[i] >= operationSize) {
            valid = true;
        }
        totalOperations += (segments[i] + operationSize - 1) / operationSize;
    }
    
    cout << (valid ? totalOperations : -1) << endl;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int testCases;
    cin >> testCases;
    while(testCases--) {
        calculatePaintingOperations();
    }
    return 0;
}

文字列比較

二つの文字列を辞書順で比較し、大小関係を出力する基本的な操作。

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

void compareStrings() {
    string first, second;
    cin >> first >> second;
    
    if(first > second) {
        cout << first << ">" << second << endl;
    } else if(first < second) {
        cout << first << "<" << second << endl;
    } else {
        cout << first << "=" << second << endl;
    }
}