#1178826 (C++23) No.3674 Zero Sum Game

• 問題: No.3674 Zero Sum Game
• ユーザー: TKTYI
• 提出日時: 2026-08-25 03:22:49
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0)
• 結果: TLE
• 実行時間: -
• コード長: 4,057 bytes
• コンパイル時間: 4,579 ms
• コンパイル使用メモリ: 386,204 KB
• 実行使用メモリ: 9,776 KB
• 最終ジャッジ日時: 2026-09-04 22:43:58
• 合計ジャッジ時間: 9,700 ms
• ジャッジサーバーID （参考情報）: judge1_1 / judge3_0

ファイルパターン	結果
sample	AC * 1
other	TLE * 1 -- * 38

ソースコード

#include<bits/stdc++.h>
#include<atcoder/all>
using namespace std;
using namespace atcoder;
typedef long long int ll;
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vl;
typedef vector<vl> vvl;
typedef vector<vvl> vvvl;
typedef vector<vvvl> vvvvl;
typedef vector<bool> vb;
typedef vector<vb> vvb;
typedef vector<vvb> vvvb;
typedef vector<vvvb> vvvvb;
typedef pair<ll,ll> pl;
typedef pair<ll,pl> ppl;
typedef pair<ll,ppl> pppl;
typedef pair<ll,pppl> pppppl;
#define rep(i,a,b) for(int i=(a);i<(b);i++)
#define rrep(i,a,b) for(int i=(b)-1;i>=(a);i--)
#define all(a) begin(a),end(a)
#define sz(a) (int)(a).size()
#define F first
#define S second
#define bs(A,x) binary_search(all(A),x)
#define lb(A,x) (ll)(lower_bound(all(A),x)-A.begin())
#define ub(A,x) (ll)(upper_bound(all(A),x)-A.begin())
#define cou(A,x) (ll)(upper_bound(all(A),x)-lower_bound(all(A),x))
template<typename T>using min_priority_queue=priority_queue<T,vector<T>,greater<T>>;
template<class T>bool chmax(T&a,T b){if(a<b){a=b;return 1;}return 0;}
template<class T>bool chmin(T&a,T b){if(b<a){a=b;return 1;}return 0;}
//*
using mint=modint998244353;
const ll mod=998244353;
//*/
/*
using mint=modint1000000007;
const ll mod=1000000007;
//*/
//using mint=modint;
//*
typedef vector<mint> vm;
typedef vector<vm> vvm;
typedef vector<vvm> vvvm;
typedef vector<vvvm> vvvvm;
ostream&operator<<(ostream&os,mint a){os<<a.val();return os;}
istream&operator>>(istream&is,mint&a){int x;is>>x;a=mint(x);return is;}
//*/
template<typename T1,typename T2>ostream&operator<<(ostream&os,pair<T1,T2>p){os<<p.F<<" "<<p.S;return os;}
template<typename T1,typename T2>istream&operator>>(istream&is,pair<T1,T2>&p){is>>p.F>>p.S;return is;}
template<typename T>ostream&operator<<(ostream&os,vector<T>v){rep(i,0,sz(v))os<<v[i]<<(i+1!=sz(v)?" ":"");return os;}
template<typename T>istream&operator>>(istream&is,vector<T>&v){for(T&in:v)is>>in;return is;}

// https://github.com/kth-competitive-programming/kactl/blob/main/content/numerical/Simplex.h
typedef vector<int> vi;
typedef vector<ld> vd;
typedef vector<vd> vvd;
const ld eps=1e-8,inf=1/.0;
#define MP make_pair
#define ltj(X) if(s==-1||MP(X[j],N[j])<MP(X[s],N[s]))s=j
struct LPSolver{
  int m,n;
  vi N,B;
  vvd D;
  LPSolver(const vvd&A,const vd&b,const vd&c):m(sz(b)),n(sz(c)),N(n+1),B(m),D(m+2,vd(n+2)){
    rep(i,0,m)rep(j,0,n)D[i][j]=A[i][j];
    rep(i,0,m){B[i]=n+i;D[i][n]=-1;D[i][n+1]=b[i];}
    rep(j,0,n){N[j]=j;D[m][j]=-c[j];}
    N[n]=-1;D[m+1][n]=1;
  }
  void pivot(int r,int s){
    ld*a=D[r].data(),inv=1/a[s];
    rep(i,0,m+2)if(i!=r&&abs(D[i][s])>eps){
      ld*b=D[i].data(),inv2=b[s]*inv;
      rep(j,0,n+2)b[j]-=a[j]*inv2;
      b[s]=a[s]*inv2;
    }
    rep(j,0,n+2)if(j!=s)D[r][j]*=inv;
    rep(i,0,m+2)if(i!=r)D[i][s]*=-inv;
    D[r][s]=inv;
    swap(B[r],N[s]);
  }
  bool simplex(int phase){
    int x=m+phase-1;
    for(;;){
      int s=-1;
      rep(j,0,n+1)if(N[j]!=-phase)ltj(D[x]);
      if(D[x][s]>=-eps)return true;
      int r=-1;
      rep(i,0,m){
        if(D[i][s]<=eps)continue;
        if(r==-1||MP(D[i][n+1]/D[i][s],B[i])<MP(D[r][n+1]/D[r][s],B[r]))r=i;
      }
      if(r==-1)return false;
      pivot(r,s);
    }
  }
  ld solve(vd&x){
    int r=0;
    rep(i,1,m)if(D[i][n+1]<D[r][n+1])r=i;
    if(D[r][n+1]<-eps){
      pivot(r,n);
      if(!simplex(2)||D[m+1][n+1]<-eps)return -inf;
      rep(i,0,m)if(B[i]==-1){
        int s=0;
        rep(j,1,n+1)ltj(D[i]);
        pivot(i,s);
      }
    }
    bool ok=simplex(1);x=vd(n);
    rep(i,0,m)if(B[i]<n)x[B[i]]=D[i][n+1];
    return ok?D[m][n+1]:inf;
  }
};

int main(){
  cin.tie(0)->sync_with_stdio(0);
  cin.exceptions(cin.failbit);
  ll _;cin>>_;
  while(_--){
  	ll N,M;cin>>N>>M;
  	vvl A(N,vl(M));cin>>A;
  	ld l=-11000,r=11000;
  	rep(__,0,100){
  	  ld m=(l+r)/2;
  	  vvd X(M+2,vd(N,1));
  	  rep(i,0,N)rep(j,0,M)X[j][i]=A[i][j]-m;
  	  rep(i,0,N)X[M+1][i]=-1;
  	  vd y(M+2),z(N),x;
  	  y[M]=1;y[M+1]=-1;
      ld val=LPSolver(X,y,z).solve(x);
      if(val==-inf)l=m;
      else r=m;
  	}
  	printf("%.20Lf\n",(l+r)/2);
  }
  return 0;
}