結果

問題 No.453 製薬会社
ユーザー souta-1326
提出日時 2021-08-20 17:37:44
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 6,761 bytes
コンパイル時間 2,623 ms
コンパイル使用メモリ 206,380 KB
最終ジャッジ日時 2025-01-23 23:03:43
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 9
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const ll inf = 10000000000;
template<class T> class frac{
  T bunsi,bunbo;
  constexpr void setting() noexcept {
    T g = gcd(bunsi,bunbo);
    bunsi /= g;bunbo /= g;
    if(bunbo < 0){
      bunsi = -bunsi;bunbo = -bunbo;
    }
  }
public:
  constexpr frac(T Bunsi = 0,T Bunbo = 1) noexcept {
    bunsi = Bunsi;bunbo = Bunbo;
    setting();
  }
  constexpr T &Bunsi() noexcept {return bunsi;}
  constexpr const T &Bunsi() const noexcept {return bunsi;}
  constexpr T &Bunbo() noexcept {return bunbo;}
  constexpr const T &Bunbo() const noexcept {return bunbo;}
  constexpr frac<T> &operator+=(const frac<T> &rhs) noexcept {
    bunsi = bunsi*rhs.bunbo+bunbo*rhs.bunsi;
    bunbo *= rhs.bunbo;
    setting();
    return *this;
  }
  constexpr frac<T> &operator-=(const frac<T> &rhs) noexcept {
    bunsi = bunsi*rhs.bunbo-bunbo*rhs.bunsi;
    bunbo *= rhs.bunbo;
    setting();
    return *this;
  }
  constexpr frac<T> &operator*=(const frac<T> &rhs) noexcept {
    bunbo *= rhs.bunbo;
    bunsi *= rhs.bunsi;
    setting();
    return *this;
  }
  constexpr frac<T> &operator/=(const frac<T> &rhs) noexcept {
    bunbo *= rhs.bunsi;
    bunsi *= rhs.bunbo;
    setting();
    return *this;
  }
  constexpr frac<T> &operator+=(const T rhs) noexcept {
    bunsi = bunsi+bunbo*rhs;
    setting();
    return *this;
  }
  constexpr frac<T> &operator-=(const T rhs) noexcept {
    bunsi = bunsi-bunbo*rhs;
    setting();
    return *this;
  }
  constexpr frac<T> &operator*=(const T rhs) noexcept {
    bunsi *= rhs;
    setting();
    return *this;
  }
  constexpr frac<T> &operator/=(const T rhs) noexcept {
    bunbo *= rhs;
    setting();
    return *this;
  }
  constexpr frac<T> operator+(const frac<T> &rhs) const noexcept {return frac(*this) += rhs;}
  constexpr frac<T> operator-(const frac<T> &rhs) const noexcept {return frac(*this) -= rhs;}
  constexpr frac<T> operator*(const frac<T> &rhs) const noexcept {return frac(*this) *= rhs;}
  constexpr frac<T> operator/(const frac<T> &rhs) const noexcept {return frac(*this) /= rhs;}
  constexpr frac<T> operator+(const T rhs) const noexcept {return frac(*this) += rhs;}
  constexpr frac<T> operator-(const T rhs) const noexcept {return frac(*this) -= rhs;}
  constexpr frac<T> operator*(const T rhs) const noexcept {return frac(*this) *= rhs;}
  constexpr frac<T> operator/(const T rhs) const noexcept {return frac(*this) /= rhs;}
  constexpr bool operator<(const frac<T> &rhs) const noexcept {return bunsi*rhs.bunbo < bunbo*rhs.bunsi;}
  constexpr bool operator>(const frac<T> &rhs) const noexcept {return bunsi*rhs.bunbo > bunbo*rhs.bunsi;}
  constexpr bool operator>=(const frac<T> &rhs) const noexcept {return bunsi*rhs.bunbo >= bunbo*rhs.bunsi;}
  constexpr bool operator<=(const frac<T> &rhs) const noexcept {return bunsi*rhs.bunbo <= bunbo*rhs.bunsi;}
  constexpr bool operator==(const frac<T> &rhs) const noexcept {return bunsi*rhs.bunbo == bunbo*rhs.bunsi;}
  constexpr bool operator!=(const frac<T> &rhs) const noexcept {return bunsi*rhs.bunbo != bunbo*rhs.bunsi;}
  constexpr bool operator<(const T rhs) const noexcept {return bunsi < bunbo*rhs;}
  constexpr bool operator>(const T rhs) const noexcept {return bunsi > bunbo*rhs;}
  constexpr bool operator<=(const T rhs) const noexcept {return bunsi <= bunbo*rhs;}
  constexpr bool operator>=(const T rhs) const noexcept {return bunsi >= bunbo*rhs;}
  constexpr bool operator==(const T rhs) const noexcept {return bunsi == bunbo*rhs;}
  constexpr bool operator!=(const T rhs) const noexcept {return bunsi != bunbo*rhs;}
};
template<class T> void print(frac<T> &f){
  cout << f.Bunsi() << "/" << f.Bunbo() << endl;
}
using F = long double;


