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

提出ソース

結果

問題	No.1122 Plane Tickets
ユーザー	square1001
提出日時	2020-07-03 18:22:37
言語	C++14 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	14 ms / 1,000 ms
コード長	10,240 bytes
コンパイル時間	1,445 ms
コンパイル使用メモリ	91,724 KB
実行使用メモリ	4,380 KB
最終ジャッジ日時	2023-09-05 22:13:31
合計ジャッジ時間	3,563 ms
ジャッジサーバーID （参考情報）	judge13 / judge15

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

テストケース

テストケース表示

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

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

ソースコード

raw source code

#ifndef CLASS_MATRIX
#define CLASS_MATRIX

#include <vector>
#include <cassert>
#include <cstddef>
#include <cstdint>
#include <utility>

template<class type>
class matrix {
private:
	std::size_t R, C;
	std::vector<type> val;
public:
	matrix() : R(0), C(0), val(std::vector<type>()) {};
	matrix(std::size_t R_, std::size_t C_) : R(R_), C(C_), val(std::vector<type>(R* C)) {}
	matrix(std::size_t N_) : R(N_), C(N_), val(std::vector<type>(N_* N_)) {}
	type& entry(std::size_t r, std::size_t c) { return val[r * C + c]; }
	type entry(std::size_t r, std::size_t c) const { return val[r * C + c]; }
	static const matrix unit(std::size_t N) {
		matrix ret(N);
		for (std::size_t i = 0; i < N; ++i) {
			ret.entry(i, i) = type(1);
		}
		return ret;
	}
	matrix transpose() const {
		matrix ret(C, R);
		for (std::size_t i = 0; i < R; ++i) {
			for (std::size_t j = 0; j < C; ++j) {
				ret.val[j * R + i] = val[i * C + j];
			}
		}
		return ret;
	}
	bool operator==(const matrix& mat) const {
		if (R != mat.R || C != mat.C) return false;
		for (std::size_t i = 0; i < R * C; ++i) {
			if (val[i] != mat.val[i]) return false;
		}
		return true;
	}
	bool operator!=(const matrix& mat) const {
		if (R != mat.R || C != mat.C) return true;
		for (std::size_t i = 0; i < R * C; ++i) {
			if (val[i] != mat.val[i]) return true;
		}
		return false;
	}
	matrix& operator+=(const matrix& mat) {
		assert(R == mat.R && C == mat.C);
		for (std::size_t i = 0; i < R * C; ++i) val[i] += mat.val[i];
		return *this;
	}
	matrix& operator-=(const matrix& mat) {
		assert(R == mat.R && C == mat.C);
		for (std::size_t i = 0; i < R * C; ++i) val[i] -= mat.val[i];
		return *this;
	}
	matrix& operator*=(const matrix& mat) {
		assert(C == mat.R);
		matrix tmat = mat.transpose();
		std::vector<type> tmp(R * tmat.R);
		for (std::size_t i = 0; i < R; ++i) {
			for (std::size_t j = 0; j < tmat.R; ++j) {
				for (std::size_t k = 0; k < C; ++k) {
					tmp[i * tmat.R + j] += val[i * C + k] * tmat.val[j * tmat.C + k];
				}
			}
		}
		C = tmat.R;
		val = tmp;
		return *this;
	}
	matrix operator+=(const type& x) {
		for (std::size_t i = 0; i < R * C; ++i) val[i] += x;
		return *this;
	}
	matrix operator-=(const type& x) {
		for (std::size_t i = 0; i < R * C; ++i) val[i] -= x;
		return *this;
	}
	matrix operator*=(const type& x) {
		for (std::size_t i = 0; i < R * C; ++i) val[i] *= x;
		return *this;
	}
	matrix operator+(const matrix& mat) const { return matrix(*this) += mat; }
	matrix operator-(const matrix& mat) const { return matrix(*this) -= mat; }
	matrix operator*(const matrix& mat) const { return matrix(*this) *= mat; }
	matrix operator+(const type& x) const { return matrix(*this) += x; }
	matrix operator-(const type& x) const { return matrix(*this) -= x; }
	matrix operator*(const type& x) const { return matrix(*this) *= x; }
	matrix pow(std::uint64_t b) const {
		assert(R == C);
		matrix ans = unit(R), cur(*this);
		while (b != 0) {
			if (b & 1) ans *= cur;
			cur *= cur;
			b >>= 1;
		}
		return ans;
	}
	std::pair<matrix, matrix> gaussian_elimination(const matrix& mat) const {
		assert(R == mat.R);
		matrix lmat(*this), rmat(mat);
		std::size_t curpos = 0;
		for (std::size_t i = 0; i < R; ++i) {
			while (curpos < C) {
				std::size_t pos = std::size_t(-1);
				for (std::size_t j = i; j < R; ++j) {
					if (lmat.val[j * C + curpos] != type(0)) {
						pos = j;
						if (j != i) {
							for (std::size_t k = 0; k < C; ++k) std::swap(lmat.val[i * C + k], lmat.val[j * C + k]);
							for (std::size_t k = 0; k < rmat.C; ++k) std::swap(rmat.val[i * rmat.C + k], rmat.val[j * rmat.C + k]);
						}
						break;
					}
				}
				if (pos != std::size_t(-1)) {
					type mult = type(1) / lmat.val[i * C + curpos];
					for (std::size_t j = 0; j < C; ++j) lmat.val[i * C + j] *= mult;
					for (std::size_t j = 0; j < rmat.C; ++j) rmat.val[i * rmat.C + j] *= mult;
					lmat.val[i * C + curpos] = type(1);
					for (std::size_t j = 0; j < R; ++j) {
						if (j == i || lmat.val[j * C + curpos] == type(0)) continue;
						type submult = lmat.val[j * C + curpos];
						for (std::size_t k = 0; k < C; ++k) lmat.val[j * C + k] -= lmat.val[i * C + k] * submult;
						for (std::size_t k = 0; k < rmat.C; ++k) rmat.val[j * rmat.C + k] -= rmat.val[i * rmat.C + k] * submult;
						lmat.val[j * C + curpos] = type(0);
					}
					break;
				}
				++curpos;
			}
			if (curpos == C) break;
		}
		return std::make_pair(lmat, rmat);
	}
	matrix inverse() const {
		assert(R == C);
		std::pair<matrix, matrix> res = gaussian_elimination(unit(R));
		if (res.first != unit(R)) return matrix();
		return res.second;
	}
	type determinant() const {
		assert(R == C);
		matrix mat(*this);
		type ans = type(1);
		for (std::size_t i = 0; i < R; ++i) {
			std::size_t pos = std::size_t(-1);
			for (std::size_t j = i; j < R; ++j) {
				if (mat.val[j * C + i] != type(0)) {
					pos = j;
					break;
				}
			}
			if (pos == std::size_t(-1)) return type(0);
			if (pos != i) {
				ans *= type(-1);
				for (std::size_t j = i; j < C; ++j) {
					std::swap(mat.val[i * C + j], mat.val[pos * C + j]);
				}
			}
			ans *= mat.val[i * C + i];
			for (std::size_t j = i + 1; j < R; ++j) {
				type mul = mat.val[j * C + i] / mat.val[i * C + i];
				for (std::size_t k = i + 1; k < C; ++k) {
					mat.val[j * C + k] -= mat.val[i * C + k] * mul;
				}
			}
		}
		return ans;
	}
};

