文字列の構成要素検証

与えられた3文字の文字列が"A"、"B"、"C"の3種類の文字のみで構成されているかを判定する問題。文字の順序は問わず、各文字が1回ずつ出現するかを確認する必要がある。

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

int main() {
    string input;
    cin >> input;
    
    array<int, 3> count = {0};
    for (char c : input) {
        if (c == 'A') count[0]++;
        else if (c == 'B') count[1]++;
        else if (c == 'C') count[2]++;
    }
    
    cout << (count[0] == 1 && count[1] == 1 && count[2] == 1 ? "はい" : "いいえ") << endl;
    return 0;
}

チェス盤の安全領域計算（ルーク）

8×8のチェス盤上で、ルークの移動経路が重ならないマス目の数を求める。ルークは同一行・列を占有するため、占有行と列を別々に集計し、安全領域を算出する。

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

int main() {
    set<int> occupiedRows, occupiedCols;
    
    for (int row = 0; row < 8; row++) {
        string board;
        cin >> board;
        for (int col = 0; col < 8; col++) {
            if (board[col] == '#') {
                occupiedRows.insert(row);
                occupiedCols.insert(col);
            }
        }
    }
    
    cout << (8 - occupiedRows.size()) * (8 - occupiedCols.size()) << endl;
    return 0;
}

チェス盤の安全領域計算（ナイト）

ナイトの跳び先を網羅的にマークし、安全なマス目をカウントする。跳び先の座標が盤面内かを確認しながら、既にマーク済みの位置は重複カウントしないよう配慮する。

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

const vector<int> knightDx = {2, 1, -1, -2, -2, -1, 1, 2};
const vector<int> knightDy = {1, 2, 2, 1, -1, -2, -2, -1};

int main() {
    int size, obstacles;
    cin >> size >> obstacles;
    
    vector<vector<bool>> covered(size + 1, vector<bool>(size + 1, false));
    int safeCount = size * size;
    
    for (int i = 0; i < obstacles; i++) {
        int x, y;
        cin >> x >> y;
        
        for (int dir = 0; dir < 8; dir++) {
            int nx = x + knightDx[dir];
            int ny = y + knightDy[dir];
            if (nx >= 1 && nx <= size && ny >= 1 && ny <= size && !covered[nx][ny]) {
                covered[nx][ny] = true;
                safeCount--;
            }
        }
    }
    
    cout << safeCount << endl;
    return 0;
}

区間包含の回避条件

与えられた区間集合を含まない新しい区間(l, r)の組み合わせ数を求める。固定したrに対して条件を満たす最小のlを動的計算し、累積的に解を導出する手法を採用。

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

int main() {
    int intervalCount, maxRange;
    cin >> intervalCount >> maxRange;
    
    vector<int> minStart(maxRange + 2, 1);
    for (int i = 0; i < intervalCount; i++) {
        int left, right;
        cin >> left >> right;
        minStart[right] = max(minStart[right], left + 1);
    }
    
    vector<int> validStart(maxRange + 1);
    for (int pos = 1; pos <= maxRange; pos++) {
        validStart[pos] = max(validStart[pos - 1], minStart[pos]);
    }
    
    long long result = 0;
    for (int end = 1; end <= maxRange; end++) {
        result += end - validStart[end] + 1;
    }
    
    cout << result << endl;
    return 0;
}

順列の周期的変換

与えられた順列をk回変換した結果を求める問題。順列を循環グラフと見なし、各要素の移動距離を周期性を考慮して2^k mod サイクル長で計算する。

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

long long modPow(long long base, long long exp, long long mod) {
    long long result = 1;
    while (exp > 0) {
        if (exp & 1) result = (result * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return result;
}

int main() {
    int n;
    long long k;
    cin >> n >> k;
    
    vector<int> perm(n);
    for (int i = 0; i < n; i++) {
        cin >> perm[i];
        perm[i]--;
    }
    
    vector<bool> visited(n, false);
    for (int i = 0; i < n; i++) {
        if (visited[i]) continue;
        
        vector<int> cycle;
        int current = i;
        while (!visited[current]) {
            visited[current] = true;
            cycle.push_back(current);
            current = perm[current];
        }
        
        int cycleLength = cycle.size();
        long long shift = modPow(2, k, cycleLength);
        
        for (int j = 0; j < cycleLength; j++) {
            perm[cycle[j]] = cycle[(j + shift) % cycleLength];
        }
    }
    
    for (int i = 0; i < n; i++) {
        cout << perm[i] + 1 << (i == n - 1 ? "\n" : " ");
    }
    return 0;
}