A - Full Moon (満月)

この問題は、N日目までの期間において、最初の満月がM日目に見え、その後P日ごとに満月が見える場合に、合計何回満月が見えるかを数えるものです。つまり、M, M+P, M+2P, ...という等差数列の項がN以下になるものがいくつあるかを求めます。

• まず、N日目がM日目よりも前であれば、満月は一度も見えません。この場合、回数は0です。
• N日目がM日目以降であれば、M日目に満月が1回見えるのは確実です。
• その後の追加の満月の回数は、M日目からN日目までの期間(N - M)日間に、P日ごとに何回満月が訪れるかを計算することで求められます。これは(N - M) / Pで得られます。

これらを合計することで、N日目までの満月の総回数が算出されます。

#include <iostream>
#include <algorithm> // std::max のために必要

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int N_total_days;     // N: 全体の期間（日数）
    int M_first_moon_day; // M: 最初の満月の日
    int P_interval_days;  // P: 満月が訪れる間隔（日数）

    std::cin >> N_total_days >> M_first_moon_day >> P_interval_days;

    long long count_full_moons = 0;

    // N日目が最初の満月の日M_first_moon_dayよりも後、または同日の場合に計算
    if (N_total_days >= M_first_moon_day) {
        // M_first_moon_day の満月を1回としてカウント
        count_full_moons = 1;
        // M_first_moon_day 以降、N_total_days までの残りの期間で、
        // P_interval_days ごとに何回満月があるかを追加でカウント
        count_full_moons += (N_total_days - M_first_moon_day) / P_interval_days;
    }

    std::cout << count_full_moons << '\n';

    return 0;
}

B - Overlapping sheets (重なるシート)

複数の長方形のシートが与えられ、それらが覆う領域の合計面積を求める問題です。各シートはx座標AからB-1まで、y座標CからD-1までの範囲をカバーします。座標の最大値が100と非常に小さいため、グリッドを直接シミュレーションする手法が適用可能です。

• 100x100（実際には座標が0から99までなので、配列サイズを101x101としてインデックス100までカバーできるようにします）の2次元論理グリッドを用意します。各セルが少なくとも1つのシートで覆われているかを記録するため、bool型の配列が適しています。
• 与えられた各シートについて、そのシートが覆う全てのセル（x_minからx_max-1、y_minからy_max-1）を「覆われている」とマークします。
• 全てのシートの処理が終わった後、グリッド内の「覆われている」とマークされたセルの総数を数えれば、それが求める合計面積となります。

#include <iostream>
#include <vector>

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int num_rectangles; // N: 長方形のシートの数
    std::cin >> num_rectangles;

    // 100x100のグリッドを用意 (座標0-99をカバーするためサイズ101)
    std::vector<std::vector<bool>> covered_cells(101, std::vector<bool>(101, false));

    for (int i = 0; i < num_rectangles; ++i) {
        int x_min, x_max, y_min, y_max; // 入力 A B C D を x_min, x_max, y_min, y_max に対応
        std::cin >> x_min >> x_max >> y_min >> y_max;

        // 指定された長方形の範囲内のセルをマーク
        // x座標は x_min から x_max-1 まで、y座標は y_min から y_max-1 まで
        for (int x_coord = x_min; x_coord < x_max; ++x_coord) {
            for (int y_coord = y_min; y_coord < y_max; ++y_coord) {
                covered_cells[x_coord][y_coord] = true;
            }
        }
    }

    long long total_covered_area = 0; // 総面積

    // グリッド内の覆われたセルの数を数える
    for (int x_coord = 0; x_coord < 100; ++x_coord) {
        for (int y_coord = 0; y_coord < 100; ++y_coord) {
            if (covered_cells[x_coord][y_coord]) {
                total_covered_area++;
            }
        }
    }

    std::cout << total_covered_area << '\n';

    return 0;
}

C - Blue Spring (青い春)

N日間の旅行における最小費用を求める問題です。各日の費用F_iが与えられ、P円を支払うことでD日間の費用を無料にできるパスを何回でも購入できます。無料にするD日間は任意に選べます。