#endif // CLASS_MATRIX

long long gcd(long long x, long long y) {
	if (y == 0) return x;
	return gcd(y, x % y);
}
long long lcm(long long x, long long y) {
	return x / gcd(x, y) * y;
}
struct fraction {
public:
	long long a, b;
	explicit fraction() : a(0), b(1) {};
	explicit fraction(long long a_) : a(a_), b(1) {};
	explicit fraction(long long a_, long long b_) {
		if (b_ < 0) a_ *= -1, b_ *= -1;
		long long g = gcd((a_ > 0 ? a_ : -a_), b_);
		a = a_ / b;
		b = b_ / b;
	};
	bool operator==(const fraction& f) { return a == f.a && b == f.b; }
	bool operator!=(const fraction& f) { return a != f.a || b != f.b; }
	fraction& operator+=(const fraction& f) {
		long long ca = 1LL * a * f.b + 1LL * b * f.a;
		long long cb = 1LL * b * f.b;
		long long g = gcd((ca > 0 ? ca : -ca), cb);
		a = ca / g;
		b = cb / g;
		return *this;
	}
	fraction& operator-=(const fraction& f) {
		long long ca = 1LL * a * f.b - 1LL * b * f.a;
		long long cb = 1LL * b * f.b;
		long long g = gcd((ca > 0 ? ca : -ca), cb);
		a = ca / g;
		b = cb / g;
		return *this;
	}
	fraction& operator*=(const fraction& f) {
		long long ca = 1LL * a * f.a, cb = 1LL * b * f.b;
		long long g = gcd((ca > 0 ? ca : -ca), cb);
		a = ca / g;
		b = cb / g;
		return *this;
	}
	fraction& operator/=(const fraction& f) {
		long long ca = 1LL * a * f.b, cb = 1LL * b * f.a;
		if (cb < 0) ca *= -1, cb *= -1;
		long long g = gcd((ca > 0 ? ca : -ca), cb);
		a = ca / g;
		b = cb / g;
		return *this;
	}
	fraction operator+(const fraction& f) const { return fraction(*this) += f; }
	fraction operator-(const fraction& f) const { return fraction(*this) -= f; }
	fraction operator*(const fraction& f) const { return fraction(*this) *= f; }
	fraction operator/(const fraction& f) const { return fraction(*this) /= f; }
	bool operator==(const fraction& f) const { return a == f.a && b == f.b; }
	bool operator!=(const fraction& f) const { return a != f.a || b != f.b; }
	bool operator<(const fraction& f) const { return (fraction(*this) - f).a < 0; }
	bool operator>(const fraction& f) const { return (fraction(*this) - f).a > 0; }
	bool operator<=(const fraction& f) const { return (fraction(*this) - f).a <= 0; }
	bool operator>=(const fraction& f) const { return (fraction(*this) - f).a >= 0; }
};

