Codeforces Round #635 (Div. 2) D. Xenia and Colorful Gems

D. Xenia and Colorful Gems

問題へのリンク

問題概要

から一つずつ数を選び、としたとき、

とする。の最小値を求めよ。

制約

• 
• 

解説

方針として、

1. 真ん中を固定して、左右を二分探索で決める
2. 左端右端を決め打って、真ん中を全探索

がある。今回2.の方針を取ったので、そちらを解説する。コンテスト中は、多くの人が1.の方針で解いていたような気がする。

すべてまとめてソートする

こういう数に種類があるやつは、とりあえず色を覚えておいてソートしがちです。こうすると、3種類を選ぶのですが、左端と右端はあまり離れてほしくないことがわかります。左端と右端を小さくする貪欲をしていきましょう。

単純な解き方として、前から配列を走査しながら、3種類になるまでみる範囲を伸ばすという方法があります。また、3種類になる前に、同じ種類が出てきたら、そちらに役目を預けて、最初に選んでいたものは捨てるべきでしょう。なぜなら、左端と右端を小さくしたいからです。

このアルゴリズムだけで、線形で解けてしまいます。実装は少し煩雑ですが、dequeを使うことで比較的綺麗に書くことができます。mapなどでdequeの中の種類数を管理しましょう。

提出

提出へのリンク

#include <bits/stdc++.h>
using namespace std;
#define rep(i,N) for(int i=0;i<int(N);++i)
#define rep1(i,N) for(int i=1;i<int(N);++i)
#define all(a) (a).begin(),(a).end()
typedef long long ll;
typedef pair<int, int> i_i;
typedef pair<ll, ll> l_l;
template <class T> using vec = vector<T>;
template <class T> using vvec = vector<vec<T>>;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }

const ll INFLL = (ll)1e18+1;

void solve(){
    int n[3];
    rep(i,3)cin >> n[i];
    vec<i_i> v;
    rep(i,3)rep(j,n[i]){
        int a;
        cin >> a;
        v.push_back({a, i});
    }
    sort(all(v));
    deque<i_i> q;
    int N = v.size();
    map<int, int> map;
    ll ans = INFLL * 3;
    rep(i,N){
        q.push_back(v[i]);
        map[v[i].second]++;
        while(q.size() > 1){
            if(q.front().second == q.back().second){
                map[q.front().second]--;
                q.pop_front();
            }
            else if(q.front().second == q[1].second){
                map[q.front().second]--;
                q.pop_front();
            }
            else break;
        }
        if(map[0] > 0 && map[1] > 0 && map[2] > 0){
            //calc
            ll l = q.front().first;
            ll r = q.back().first;
            int id1 = q.front().second;
            int id2 = q.back().second;
            for(int j = 1; j <= q.size() - 2;j++){
                if(q[j].second == 3 - id1 - id2){
                    ll mid = q[j].first;
                    ll tmp = 0;
                    tmp += (l - mid) * (l-mid);
                    tmp += (r - mid) * (r-mid);
                    tmp += (l - r) *   (l-r);
                    chmin(ans, tmp);
                }
            }
            map[q.front().second]--;
            q.pop_front();
        }
    }
    cout << ans << endl;
}
int main() {

    int Q;
    cin >> Q;
    while(Q--){
        solve();
    }
}