A - 二つの配列と要素の組み合わせ

問題文
2つの長さnの配列a,bが与えられる。この配列の各要素は少なくとも2回以上出現する。配列aとbを並べ替えて、c_i = a_i + b_iとなる長さnの配列cを作る。このcに3種類以上の異なる要素が存在するか判定せよ。

解法
n ≥ 3のため、aとbのそれぞれに含まれる異なる要素の数を確認する。aが1種類でbが2未満、または逆の場合にのみ「No」になる。

#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n;
    cin >> n;
    unordered_set<int> s1, s2;
    for (int i = 0; i < n; i++) {
        int x; cin >> x; s1.insert(x);
    }
    for (int i = 0; i < n; i++) {
        int x; cin >> x; s2.insert(x);
    }
    if ((s1.size() == 1 && s2.size() < 3) || (s2.size() == 1 && s1.size() < 3)) {
        cout << "No" << endl;
    } else {
        cout << "Yes" << endl;
    }
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T = 1; cin >> T;
    while (T--) solve();
}

B - 配列の分割コスト

問題文
長さnの整数配列aと偶数kが与えられる。aをk個のサブアレイに分割し、偶数インデックスのサブアレイを連結した配列bに0を追加する。b_i ≠ iとなる最小のiをコストとする。このコストの最小値を求めよ。

解法
k = nの場合は直接計算。それ以外では、b_1 ≠ 1を達成できる場合コストは1。達成不能な場合はaの先頭要素がすべて1の場合でコストは2。

#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n, k; cin >> n >> k;
    vector<int> arr(n+1);
    for (int i = 1; i <= n; i++) cin >> arr[i];
    
    if (k == n) {
        int idx = 1;
        for (int i = 2; i <= n; i += 2) {
            if (arr[i] != idx) {
                cout << idx << endl; return;
            }
            idx++;
        }
        cout << idx << endl; return;
    }
    
    for (int i = 2; i <= n - k + 2; i++) {
        if (arr[i] != 1) {
            cout << 1 << endl; return;
        }
    }
    cout << 2 << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T = 1; cin >> T;
    while (T--) solve();
}

C - サービスカウンターの最適化

問題文
n個のキューがある。n×nの2次元配列aが与えられ、a[i][j]はi番目のキューが時間jに受け取る人数を示す。各時間に1つのキューを空にできる。最終的に各キューの人数x_iのMEXを最大化せよ。

解法
最後に空にしたキューは0になる。他のキューでは連続する1の後ろの部分を維持し、最大の後ろの連続長mを取得する。これにより0～mの範囲で人数を調整可能。

#include <bits/stdc++.h>
using namespace std;
#define int long long

void solve() {
    int n; cin >> n;
    vector<int> suffix(n+1);
    vector<vector<int>> grid(n+1, vector<int>(n+1));
    
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> grid[i][j];
        }
        int cnt = 0;
        for (int j = n; j >= 1; j--) {
            if (grid[i][j] == 1) cnt++;
            else break;
        }
        suffix[i] = cnt;
    }
    
    multiset<int> mset;
    for (int i = 1; i <= n; i++) mset.insert(suffix[i]);
    
    int mex = 1;
    for (auto val : mset) {
        if (val >= mex) mex++;
    }
    cout << min(mex, n) << endl;
}

signed main() {
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    int T = 1; cin >> T;
    while (T--) solve();
}

D -

問題文

解法

コード