Codeforces Round #690 (Div. 3) - 接着剤の精進日記

A. Favorite Sequence

問題文に書いてあるとおりに前後前後…の順に出力
deque使えば楽だったね
提出コード

void solve(){
    int n;
    cin >> n;
    vector<ll> b(n);
    REP(i,n) cin >> b[i];
    vector<int> ans;
    REP(i,n/2){
        ans.emplace_back(b[i]);
        ans.emplace_back(b[n-i-1]);
    }
    if(n & 1) ans.emplace_back(b[n/2]);
    REP(i,n) cout << ans[i] << " ";
    cout << endl;
}

B. Last Year's Substring

先頭からのsubstringと後ろからのsubstringで2020を作れるかを判定する
提出コード

void solve(){
    int n;
    string s;
    cin >> n >> s;
    if(n < 4){
        cout << "NO" << endl;
        return;
    }

    for(int i=0;i<=4;i++){
        string t = s.substr(0,i);
        t += s.substr(n-4+i, 4-i);
        if(t == "2020"){
            cout << "YES" << endl;
            return;
        }
    }
    cout << "NO" << endl;
}

C. Unique Number

よくわからないので手元で計算して埋め込んだ
和が大きくなるように貪欲に作っていって、出来た文字列をソートすればいい
提出コード

vector<ll> mi = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 19, 29, 39, 49, 59, 69, 79, 89, 189, 289, 389, 489, 589, 689,789, 1789, 2789, 3789, 4789, 5789, 6789, 16789, 26789, 36789, 46789, 56789, 156789, 256789,356789, 456789, 1456789, 2456789, 3456789, 13456789, 23456789, 123456789, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000, 1000000000000000000};
void solve(){
    int x;
    cin >> x;
    ll ans = mi[x];
    if(ans == LINF) ans = -1;
    cout << ans << endl;
}

D. Number into Sequence

操作を行って最終的に残る数を$ x $とすると、$ x, x, x, ... $のように$ x $が連続したものになる
$ a $の総和は不変のため、上記のような$ x $の候補は総和の約数になる
よってこの約数それぞれに対し、操作が可能かどうかと可能ならその操作回数を調べればいい
提出コード

void solve(){
    int n;
    cin >> n;
    vector<int> a(n);
    int sum = 0;
    REP(i,n){
        cin >> a[i];
        sum += a[i];
    }
    auto res = divisor(sum);
    ll ans = n-1;
    for(auto x : res){
        int cur = 0;
        REP(i,n){
            cur += a[i];
            if(cur == x) cur = 0;
            else if(cur > x){
                cur = -1;
                break;
            }
        }
        if(cur == 0){
            chmin(ans, n-sum/x);
        }
    }
    cout << ans << endl;
}

E2. Close Tuples (hard version)

数列をソートして考える
このとき最小値を固定してその組み合わせの数を加算していく
$ a_i $を最小値として固定したとき、$ a_i + a_r \leq k $を満たす一番右端のindexを$ r $とすると、$ r - i - 1 $個の中から$ m - 1 $個選ぶ組み合わせの数になるので各$ i $に対して$ _{r - i - 1} C _{m - 1} $の総和を求めればいい
提出コード

void solve(){
    int n, m, k;
    cin >> n >> m >> k;
    vector<int> a(n);
    REP(i,n) cin >> a[i];
    sort(a.begin(), a.end());

    mint ans = 0;
    REP(i,n){
        int t = upper_bound(a.begin(), a.end(), a[i]+k) - a.begin();
        t -= (i + 1);
        if(t >= m-1) ans += bc.com(t, m-1);
    }
    cout << ans << endl;
}

F. The Treasure of The Segments

区間$ [ l_i, r_i] $がいくつの区間を覆っているかは、全ての区間の個数から$ r_j \lt l_i $を満たす個数と$ r_i \lt l_k $を満たす個数を引いたものになる
これは累積和を使えば計算できるが、値が大きいので座圧する必要がある
提出コード

void solve(){
    int n;
    cin >> n;
    vector<int> l(n), r(n);
    Compress<int> cmp;
    REP(i,n){
        cin >> l[i] >> r[i];
        cmp.add(l[i]);
        cmp.add(r[i]);
    }
    cmp.add(0);
    cmp.add(INF+10);
    cmp.build();
    int sz = cmp.size();
    vector<int> cumL(sz+1), cumR(sz+1);
    REP(i,n){
        cumL[cmp.get(r[i])]++;
        cumR[cmp.get(l[i])]++;
    }
    REP(i,sz) cumL[i+1] += cumL[i];
    for(int i=sz-1;i>0;i--) cumR[i-1] += cumR[i];
    int ans = 0;
    REP(i,n){
        chmax(ans, n - cumL[cmp.get(l[i])-1] - cumR[cmp.get(r[i])+1]);
    }
    cout << n - ans << endl;
}