D - チョコレートの再構築

この問題は比較的単純な実装問題です。チョコレートの配置を再構築するアルゴリズムを示します。

struct Chocolate {
    int height;
    int width;
    int id;
};

bool compareWidth(const Chocolate &a, const Chocolate &b) {
    return a.width > b.width;
}

bool compareHeight(const Chocolate &a, const Chocolate &b) {
    return a.height > b.height;
}

void solveChocolateProblem(int h, int w, vector<Chocolate> &pieces) {
    vector<Chocolate> sortedByWidth = pieces;
    vector<Chocolate> sortedByHeight = pieces;
    
    sort(sortedByWidth.begin(), sortedByWidth.end(), compareWidth);
    sort(sortedByHeight.begin(), sortedByHeight.end(), compareHeight);
    
    // 配置処理の実装
    // ...
}

E - 複数LCMの計算

この問題では効率的に最小公倍数を計算する方法が鍵となります。素因数分解を活用した解法を示します。

const int MAX = 1e7;
vector<int> minPrime(MAX + 1);

void sieve() {
    iota(minPrime.begin(), minPrime.end(), 0);
    for (int i = 2; i <= MAX; i++) {
        if (minPrime[i] == i) {
            for (int j = i * 2; j <= MAX; j += i) {
                if (minPrime[j] == j) {
                    minPrime[j] = i;
                }
            }
        }
    }
}

void solveLCMProblem(vector<int> &numbers) {
    sieve();
    unordered_map> maxExponents;
    
    for (int num : numbers) {
        int temp = num;
        while (temp > 1) {
            int factor = minPrime[temp];
            int count = 0;
            while (temp % factor == 0) {
                temp /= factor;
                count++;
            }
            
            if (count > maxExponents[factor].first) {
                maxExponents[factor].second = maxExponents[factor].first;
                maxExponents[factor].first = count;
            } else if (count > maxExponents[factor].second) {
                maxExponents[factor].second = count;
            }
        }
    }
    
    // LCM計算処理の実装
    // ...
}

F - Kステップ最短経路

この問題ではmin-plus行列乗算を用いた解法が有効です。グラフ理論における興味深いアプローチです。

vector minPlusMultiply(const vector &a, const vector &b) {
    int n = a.size();
    vector result(n, vector<int>(n, INT_MAX));
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            for (int k = 0; k < n; k++) {
                if (a[i][j] != INT_MAX && b[j][k] != INT_MAX) {
                    result[i][k] = min(result[i][k], a[i][j] + b[j][k]);
                }
            }
        }
    }
    
    return result;
}

void solveShortestPathProblem(vector &graph, int k) {
    vector result = graph;
    vector temp = graph;
    k--;
    
    while (k > 0) {
        if (k & 1) {
            result = minPlusMultiply(result, temp);
        }
        temp = minPlusMultiply(temp, temp);
        k >>= 1;
    }
    
    // 結果出力処理
    // ...
}