Perform Easily - Codeforces Round #679 Div.2 C

Div.2 C問題なのに解けなかったよオヨヨ。 C問題は1438人、D問題は1664人が正解していてD問題が簡単そう。コンテスト中はCに固執せずDにも目を通すべきだった。

このコンテストは問題にNARUTOのキャラクタが出てくる。コドフォはよく問題文にキャラクタが登場する。

問題情報

問題名: Perform Easily
コンテスト: Codeforces Round #679 (Div. 2, based on Technocup 2021 Elimination Round 1)
問題番号: C(Div.1 A)

キーワード

二分探索木

問題概要

A、設定がまどろっこしいけど、n本のレーンにそれぞれ点が何個か乗っていてどのレーンでも1個以上点が含まれるような最短の区間を求めよ。まで定式化できれば途端にド典型 pic.twitter.com/Icw5TVZVy4
— phocom (@_phocom) 2020年10月25日

ギターに6本の弦と無限フレットがある。フレットには左から順に番号がついている。 N個の音符を演奏しなければならない。ある音符は重複あり6つのフレットで演奏できる。 N個すべての音符を演奏できるフレットの最大番号と最小番号の差の最小値は？

考えたこと

演奏で使うフレットはたかだか6N個。あるフレットを使うときのフレットの最大番号と最小番号の差を、すべてのフレットで探索する。フレットの最大番号と最小番号を高速で求めるため、演奏で使うN個のフレットをsetで管理する。新しいフレットをsetに入れて、新しいフレットで演奏する音符を演奏するフレットを取り出す。計算量はO(NlogN)。

コード

#include <algorithm>
#include <array>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <vector>
using namespace std;
#define int long long
constexpr long long INF = 1000000000000000000LL + 8;
constexpr int N = 6;

signed main() {
    cin.tie(0);
    ios::sync_with_stdio(0);

    array<int, N> a;
    for (int i = 0; i < N; i++) cin >> a[i];
    int n;
    cin >> n;
    vector<int> b(n);
    for (int i = 0; i < n; i++) cin >> b[i];

    sort(a.begin(), a.end());
    sort(b.begin(), b.end());

    // fn[i]: 弾くべき音符を弾けるfret番号と音符番号のペア
    set<pair<int, int>> num_note;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < N; j++) {
            const int num = b[i] - a[j];
            num_note.emplace(make_pair(num, i));
        }
    }

    // use_nums[i]: 音符iを弾くfret番号
    vector<int> use_nums(n, -1);
    // 今使うfret番号と音符番号の集合 最大値と最小値を得るのに使う
    set<pair<int, int>> minmaxnums;

    int ans = INF;

    // use_noteを小さい順から使っていく
    for (auto &&f : num_note) {
        // fと同じ音符を弾くfret音符ペアをminmaxnumsから削除する
        if (use_nums[f.second] > 0) {
            minmaxnums.erase(
                minmaxnums.find(make_pair(use_nums[f.second], f.second)));
        }

        // use_numsとminmaxnumsにfを追加する
        use_nums[f.second] = f.first;
        minmaxnums.emplace(f);

        // n個全ての音符を弾けるなら、minmaxnumsを使ってansを更新
        if (minmaxnums.size() == n) {
            const int dist_nums =
                (*prev(minmaxnums.end())).first - (*minmaxnums.begin()).first;
            ans = min(dist_nums, ans);
        }
    }

    cout << ans << "\n";
}