\(1\) 枚目の解説より高速な解法を示します。
まず、\(a<b\) であるとき、 \(N\) ラウンド目で \(a\) 点を取るより \(N\) ラウンド目で \(b\) 点を取る方が最終結果が高くなることが示せます。
このことから、 \(N\) ラウンド目に取るべき点数を二分探索することが可能です。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int n,x;
  cin >> n >> x;
  vector<int> a(n-1);
  for(auto &nx : a){cin >> nx;}

  int l=0,r=100;
  while(l<=r){
    int te=(l+r)/2;
    vector<int> b=a;
    b.push_back(te);
    int sum=0,ma=0,mi=100;
    for(auto &nx : b){
      sum+=nx;
      ma=max(ma,nx);
      mi=min(mi,nx);
    }
    int score=sum-ma-mi;
    if(score>=x){r=te-1;}
    else{l=te+1;}
  }
  if(l>100){l=-1;}
  cout << l << "\n";
  return 0;
}

さらに、 \(N\) ラウンド目に取ったスコアと最終結果との関係を解析してみましょう。以下の結論が得られます。

• ( \(N-1\) ラウンド目までのスコアの最小値 ) を \(l\)
• ( \(N-1\) ラウンド目までのスコアの最大値 ) を \(r\)
• ( \(N-1\) ラウンド目までのスコアの総和 ) を \(s\)

とします。

• ( \(N\) ラウンド目のスコア ) \(\le l\) である場合、最終結果は \(s-r\) となる。
• \(l <\) ( \(N\) ラウンド目のスコア ) \(<r\) である場合、最終結果は \(s-l-r+\) ( \(N\) ラウンド目のスコア ) となる。
• ( \(N\) ラウンド目のスコア ) \(\ge r\) である場合、最終結果は \(s-l\) となる。

この結論から、場合分けにより \(l,r,s\) を求めた後は \(O(1)\) となる解法が導出できます。

#include<bits/stdc++.h>

using namespace std;

int main(){
  int n,x;
  cin >> n >> x;
  int l=100,r=0,s=0;
  for(int i=0;i<n-1;i++){
    int a;
    cin >> a;
    l=min(l,a);
    r=max(r,a);
    s+=a;
  }

  if(s-r >= x){cout << "0\n";return 0;}
  int need=x-(s-l-r);
  if(need <= r){cout << need << "\n";return 0;}
  cout << "-1\n";
  return 0;
}