マトリックス操作と深さ優先探索（DFS）

最初の問題は、与えられたバイナリ行列を行の反転と列の置換によって目標の行列に一致させられるかを判定するものです。行の反転は同一の行に対して2回行うと無効になるため、各行に対する操作は「行う」か「行わないか」の二択です。

まず、各行の要素の合計値を見て、反転することが確定している行を処理します。特定の行において、現在の合計と目標の合計の和が列数と等しい場合、その行を反転する必要があります。それ以外の場合、合計値が一致しなければ解は存在しません。

しかし、合計値が列数の半分である行は、反転してもしなくても一意に決まらない曖昧な状態です。これらの行に対しては深さ優先探索（DFS）を用いて全パターンを試行し、その都度、列の置換のみで目標行列に一致するか（全単射が存在するか）を判定します。

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

const int MAX_N = 105;
int source[MAX_N][MAX_N], target[MAX_N][MAX_N];
int n, m;
int src_row_sum[MAX_N], tgt_row_sum[MAX_N];
bool is_solvable = false;

// 特定の行のビットを反転させる
void flip_row(int r) {
    for (int c = 1; c <= m; ++c) {
        source[r][c] ^= 1;
    }
}

// 現在の状態で列の置換によって目標状態と一致させられるか判定
bool check_columns() {
    int used[MAX_N] = {0};
    for (int i = 1; i <= m; ++i) {
        bool matched = false;
        for (int j = 1; j <= m; ++j) {
            if (used[j]) continue;
            bool equal = true;
            for (int k = 1; k <= n; ++k) {
                if (source[k][i] != target[k][j]) {
                    equal = false;
                    break;
                }
            }
            if (equal) {
                used[j] = 1;
                matched = true;
                break;
            }
        }
        if (!matched) return false;
    }
    return true;
}

// DFSの途中経過で部分整合性を確認するための関数（枝刈り用）
bool check_partial(int row_limit) {
    int used[MAX_N] = {0};
    for (int i = 1; i <= m; ++i) {
        bool matched = false;
        for (int j = 1; j <= m; ++j) {
            if (used[j]) continue;
            bool equal = true;
            for (int k = 1; k <= row_limit; ++k) {
                if (source[k][i] != target[k][j]) {
                    equal = false;
                    break;
                }
            }
            if (equal) {
                used[j] = 1;
                matched = true;
                break;
            }
        }
        if (!matched) return false;
    }
    return true;
}

// 深さ優先探索による行操作の決定
void dfs(int current_row) {
    if (is_solvable) return;
    if (current_row == n + 1) {
        if (check_columns()) is_solvable = true;
        return;
    }

    // 要素の合計が m/2 の場合のみ反転の選択肢がある
    if (src_row_sum[current_row] == m / 2) {
        // パターン1: 反転させない
        dfs(current_row + 1);
        
        // パターン2: 反転させる
        flip_row(current_row);
        if (check_partial(current_row)) {
            dfs(current_row + 1);
        }
        flip_row(current_row); // バックトラック
    } else {
        dfs(current_row + 1);
    }
}

int main() {
    int test_cases;
    cin >> test_cases;
    while (test_cases--) {
        cin >> n >> m;
        is_solvable = false;
        memset(src_row_sum, 0, sizeof(src_row_sum));
        memset(tgt_row_sum, 0, sizeof(tgt_row_sum));

        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j) {
                cin >> source[i][j];
                src_row_sum[i] += source[i][j];
            }
        for (int i = 1; i <= n; ++i)
            for (int j = 1; j <= m; ++j) {
                cin >> target[i][j];
                tgt_row_sum[i] += target[i][j];
            }

        bool possible = true;
        for (int i = 1; i <= n; ++i) {
            if (src_row_sum[i] + tgt_row_sum[i] == m) {
                flip_row(i);
            } else if (src_row_sum[i] != tgt_row_sum[i]) {
                possible = false;
                break;
            }
        }

        if (!possible) {
            cout << "NO" << endl;
        } else if (check_columns()) {
            cout << "YES" << endl;
        } else if (m % 2 == 0) {
            dfs(1);
            cout << (is_solvable ? "YES" : "NO") << endl;
        } else {
            cout << "NO" << endl;
        }
    }
    return 0;
}

最長の重複なし部分列問題（動的計画法）

次の問題は、数列から重複する要素を含まない最長の連続区間（部分列）を見つける問題です。これは動的計画法（DP）とハッシュマップを組み合わせることで効率的に解くことができます。

配列 $dp[i]$ を「位置 $i$ で終わる重複なし部分列の最大長」と定義します。各要素について、最後に出現した位置を記録しておき、現在の要素が以前に出現している場合、直前のDP値に1を加えたものと、直前の出現位置からの距離のうち小さい方を採用します。これは、直前の有効な区間を延長するか、新しく区間を切り直すかを判断するためです。

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

const int MAX_N = 1000006;
int data[MAX_N];
int dp[MAX_N];
map<int, int> last_pos;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 1; i <= n; ++i) {
        cin >> data[i];
    }

    int max_len = 0;
    for (int i = 1; i <= n; ++i) {
        int val = data[i];
        if (last_pos.count(val)) {
            // 重複がある場合：前回の出現位置からの距離 と 前のDP値+1 の小さい方
            int dist = i - last_pos[val];
            dp[i] = min(dist, dp[i - 1] + 1);
        } else {
            // 重複がない場合：前のDP値を延長
            dp[i] = dp[i - 1] + 1;
        }
        last_pos[val] = i;
        max_len = max(max_len, dp[i]);
    }
    cout << max_len << endl;
    return 0;
}

平均値の最大化と二分探索

最後は、長さが $F$ 以上である部分列の中で、平均値が最大になるものを求める問題です。部分列の全探索は計算量が膨大になるため、「二分探索」を用いて答えそのものを探索します。

判定関数において、平均値 $X$ を仮定し、各要素から $X$ を引いた値の配列を考えます。この配列の部分和が0以上になる長さ $F$ 以上の区間が存在すれば、平均 $X$ 以上の区間が存在することになります。この判定は前処理として累積和を計算し、そこから最小の累積和を管理しながら走査することで $O(N)$ で行えます。

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

int n, min_len;
vector<int> values;
vector<double> prefix_sum;

// 平均 avg 以上の区間が長さ min_len 以上で存在するか判定
bool is_feasible(double avg) {
    // 各要素から avg を引いた値の累積和を計算
    for (int i = 1; i <= n; ++i) {
        prefix_sum[i] = prefix_sum[i - 1] + (values[i] - avg);
    }
    
    // 双ポインタまたは最小値管理走査
    double min_val = 0.0;
    // i は区間の終点、j は区間の始点の候補
    for (int i = min_len, j = 0; i <= n; ++i, ++j) {
        min_val = min(min_val, prefix_sum[j]);
        if (prefix_sum[i] - min_val >= 0) {
            return true;
        }
    }
    return false;
}

int main() {
    cin >> n >> min_len;
    values.resize(n + 1);
    prefix_sum.resize(n + 1);
    
    double max_val = 0;
    for (int i = 1; i <= n; ++i) {
        cin >> values[i];
        max_val = max(max_val, (double)values[i]);
    }

    double left = 0, right = max_val;
    // 実数二分探索
    while (right - left > 1e-6) {
        double mid = (left + right) / 2.0;
        if (is_feasible(mid)) {
            left = mid;
        } else {
            right = mid;
        }
    }
    
    // 結果を1000倍して整数で出力
    cout << (int)(right * 1000) << endl;
    return 0;
}