#516426 (C++14) No.1122 Plane Tickets

提出ソース

結果

問題	No.1122 Plane Tickets
ユーザー	startcpp
提出日時	2020-07-22 22:27:36
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	WA
実行時間	-
コード長	7,180 bytes
コンパイル時間	1,134 ms
コンパイル使用メモリ	89,840 KB
実行使用メモリ	4,508 KB
最終ジャッジ日時	2023-09-04 21:37:59
合計ジャッジ時間	3,010 ms
ジャッジサーバーID （参考情報）	judge11 / judge14

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 4,380 KB
testcase_01	AC	2 ms 4,380 KB
testcase_02	AC	1 ms 4,380 KB
testcase_03	AC	1 ms 4,376 KB
testcase_04	AC	1 ms 4,376 KB
testcase_05	AC	2 ms 4,376 KB
testcase_06	AC	1 ms 4,376 KB
testcase_07	AC	1 ms 4,380 KB
testcase_08	WA	-
testcase_09	WA	-
testcase_10	WA	-
testcase_11	WA	-
testcase_12	WA	-
testcase_13	WA	-
testcase_14	WA	-
testcase_15	WA	-
testcase_16	WA	-
testcase_17	WA	-
testcase_18	WA	-
testcase_19	WA	-
testcase_20	WA	-
testcase_21	WA	-
testcase_22	WA	-
testcase_23	WA	-
testcase_24	WA	-
testcase_25	WA	-
testcase_26	WA	-
testcase_27	WA	-
testcase_28	WA	-
testcase_29	WA	-
testcase_30	WA	-
testcase_31	WA	-
testcase_32	WA	-
testcase_33	WA	-
testcase_34	WA	-
testcase_35	WA	-
testcase_36	WA	-
testcase_37	WA	-
testcase_38	WA	-
testcase_39	WA	-
testcase_40	AC	1 ms 4,376 KB
testcase_41	WA	-
testcase_42	WA	-
testcase_43	AC	1 ms 4,384 KB
testcase_44	AC	2 ms 4,380 KB
testcase_45	AC	1 ms 4,376 KB
testcase_46	AC	1 ms 4,376 KB
testcase_47	WA	-
testcase_48	AC	1 ms 4,376 KB
testcase_49	WA	-
testcase_50	AC	1 ms 4,380 KB
testcase_51	WA	-
testcase_52	WA	-
testcase_53	WA	-
testcase_54	WA	-
testcase_55	WA	-
testcase_56	WA	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

//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;
}

yukicoder

結果

テストケース

ソースコード