pair<F,vector<F>> Simplex_Method(ll N,ll M,vector<F> C,vector<vector<F>> A,vector<F> B){
  assert(C.size() == N && A.size() == M && B.size() == M);
  for(int i=0;i<M;i++) assert(A[i].size() == N);
  F Ans = 0;//最大値
  vector<F> X(N);//最大値を取る数列x

  //スラック変数を導入する
  //M個の条件に対し1つずつスラック変数を用意するので、スラック変数をM個追加
  X.resize(N+M);
  C.resize(N+M);
  for(int i=0;i<M;i++) A[i].resize(N+M);

  //スラック変数を初期化 X[N+i]=B[i],A[i][N+i]=1
  for(int i=0;i<M;i++) X[N+i] = B[i];
  for(int i=0;i<M;i++) A[i][N+i] = 1;

  //スラック変数であるならば条件のindex,なければ-1
  vector<int> Slack(N+M,-1);
  for(int i=0;i<M;i++) Slack[N+i] = i;

  //i番目の条件のスラック変数のindex
  vector<int> A_Slack(M);
  for(int i=0;i<M;i++) A_Slack[i] = N+i;

  //操作ができるまで
  while(true){
    //正の係数をとる非スラック変数を探す
    int target = -1;
    for(int i=0;i<N+M;i++){
      if(Slack[i] == -1 && C[i] > 0){
        target = i;break;
      }
    }

    //もしすべての係数が正でなかったら、操作を終了
    if(target == -1) break;

    //スラック変数の余裕がある限りX[target]を増やす
    //各条件で増やせる量のminを取れば良い
    //targetと、minを取る条件のスラック変数をswapするので、その条件のindexも記録する
    //いくらでも増やせる場合、infを返し操作を終了

    F minval = inf;
    int minitr = -1;
    for(int i=0;i<M;i++){
      if(A[i][target] <= 0) continue;
      if(B[i]/A[i][target] < minval){
        minval = B[i]/A[i][target];
        minitr = i;
      }
    }
    if(minval == inf){
      Ans = inf;break;
    }

    //A[minitr]以外の条件式に対して変更を行う
    for(int i=0;i<M;i++){
      if(i == minitr || A[i][target] == 0) continue;
      F propo = A[i][target]/A[minitr][target];
      //B[i]の値を変更
      B[i] -= B[minitr]*propo;
      //スラック変数の値を変更
      X[A_Slack[i]] = B[i]/A[i][A_Slack[i]];
      //A[i]の各値を変更
      for(int j=0;j<N+M;j++){
        A[i][j] -= A[minitr][j]*propo;
      }
    }

    //最大化式も変更
    F propo = C[target]/A[minitr][target];
    Ans += B[minitr]*propo;
    for(int j=0;j<N+M;j++){
      C[j] -= A[minitr][j]*propo;
    }

    //最後にスラック変数をSwap
    X[target] = B[minitr]/A[minitr][target];
    X[A_Slack[minitr]] = 0;
    
    Slack[target] = minitr;
    Slack[A_Slack[minitr]] = -1;
    A_Slack[minitr] = target;
  }
  
  //出力
  vector<F> SubX;
  copy(X.begin(),X.begin()+N,back_inserter(SubX));
  return make_pair(Ans,SubX);
}
int main(){
  cout << fixed << setprecision(10);
  int C,D;cin >> C >> D;
  int N = 2,M = 2;
  vector<F> Ma({1000,2000});
  vector<vector<F>> A({{F(3)/4,F(2)/7},{F(1)/4,F(5)/7}});
  vector<F> B({F(C),F(D)});
  auto ret = Simplex_Method(N,M,Ma,A,B);
  F ans = ret.first;
  cout << ans << endl;
}
0