結果

問題 No.3363 Two Closest Numbers
コンテスト
ユーザー D M
提出日時 2026-01-08 11:01:18
言語 C++23
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 213 ms / 2,000 ms
コード長 3,470 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 7,151 ms
コンパイル使用メモリ 389,064 KB
実行使用メモリ 7,852 KB
最終ジャッジ日時 2026-01-08 11:01:29
合計ジャッジ時間 10,606 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 59
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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

#define rep(i, x, limit) for (int i = (int)(x); i < (int)(limit); i++)
#define all(x) (x).begin(), (x).end()
#define el '\n'

using ll = long long;
const ll infl = (1LL<<60);
const ll MOD = 998244353;

// 任意型のベクターをランレングス圧縮して (値, 出現回数) のペア一覧を返す
template<typename T>
vector<pair<T,int>> runLengthEncode(const vector<T>& arr) {
    vector<pair<T,int>> result;
    if (arr.empty()) return result;
    T prev = arr[0];
    int count = 1;
    for (size_t i = 1; i < arr.size(); ++i) {
        if (arr[i] == prev) ++count;
        else {
            result.emplace_back(prev, count);
            prev = arr[i];
            count = 1;
        }
    }
    result.emplace_back(prev, count);
    return result;
}

// stc(サイズm=偶数)を m/2 と m/2 に分けて並べ替え、|X-Y|の最小を総当たり
static ll solve_small(vector<ll> stc){
    int m = (int)stc.size();
    if (m == 0) return 0;
    int half = m/2;
    ll best = infl;

    // 要素が重複するので、順列列挙は next_permutation でOK（重複は多少増えるが m<=10 程度なら十分）
    // 分割はビットマスクで総当たり（m<=10想定）
    for(int mask=0; mask < (1<<m); mask++){
        if (__builtin_popcount((unsigned)mask) != half) continue;
        vector<ll> A, B;
        A.reserve(half); B.reserve(half);
        for(int i=0;i<m;i++){
            if(mask&(1<<i)) A.push_back(stc[i]);
            else B.push_back(stc[i]);
        }
        sort(all(A));
        sort(all(B));
        do{
            // BはAごとに最初から回す（next_permutationは最後で昇順に戻るが、明示しておくと安全）
            vector<ll> B0 = B;
            do{
                ll a=0,b=0;
                for(int i=0;i<half;i++){
                    a = a*10 + A[i];
                    b = b*10 + B[i];
                }
                best = min(best, llabs(a-b));
            }while(next_permutation(all(B)));
            B = B0;
        }while(next_permutation(all(A)));
    }
    return best;
}

#include <atcoder/all>
using namespace atcoder;
using mint = modint998244353;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    ll n; cin >> n;
    vector<ll> C(n);
    rep(i,0,n) cin >> C[i];

    if(n%2==0){
        sort(all(C));
        auto rle = runLengthEncode(C);

        // digitの出現回数を数える（1..9）
        vector<int> cnt(10,0);
        for(auto &[a,b]: rle) cnt[(int)a] = b;

        // 奇数回出現した数字を1個ずつ集める
        vector<ll> base;
        for(int d=1; d<=9; d++){
            if(cnt[d]%2==1) base.push_back(d);
        }

        ll ans = solve_small(base);

        // ★追加：どれか1種類の数字を2個足したケースも試す
        // 供給可能条件：cnt[d] >= (cnt[d]%2) + 2
        for(int d=1; d<=9; d++){
            if(cnt[d] < (cnt[d]%2) + 2) continue;
            auto stc = base;
            stc.push_back(d);
            stc.push_back(d);
            ans = min(ans, solve_small(stc));
        }

        cout << (ans % MOD) << el;
    }else{
        sort(all(C));
        vector<ll> A(C.begin(), C.begin()+n/2+1);
        vector<ll> B(C.rbegin(), C.rbegin()+n/2);

        mint x=0,y=0;
        for(ll v: A){ x*=10; x+=v; }
        for(ll v: B){ y*=10; y+=v; }
        mint ans = x - y;
        cout << ans.val() << el;
    }
}
0