この問題は「貪欲法（Greedy Algorithm）」で解くことができます。

• パスの効果を最大化するためには、常に最も費用が高い日を優先的に無料にするのが最適です。なぜなら、パスは任意のD日間の費用を無料にできるため、その効果を最大限に利用するには、費用が最も高い日を選んだ方が総費用を大きく削減できるからです。
• したがって、まず各日の費用を降順（高い順）にソートします。
• ソート後、費用が高い順にD日間の塊を処理していきます。各D日間の費用合計とパスの購入費用Pを比較し、小さい方を総費用に加算します。これを全ての日にちについて行います。

この戦略により、常に最適な選択を行い、全体の総費用を最小化することができます。

#include <iostream>
#include <vector>
#include <algorithm> // std::sort, std::min のために必要

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    long long num_days;          // N: 旅行の日数
    long long free_days_per_pass; // D: パスで無料にできる日数
    long long pass_purchase_cost; // P: パスの購入費用

    std::cin >> num_days >> free_days_per_pass >> pass_purchase_cost;

    std::vector<long long> daily_expenses(num_days); // 各日の費用
    for (int i = 0; i < num_days; ++i) {
        std::cin >> daily_expenses[i];
    }

    // 費用を降順にソート（最も高価な日を優先的に処理するため）
    std::sort(daily_expenses.rbegin(), daily_expenses.rend());

    long long total_minimum_cost = 0;
    long long current_day_idx = 0;

    // ソートされた費用リストを D 日間ごとに区切って処理
    while (current_day_idx < num_days) {
        long long sum_current_block_expenses = 0;
        // 現在のブロックの D 日間（または残り全ての日数）の費用を合計
        for (int i = 0; i < free_days_per_pass; ++i) {
            if (current_day_idx + i < num_days) {
                sum_current_block_expenses += daily_expenses[current_day_idx + i];
            } else {
                break; // N 日を超えたらループを終了
            }
        }

        // D日間の費用合計とパス購入費用を比較し、小さい方を総費用に加算
        total_minimum_cost += std::min(pass_purchase_cost, sum_current_block_expenses);

        // 次の D 日間のブロックへ移動
        current_day_idx += free_days_per_pass;
    }

    std::cout << total_minimum_cost << '\n';

    return 0;
}

D - General Weighted Max Matching (最大重みマッチング)

N個の頂点を持つ完全グラフにおいて、最大重みマッチングを求める問題です。Nが最大16と非常に小さいため、ビットDP（Bitmask Dynamic Programming）という動的計画法を用いることができます。

ビットDPでは、整数値のビット列を使って、どの頂点が既にマッチング済みであるかの状態を表現します。例えば、maskのi番目のビットが1であれば、頂点iが使用済みであることを示します。

• max_matching_weight_dp[mask]を「maskで表される頂点集合がマッチングされたときの、その最大重み」と定義します。
• 目標は、max_matching_weight_dpテーブル全体の中から最大値を見つけることです。これは、Nが奇数の場合でも、一部の頂点がマッチングされない状態を含めて最大重みマッチングを正しく求めるためです。
• DPのベースケースはmax_matching_weight_dp[0] = 0です。これはどの頂点もマッチングされていない状態での重みは0であることを意味します。
• DPの遷移は以下のようになります。
  1. maskを0から(1 << N) - 1まで小さい順に処理します。
  2. もしmax_matching_weight_dp[mask]が未計算（初期値-1）であれば、その状態は到達不可能なのでスキップします。
  3. mask内で最も小さいインデックスを持つ未マッチングの頂点u_node_idxを見つけます。
  4. 次に、u_node_idxを、mask内でまだ未マッチングの他の任意の頂点v_node_idx（u_node_idx < v_node_idx）とマッチングさせることを考えます。
  5. 新しい状態next_mask = mask | (1 << u_node_idx) | (1 << v_node_idx)を計算し、max_matching_weight_dp[next_mask] = std::max(max_matching_weight_dp[next_mask], max_matching_weight_dp[mask] + adjacency_weights[u_node_idx][v_node_idx])で更新します。