#include <string>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
int main() {
	vector<long long> A(5);
	cin >> A[0] >> A[1] >> A[2] >> A[3] >> A[4];
	vector<vector<int> > base_mat = {
		{ 1, 0, 0, 1, 1 },
		{ 1, 1, 0, 0, 1 },
		{ 1, 1, 1, 0, 0 },
		{ 0, 1, 1, 1, 0 },
		{ 0, 0, 1, 1, 1 },
	};
	long long ans = 0;
	for (int i = 0; i < 1024; ++i) {
		int pcnt = 0;
		vector<int> sela, selb, selc;
		for (int j = 0; j < 10; ++j) {
			if ((i >> j) & 1) {
				++pcnt;
				if (j < 5) sela.push_back(j);
				else selb.push_back(j - 5);
			}
			else if (j < 5) {
				selc.push_back(j);
			}
		}
		if (pcnt != 5 || selb.size() == 0) continue;
		// 0 <= id <= 4: constraint x[id] = 0
		// 5 <= id <= 9: constraint sum(base_mat[id-5][i] * x[i]) = A[id - 5]
		int S = selb.size();
		matrix<fraction> mat(S);
		for (int j = 0; j < S; ++j) {
			for (int k = 0; k < S; ++k) {
				mat.entry(j, k) = fraction(base_mat[selb[j]][selc[k]]);
			}
		}
		matrix<fraction> imat = mat.inverse();
		if (imat == matrix<fraction>()) continue;
		int denom = 1;
		for (int j = 0; j < S; ++j) {
			for (int k = 0; k < S; ++k) {
				denom = lcm(denom, imat.entry(j, k).b);
			}
		}
		int max_improve = (denom - 1) * S;
		for (int j = 0; j <= max_improve; ++j) {
			string seq = string(j, 'o') + string(4, '|');
			do {
				vector<int> dec;
				int cont = 0;
				for (int k = 0; k <= seq.size(); ++k) {
					if (k == seq.size() || seq[k] == '|') {
						dec.push_back(cont);
						cont = 0;
					}
					else {
						++cont;
					}
				}
				bool valid = true;
				for (int k = 0; k < 5; ++k) {
					if (dec[k] > A[k]) {
						valid = false;
					}
				}
				if (!valid) continue;
				vector<fraction> val(S);
				for (int k = 0; k < S; ++k) {
					for (int l = 0; l < S; ++l) {
						val[k] += imat.entry(k, l) * fraction(A[selb[l]] - dec[selb[l]]);
					}
				}
				bool correct = true;
				for (int k = 0; k < S; ++k) {
					if (val[k] < fraction(0) || val[k].b != 1) {
						correct = false;
					}
				}
				if (!correct) continue;
				vector<long long> true_val(5);
				for (int k = 0; k < S; ++k) {
					true_val[selc[k]] = val[k].a;
				}
				bool fully_correct = true;
				for (int k = 0; k < 5; ++k) {
					long long sum = 0;
					for (int l = 0; l < 5; ++l) {
						sum += base_mat[k][l] * true_val[l];
					}
					if (sum > A[k]) {
						fully_correct = false;
					}
				}
				if (fully_correct) {
					long long score = 0;
					for (int k = 0; k < S; ++k) {
						score += val[k].a;
					}
					ans = max(ans, score);
				}
			} while (next_permutation(seq.begin(), seq.end()));
		}
	}
	cout << ans << endl;
	return 0;
}

yukicoder

結果

テストケース

ソースコード