プログラミングコンテスト初級:典型問題の実装パターン

問題1:文字列の反復生成

文字 'L'、'o' を N 回繰り返した文字列、そして "ng" を連結して出力する問題です。ループを使用せず、文字列コンストラクタを活用することで簡潔に記述できます。

#include <iostream>
#include <string>

int main() {
    int repeat;
    std::cin >> repeat;
    std::string result = "L" + std::string(repeat, 'o') + "ng";
    std::cout << result << std::endl;
    return 0;
}

問題2:大文字小文字を無視した文字列判定

入力された文字列が "YES" かどうかを判定します。大文字小文字の違いを無視するため、入力文字列をすべて大文字に変換してから比較を行います。

#include <iostream>
#include <string>
#include <algorithm>

int main() {
    int cases;
    std::cin >> cases;
    while (cases--) {
        std::string input;
        std::cin >> input;
        std::string upperInput = input;
        std::transform(upperInput.begin(), upperInput.end(), upperInput.begin(), ::toupper);
        std::cout << (upperInput == "YES" ? "YES" : "NO") << std::endl;
    }
    return 0;
}

問題3:巨大な数値の奇偶判別

数値が非常に大きいため文字列として扱います。奇数か偶数かは最後の桁だけで決まるため、文字列の末尾要素を取り出して数値変換し、2で割った余りを確認します。

#include <iostream>
#include <string>

int main() {
    int totalCases;
    std::cin >> totalCases;
    while (totalCases--) {
        std::string numStr;
        std::cin >> numStr;
        char lastDigitChar = numStr.back();
        int lastDigit = lastDigitChar - '0';
        std::cout << (lastDigit % 2 ? "odd" : "even") << std::endl;
    }
    return 0;
}

問題4:頻度分布と必要数の算出

AからGの各難易度の出現回数をカウントします。各難易度において、最低限必要な数 m に満たない場合、その不足分を累計して答えとします。

#include <iostream>
#include <string>
#include <array>

int main() {
    int cases;
    std::cin >> cases;
    while (cases--) {
        int n, m;
        std::cin >> n >> m;
        std::string data;
        std::cin >> data;
        
        std::array<int, 7> counts = {0};
        for (char level : data) {
            counts[level - 'A']++;
        }
        
        int deficit = 0;
        for (int c : counts) {
            if (c < m) deficit += m - c;
        }
        std::cout << deficit << std::endl;
    }
    return 0;
}

問題5:過半数の条件判定

複数日分のデータにおいて、特定の選択肢 k を支持した住民が過半数(半数以上)を占める日数を計算します。最終的に、その日数が総日数の半数以上であれば "YES" を出力します。

#include <iostream>

int main() {
    int residents, days, targetValue;
    std::cin >> residents >> days >> targetValue;
    
    int sufficientDays = 0;
    
    for (int d = 0; d < days; ++d) {
        int matchCount = 0;
        for (int r = 0; r < residents; ++r) {
            int vote;
            std::cin >> vote;
            if (vote == targetValue) matchCount++;
        }
        if (matchCount * 2 >= residents) sufficientDays++;
    }
    
    std::cout << (sufficientDays * 2 >= days ? "YES" : "NO") << std::endl;
    return 0;
}

問題6:文字列の一括置換

文字列 S に対して、指定された文字の置換操作を T 回繰り返します。標準ライブラリの std::replace を使用することで、ループを用いて文字を走査し置換する処理を簡潔に記述できます。

#include <iostream>
#include <string>
#include <algorithm>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int length;
    std::string text;
    std::cin >> length >> text;
    
    int operations;
    std::cin >> operations;
    
    while (operations--) {
        char oldChar, newChar;
        std::cin >> oldChar >> newChar;
        if (oldChar == newChar) continue;
        std::replace(text.begin(), text.end(), oldChar, newChar);
    }
    
    std::cout << text << std::endl;
    return 0;
}

問題7:行列のインデックスマッピングによる操作

行列の行および列の入れ替え操作を多数回行う場合、実際に要素を移動させると計算コストが高くなります。代わりに、行番号と列番号の対応表(マッピング配列)を保持し、その対応表のみを更新することで、論理的な入れ替えを O(1) で処理します。

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    
    int size, queries;
    std::cin >> size >> queries;
    
    std::vector<std::vector<int>> matrix(size, std::vector<int>(size));
    for (int i = 0; i < size; ++i) {
        for (int j = 0; j < size; ++j) {
            std::cin >> matrix[i][j];
        }
    }
    
    std::vector<int> rowMap(size), colMap(size);
    for (int i = 0; i < size; ++i) rowMap[i] = colMap[i] = i;
    
    while (queries--) {
        int type, x, y;
        std::cin >> type >> x >> y;
        x--; y--; // Convert to 0-based index
        if (type == 0) std::swap(colMap[x], colMap[y]);
        else std::swap(rowMap[x], rowMap[y]);
    }
    
    for (int i = 0; i < size; ++i) {
        for (int j = 0; j < size; ++j) {
            std::cout << matrix[rowMap[i]][colMap[j]] << (j == size - 1 ? "" : " ");
        }
        std::cout << "\n";
    }
    return 0;
}

タグ: C++ Competitive Programming String Manipulation Array Matrix

7月17日 16:04 投稿