Google Code Jam 2021 Round 3 1問目 - Build-A-Pair

Source

Google Code Jam 2021 Round 3 1問目 (3pts, 12pts)
問題文

問題概要

省略

解法

省略

cLay（version 20210607-1）のコード

C++に変換後のコードはこちら

int TEST;
int N; char S[40];
int ps, p[20];
int hist[10], h[10];

__int128_t greed(__int128_t x, __int128_t y){
  rep(i,10) h[i] = hist[i];
  for(;;){
    rep(i,10) if(h[i]) break;
    if(i==10) break;

    rrep(i,10) if(h[i]) break;
    y = 10 * y + i; h[i]--;

    rep(i,10) if(h[i]) break;
    x = 10 * x + i; h[i]--;
  }
  return x - y;
}

{
  int i, j, k;
  REP(TEST, rd_int()){
    __int128_t res = ll_inf;
    wtF("Case #{TEST+1}: ");
    rd(S@N);
    rep(i,10) hist[i] = 0;
    rep(i,N) hist[S[i]-'0']++;

    if(N%2){
      rep(i,1,10) if(hist[i]){
        hist[i]--;
        res <?= greed(i,0);
        hist[i]++;
      }
    } else {
      ps = 0;
      rep(i,10) rep(hist[i]/2) p[ps++] = i;
      if(ps == N/2) res = 0;
      rep(mask, 1<<ps){
        k = -1;
        rep(i,ps) if(BIT_ith(mask,i)) k >?= p[i];
        if(k == 0) continue;
        rep(i,ps) if(BIT_ith(mask,i)) hist[p[i]] -= 2;
        rep(i,10) if(hist[i]) rep(j,i) if(hist[j]){
          if(mask == 0 && j==0) continue;
          (hist[i], hist[j])--;
          res <?= greed(i,j);
          (hist[i], hist[j])++;
        }
        rep(i,ps) if(BIT_ith(mask,i)) hist[p[i]] += 2;
      }
    }

    wt(res);
  }
}

Current time: 2024年04月20日01時24分38秒
Last modified: 2021年06月07日22時53分54秒 (by laycrs)
Tags: Competitive_Programming_Incomplete Google_Code_Jam GCJ_2021 GCJ_2021_Round_3
トップページに戻る

Logged in as: unknown user (not login)