結果
| 問題 |
No.1122 Plane Tickets
|
| コンテスト | |
| ユーザー |
 startcpp
|
| 提出日時 | 2020-07-22 22:27:36 |
| 言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 7,180 bytes |
| コンパイル時間 | 1,196 ms |
| コンパイル使用メモリ | 91,548 KB |
| 実行使用メモリ | 6,948 KB |
| 最終ジャッジ日時 | 2024-06-22 19:06:58 |
| 合計ジャッジ時間 | 2,700 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 13 WA * 42 |
ソースコード
//http://zeus.mech.kyushu-u.ac.jp/~tsuji/java_edu/Simplex_st.htmlを参考に実装.
//整数計画じゃないから最適より大きい値が出る可能性、普通にあるのよねぇ…
#include <iostream>
#include <vector>
#include <tuple>
#include <cassert>
#include <string> //表示用関数で使っている
#define rep(i, n) for(i = 0; i < n; i++)
using namespace std;
typedef vector<double> Vector;
typedef vector<Vector> Mat;
//a >= 0
string toString(int a) {
if (a == 0) return "0";
string s;
while (a > 0) {
s += (char)((a % 10) + '0');
a /= 10;
}
int l = 0, r = s.length() - 1;
while (l < r) {
char c = s[l]; s[l] = s[r]; s[r] = c;
l++;
r--;
}
return s;
}
//表示用. とりあえず整数部分は全て変換. 小数点以下はketa桁まで変換. 基本, 切捨て.
//・-2.775が"-2.774"に変換されたり、0.53が"0.530"に変換されてしまう不具合。浮動小数点数誤差っぽい。
//・微小値epsを用意して、a < 0ならepsを引いておき、a > 0ならepsを足しておく。
//・"0.530"のようになったら、小数部の末尾の0を消す. 全部消えたら小数点も消す.
string toString(double a, int keta) {
bool minus_flag = false;
//ここ、aが大きいほど足し引きする微小量も大きくした方がいいんだけど、面倒くさいからこうしている。
if (a >= 0) {
a += 1e-12;
}
else {
minus_flag = true;
a -= 1e-12;
}
int ia = a; //example. a = -2.5 -> ia = -2. a = 2.5 -> ia = 2. a = 0.1 -> ia = 0.
string istr;
if (minus_flag) istr += "-";
istr += toString(ia * ((ia < 0) ? -1 : 1));
double da = a - ia;
if (da < 0) da = -da;
string dstr;
int i;
for (i = 0; i < keta; i++) {
da *= 10;
int val = (int)da;
dstr += (char)('0' + val);
da -= val;
}
for (i = (int)dstr.length() - 1; i >= 0; i--) {
if (dstr[i] != '0') {
break;
}
}
int lim_i = i;
string dStr;
for (i = 0; i <= lim_i; i++) {
dStr += dstr[i];
}
if (dStr.length() == 0) return istr;
return istr + "." + dStr;
}
//手抜き実装なので、10変数以上あると表示が崩れます.
void print_simplex_state(vector<int> &ids, Mat &table, Vector &con) {
int i, j;
vector<int> max_length(table[0].size(), 0);
rep(i, table.size()) {
rep(j, table[i].size()) {
max_length[j] = toString(table[i][j], 6).length();
}
}
rep(j, table[0].size()) {
int length = 2 + toString(i).length();
if (max_length[j] < length) max_length[j] = length;
}
cout << "基底変数 | ";
rep(i, table[0].size()) {
string str = toString(i);
for (j = 0; j + str.length() + 2 < max_length[i]; j++) {
cout << " ";
}
cout << "x_" << str << ", ";
}
cout << "定数項" << endl;
rep(i, table.size()) {
if (ids[i] == -1) cout << "z | ";
else {
string str = toString(ids[i]);
cout << "x_" << str;
for (j = 2 + str.length(); j < 9; j++) cout << " ";
cout << "| ";
}
rep(j, table[i].size()) {
string str = toString(table[i][j], 6);
for (int k = 0; k + str.length() < max_length[j]; k++) cout << " ";
cout << table[i][j] << ", ";
}
cout << con[i] << endl;
}
cout << endl;
}
//max. cx, s.t Ax <= bを解く. xはベクトル. x = 0は条件を満たすと仮定する.
//[非基底変数；最大化したい式に含まれる変数. 制約の範囲で自由に動かす. 各ステップ開始時に値が0になっている。]
tuple<bool, double, vector<double>> simplex_leq(Mat A, Vector b, Vector c) {
tuple<bool, double, vector<double>> error_value = tuple<bool, double, vector<double>>(false, 0, vector<double>());
vector<int> ids; //ids[i] = i(>=0)行目の基底変数はx[ids[i]]. 0行目は目的変数Zなので, ids[0] = -1とする.
Mat table; //table : シンプレックス表, table[i] = i=0:目的変数Zの制約式, i>=1:制約式
//table[i][j] = i個目の制約式(等式の左辺)における、変数x[j]の係数.
Vector con; //con[i] = i個目の制約式の定数項. i=0のときは目的変数Zの制約式の定数項 (現在の値).
//理論上, x = 0が条件を満たす場合, con[i] >= 0は常に満たされる.
int w = c.size() + A.size(); //変数x[0]～x[c.size()-1] + スラック変数：x[c.size()]～, 全て非負
int h = 1 + A.size(); //目的関数がある分、制約式 + 1行にしておく。
int i, j;
ids.resize(h);
ids[0] = -1;
rep(i, A.size()) ids[i + 1] = c.size() + i; //最初は, スラック変数が基底変数
table.resize(h);
rep(i, h) table[i].resize(w);
rep(j, w) {
if (j < c.size()) table[0][j] = -c[j];
else table[0][j] = 0;
}
rep(i, A.size()) {
rep(j, w) {
if (j < A[i].size()) table[i + 1][j] = A[i][j];
else if (j == A[i].size() + i) table[i + 1][j] = 1;
else table[i + 1][j] = 0;
}
}
con.resize(h + 1);
con[0] = 0;
rep(i, b.size()) con[i + 1] = b[i];
//では解いていきましょう
while (true) {
//print_simplex_state(ids, table, con);
//STEP1. table[0] (目的関数の係数) の中から最小な係数がある列qを求める
int q = 0;
rep(j, w) {
if (table[0][q] > table[0][j]) {
q = j;
}
}
//STEP2. table[0]の係数が全て非負になったら終了. 目的関数の値はこれ以上増加しないため.
if (table[0][q] >= 0) {
break;
}
//STEP3. table[i][q] > 0になる行i=1,2,…,h-1の中から、
//con[i] / table[i][q]が最小となる行pを探す. (変数x[q]をいくつ増やせるか）
//そのようなpが存在しなければ、最適値が存在しない（いくらでも大きくできてしまう）
int p = -1;
double min_t;
for (i = 1; i < h; i++) {
if (table[i][q] <= 0) continue;
double t = con[i] / table[i][q];
if (p == -1 || min_t > t) {
min_t = t;
p = i;
}
}
if (p == -1) { return error_value; }
//STEP4. p行q列をピポットにして掃き出し法をおこなう.
//基底変数の交換 -> 代入に相当する操作.
double c0 = table[p][q];
rep(j, w) table[p][j] /= c0;
con[p] /= c0;
rep(i, h) {
if (i == p) continue;
double c1 = -table[i][q];
rep(j, w) {
table[i][j] += c1 * table[p][j];
}
con[i] += c1 * con[p];
}
ids[p] = q;
}
//解を返す
double max_z = con[0];
vector<double> x(c.size(), 0);
for (i = 1; i < h; i++) {
if (0 <= ids[i] && ids[i] < c.size()) {
x[ids[i]] = con[i];
}
}
return tuple<bool, double, vector<double>>(true, max_z, x);
}
int main() {
int i, j;
int a[5];
cin >> a[0] >> a[1] >> a[2] >> a[3] >> a[4];
Vector c, b;
Mat A;
c.resize(5);
rep(i, 5) c[i] = 1;
A.resize(5);
b.resize(5);
rep(i, 5) {
A[i].resize(5);
rep(j, 3) { A[i][(i + j) % 5] = 1; }
A[i][(i + 3) % 5] = 0;
A[i][(i + 4) % 5] = 0;
b[i] = a[(i + 2) % 5];
}
tuple<bool, double, vector<double>> ans = simplex_leq(A, b, c);
bool isSucceed = get<0>(ans);
double max_z = get<1>(ans);
vector<double> x = get<2>(ans);
if (isSucceed) {
cout << (int)max_z << endl;
/*cout << "z = " << max_z << endl;
rep(i, x.size()) {
cout << "x_" << i << " = " << x[i] << endl;
}*/
}
else {
assert(0);
//cout << "Fail" << endl;
}
return 0;
}