• このプロセスにより、全ての可能なマッチングの組み合わせが効率的に探索され、最大重みが計算されます。

#include <iostream>
#include <vector>
#include <algorithm> // std::max のために必要

// dpテーブル: max_matching_weight_dp[mask] = maskで表される頂点集合がマッチングされたときの最大重み
// Nが最大16なので、2^16 = 65536 個の状態に対応
std::vector<long long> max_matching_weight_dp;
// グラフの重み行列
std::vector<std::vector<int>> adjacency_weights;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int num_nodes; // N: 頂点の数
    std::cin >> num_nodes;

    // 重み行列の読み込み (0-indexed に調整)
    adjacency_weights.resize(num_nodes, std::vector<int>(num_nodes));
    for (int i = 0; i < num_nodes; ++i) {
        for (int j = i + 1; j < num_nodes; ++j) {
            std::cin >> adjacency_weights[i][j];
            adjacency_weights[j][i] = adjacency_weights[i][j]; // 無向グラフなので対称
        }
    }

    // DPテーブルの初期化: 未計算状態を-1で表す
    int max_mask_value = (1 << num_nodes); // 2^N
    max_matching_weight_dp.assign(max_mask_value, -1);
    max_matching_weight_dp[0] = 0; // どの頂点もマッチングされていない状態は重み0

    // DP計算: maskを0から(2^N - 1)まで順に処理
    for (int mask = 0; mask < max_mask_value; ++mask) {
        if (max_matching_weight_dp[mask] == -1) {
            continue; // この状態は到達不可能（前の状態から遷移してこなかった）
        }

        // mask内で最も小さいインデックスを持つ未マッチングの頂点 u_node_idx を見つける
        int u_node_idx = -1;
        for (int i = 0; i < num_nodes; ++i) {
            if (!((mask >> i) & 1)) { // i番目のビットが0であれば未マッチング
                u_node_idx = i;
                break;
            }
        }

        // 全ての頂点がマッチング済みであれば、これ以上マッチングはできない
        if (u_node_idx == -1) {
            continue;
        }

        // 頂点 u_node_idx を、mask内でまだ未マッチングの他の頂点 v_node_idx とマッチングさせる
        // v_node_idx は u_node_idx より大きいインデックスから探し始めると、重複なく効率的に処理できる
        for (int v_node_idx = u_node_idx + 1; v_node_idx < num_nodes; ++v_node_idx) {
            if (!((mask >> v_node_idx) & 1)) { // v_node_idx番目のビットが0であれば未マッチング
                // 新しいマスクを計算: u_node_idx と v_node_idx をマッチング済みとして設定
                int next_mask = mask | (1 << u_node_idx) | (1 << v_node_idx);
                // DP遷移: 現在の重みに新しいマッチングの重みを加算
                max_matching_weight_dp[next_mask] = std::max(max_matching_weight_dp[next_mask], 
                                                             max_matching_weight_dp[mask] + adjacency_weights[u_node_idx][v_node_idx]);
            }
        }
    }

    // Nが奇数の場合など、完全にマッチングできないケースも考慮し、dpテーブル内の最大値が最終的な答えとなる
    long long final_max_weight = 0;
    for (int mask = 0; mask < max_mask_value; ++mask) {
        final_max_weight = std::max(final_max_weight, max_matching_weight_dp[mask]);
    }
    
    std::cout << final_max_weight << '\n';

    return 0;
}

E - Sandwiches (サンドイッチ)

長さNの整数列Aが与えられ、A_i = A_kかつi < j < kを満たす三つ組(i, j, k)の「値」の合計を求める問題です。各三つ組の値はk - i - 1と定義されています。これは実質的に、A_i = A_kかつi < j < kを満たす全ての(i, j, k)の組に対して1を数え上げ、その合計を求めることと同じです。

愚直に全ての三つ組を探索するとO(N^3)となり、N=2*10^5では時間切れとなるため、より効率的な数え上げの手法が必要です。

