配列内要素の隣接関係判定

与えられた配列において、特定の2つの要素xとyが隣接しているかどうかを判定する問題です。

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

bool checkAdjacent(vector<int>& arr, int target1, int target2) {
    int n = arr.size();
    for(int i = 0; i < n; i++) {
        if(arr[i] == target1) {
            if((i > 0 && arr[i-1] == target2) || 
               (i < n-1 && arr[i+1] == target2)) {
                return true;
            }
        }
    }
    return false;
}

int main() {
    int n;
    cin >> n;
    vector<int> sequence(n);
    for(int i = 0; i < n; i++) {
        cin >> sequence[i];
    }
    
    int elem1, elem2;
    cin >> elem1 >> elem2;
    
    if(checkAdjacent(sequence, elem1, elem2)) {
        cout << "Yes" << endl;
    } else {
        cout << "No" << endl;
    }
    
    return 0;
}

環状経路上の最短距離計算

環状に配置された駅間の最短移動距離を計算する問題です。前方向と後方向の両方を考慮します。

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

long long calculateMinDistance(vector<int>& distances, int start, int end) {
    int n = distances.size();
    start--; end--;
    if(start > end) swap(start, end);
    
    vector<long long> prefixSum(2*n);
    for(int i = 1; i < 2*n; i++) {
        prefixSum[i] = prefixSum[i-1] + distances[(i-1) % n];
    }
    
    long long forwardDist = prefixSum[end] - prefixSum[start];
    long long backwardDist = prefixSum[start + n] - prefixSum[end];
    
    return min(forwardDist, backwardDist);
}

int main() {
    int stationCount;
    cin >> stationCount;
    vector<int> stationDists(stationCount);
    for(int i = 0; i < stationCount; i++) {
        cin >> stationDists[i];
    }
    
    int from, to;
    cin >> from >> to;
    
    cout << calculateMinDistance(stationDists, from, to) << endl;
    
    return 0;
}

最小化合計値を持つ配列構築

隣接要素の積の合計を最小化するような配列を構築します。

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

vector<int> constructOptimalSequence(int n) {
    vector<int> result;
    int left = 1;
    int right = n;
    
    while(left <= right) {
        result.push_back(left);
        if(left != right) {
            result.push_back(right);
        }
        left++;
        right--;
    }
    return result;
}

int main() {
    int num;
    cin >> num;
    vector<int> optimalSeq = constructOptimalSequence(num);
    
    for(int i = 0; i < optimalSeq.size(); i++) {
        cout << optimalSeq[i];
        if(i != optimalSeq.size()-1) cout << " ";
    }
    cout << endl;
    
    return 0;
}

木構造上の条件付き色付け問題

木構造において、特定の条件を満たすノードのペアに色を付ける問題です。

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

int colorTreeNodes(vector<int>& values, vector<vector<int>>& tree) {
    int n = values.size();
    vector<bool> colored(n, false);
    int coloredCount = 0;
    
    function<void(int, int)> traverse = [&](int current, int parent) {
        for(int neighbor : tree[current]) {
            if(neighbor == parent) continue;
            traverse(neighbor, current);
            
            if(!colored[neighbor] && !colored[current]) {
                long long product = (long long)values[neighbor] * values[current];
                long long root = sqrt(product);
                if(root * root == product) {
                    colored[neighbor] = colored[current] = true;
                    coloredCount += 2;
                }
            }
        }
    };
    
    traverse(0, -1);
    return coloredCount;
}

int main() {
    int nodeCount;
    cin >> nodeCount;
    vector<int> nodeValues(nodeCount);
    for(int i = 0; i < nodeCount; i++) {
        cin >> nodeValues[i];
    }
    
    vector<vector<int>> adjacencyList(nodeCount);
    for(int i = 0; i < nodeCount-1; i++) {
        int u, v;
        cin >> u >> v;
        u--; v--;
        adjacencyList[u].push_back(v);
        adjacencyList[v].push_back(u);
    }
    
    cout << colorTreeNodes(nodeValues, adjacencyList) << endl;
    
    return 0;
}