**効率的な数え上げの考え方:**

1. まず、各ユニークな値Xについて、配列Aの中でXが出現する全てのインデックスを収集し、リストに格納します。例えば、値Xがインデックスp_0, p_1, ..., p_{m-1}に出現したとします。
2. 次に、このインデックスリスト[p_0, p_1, ..., p_{m-1}]内の隣接するペア(p_s, p_{s+1})に注目します。
3. この隣接する2つのインデックスp_sとp_{s+1}の間には、p_{s+1} - p_s - 1個のインデックスjが存在します。これらのjは、三つ組(i, j, k)のjになる可能性があります。
4. それぞれのjの位置は、A_i = Xとなるi（p_sまたはそれより左のインデックス）と、A_k = Xとなるk（p_{s+1}またはそれより右のインデックス）によって挟まれることができます。
   • p_sを含め、それより左側にあるXの出現回数はs + 1個（p_0からp_sまで）。これらがiになり得ます。
   • p_{s+1}を含め、それより右側にあるXの出現回数はm - (s + 1)個（p_{s+1}からp_{m-1}まで）。これらがkになり得ます。
5. したがって、隣接するインデックスp_sとp_{s+1}の間にあるjのそれぞれの位置に対して、 (s + 1) * (m - (s + 1)) 通りの(i, k)ペアと組になることができます。
6. この積（(p_{s+1} - p_s - 1) * (s + 1) * (m - (s + 1))）を、全ての値X、そしてその値の全ての隣接インデックスペア(p_s, p_{s+1})について合計することで、最終的な答えが得られます。

#include <iostream>
#include <vector>
#include <algorithm> // (このコードでは直接使用しないが、ソートなどでよく使われる)

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);

    int array_length; // N: 配列 A の長さ
    std::cin >> array_length;

    // 各値が出現するインデックスを格納するリスト
    // A_i の値は 1 から N までなので、サイズ N+1 のベクターのベクターで対応
    std::vector<std::vector<long long>> value_occurrences(array_length + 1);

    for (int i = 0; i < array_length; ++i) {
        long long current_element_value; // A[i] の値
        std::cin >> current_element_value;
        value_occurrences[current_element_value].push_back(i); // 0-indexed でインデックスを記録
    }

    long long total_sandwich_triplets = 0; // すべてのサンドイッチトリプレットの合計値

    // 各ユニークな値について処理
    for (int val = 1; val <= array_length; ++val) {
        const auto& indices_for_val = value_occurrences[val];

        // 同じ値が2回以上出現しないとサンドイッチは作れない
        if (indices_for_val.size() < 2) {
            continue;
        }

        // 隣接するインデックスペア (p_s, p_{s+1}) を調べるループ
        // indices_for_val は p_0, p_1, ..., p_{m-1} の形式で格納されている
        for (int s_idx = 0; s_idx < indices_for_val.size() - 1; ++s_idx) {
            long long left_idx_ps = indices_for_val[s_idx];       // A_i となる左側のインデックス
            long long right_idx_ps_plus_1 = indices_for_val[s_idx + 1]; // A_k となる右側のインデックス

            // p_s と p_{s+1} の間に存在する j の数
            long long num_middle_j_candidates = right_idx_ps_plus_1 - left_idx_ps - 1;

            if (num_middle_j_candidates <= 0) {
                continue; // 間に j が存在しない場合はスキップ
            }

            // p_s を i として利用できる、p_0 から p_s までの X の数
            long long count_left_endpoints = s_idx + 1;
            // p_{s+1} を k として利用できる、p_{s+1} から p_{m-1} までの X の数
            long long count_right_endpoints = indices_for_val.size() - (s_idx + 1);

            // この隣接ペアによって生成される全てのサンドイッチトリプレットの値を合計に加算
            total_sandwich_triplets += num_middle_j_candidates * count_left_endpoints * count_right_endpoints;
        }
    }

    std::cout << total_sandwich_triplets << '\n';

    return 0;
}