#1197539 (C++23) No.2035 Tunnel

提出ソース
結果

問題	No.2035 Tunnel
コンテスト
ユーザー	ecottea
提出日時	2026-11-07 00:25:05
言語	C++23 (gcc 15.3.0 + boost 1.92.0 + ACL) コンパイル: `g++-15 -O2 -fplugin=/usr/lib/yukicoder/noavx512-gcc15.so -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_` 実行: `./a.out`
結果	AC
実行時間	10 ms / 2,000 ms
	+ 340µs
コード長	12,560 bytes
記録記録タグの例: 初AC ショートコード純ショートコード純主流ショートコード最速実行時間
コンパイル時間	5,646 ms
コンパイル使用メモリ	377,432 KB
実行使用メモリ	9,924 KB
最終ジャッジ日時	2026-11-07 00:25:14
合計ジャッジ時間	7,530 ms
ジャッジサーバーID （参考情報）	judge3_0 / judge7_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 3
other	AC * 28
権限があれば一括ダウンロードができます
ソースコード

raw source code
// 最適化DP（max-plus）自動生成：愚直解から (max,+) 線形表現 u ⊗ A_{S1} ⊗ ... ⊗ A_{SN} ⊗ v を復元する
#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int INF = 1001001001; ll INFL = 4004004003094073385LL; // (int)INFL = INF, (int)(-INFL) = -INF;

#define rep(i, n) for (int i = 0, i##_len = int(n); i < i##_len; ++i)
#define repi(i, s, t) for(int i = int(s), i##_end = int(t); i <= i##_end; ++i) // s から t まで昇順
#define repb(set, d) for(int set = 0, set##_ub = 1 << int(d); set < set##_ub; ++set) // d ビット全探索（昇順）
#define sz(x) ((int)(x).size())

template <class T> inline bool chmax(T & M, const T & x) { if (M < x) { M = x; return true; } return false; } // 最大値を更新（更新されたら true を返す）
template <class T> inline bool chmin(T & m, const T & x) { if (m > x) { m = x; return true; } return false; } // 最小値を更新（更新されたら true を返す）template <class T> inline int getb(T set, int i) { return (set >> i) & T(1); }
template <class T> inline int getb(T set, int i) { return (set >> i) & T(1); }

const ll NEG = LLONG_MIN / 4;                                   // -∞
inline ll addn(ll a, ll b) { return (a <= NEG || b <= NEG) ? NEG : a + b; } // (max,+) の積
inline ll fmtn(ll x) { return x; }

//====================== ここを書き換える：愚直解（最大化．不可能なら NEG を返す） ======================
// 文字は '0','1',... ．最小化したい問題は「値の符号を反転して」返す（最後に符号を戻す）．
#ifndef NAIVE_ID
#define NAIVE_ID 0
#endif
#if NAIVE_ID == 0
ll naive(string s) {
	int n = sz(s);

	int res = 0;

	while (1) {
		string t(n, '0');
		bool end = true;

		rep(i, n) {
			if (s[i] == '1') {
				if (i == n - 1) {
					;
				}
				else {
					if (s[i + 1] == '0') {
						t[i + 1] = '1';
					}
					else {
						t[i] = '1';
					}
				}
				end = false;
			}
		}
		s = move(t);

		if (end) break;

		res++;
	}

	return res;
}
#elif NAIVE_ID == 1
// 最大部分配列和（空可）．'0'→-1, '1'→+1, '2'→-2... 重みは w[c]
const ll WT[3] = { -1, 1, 0 }; // 文字 0,1,2 の重み
ll naive(const string& s) {
	ll best = 0; int n = sz(s);
	rep(i, n) { ll sum = 0; for (int j = i; j < n; j++) { sum += WT[s[j] - '0']; best = max(best, sum); } }
	return best;
}
#elif NAIVE_ID == 2
// 隣り合う位置は同時に選べない．選んだ位置の価値 val[c] の総和の最大化（全探索 2^n）
const ll VAL[2] = { 3, -1 };
ll naive(const string& s) {
	int n = sz(s); ll best = 0;
	rep(mask, 1 << n) {
		if (mask & (mask >> 1)) continue;
		ll sum = 0; rep(i, n) if (mask >> i & 1) sum += VAL[s[i] - '0'];
		best = max(best, sum);
	}
	return best;
}
#elif NAIVE_ID == 3
// T との LCS（T = "0110"）
ll naive(const string& s) {
	const string T = "0110"; int n = sz(s), m = sz(T);
	vector<vector<ll>> dp(n + 1, vector<ll>(m + 1, 0));
	rep(i, n) rep(j, m) dp[i + 1][j + 1] = max({ dp[i][j + 1], dp[i + 1][j], dp[i][j] + (s[i] == T[j]) });
	return dp[n][m];
}
#elif NAIVE_ID == 4
// 選んだ部分列の中で同じ文字が3連続しないように部分列を選び，価値 val[c] の総和を最大化（全探索 2^n）
const ll VAL[2] = { 2, 1 };
ll naive(const string& s) {
	int n = sz(s); ll best = 0;
	rep(mask, 1 << n) {
		string t; ll sum = 0;
		rep(i, n) if (mask >> i & 1) { t += s[i]; sum += VAL[s[i] - '0']; }
		bool ok = true; rep(i, sz(t) - 2) if (t[i] == t[i + 1] && t[i + 1] == t[i + 2]) ok = false;
		if (ok) best = max(best, sum);
	}
	return best;
}
#endif
//==============================================================================================

unordered_map<string, ll> memo;
ll H(const string& s) { auto it = memo.find(s); if (it != memo.end()) return it->second; return memo[s] = naive(s); }

using Row = vector<ll>;

// r が G の (max,+) 線形結合で書けるか判定する．留数（principal solution）λ_k = min_z (r[z] - G_k[z]) を求め，
// max_k(λ_k + G_k) == r なら成功．skip 番目の生成元は使わない．
bool residuate(const Row& r, const vector<Row>& G, int skip, vector<ll>& lam) {
	int K = sz(G), m = sz(r);
	lam.assign(K, NEG);
	Row rec(m, NEG);
	rep(k, K) {
		if (k == skip) continue;
		ll mn = LLONG_MAX;
		rep(z, m) if (G[k][z] > NEG) mn = min(mn, r[z] <= NEG ? NEG : r[z] - G[k][z]);
		if (mn == LLONG_MAX) continue;
		lam[k] = mn;
		rep(z, m) rec[z] = max(rec[z], addn(lam[k], G[k][z]));
	}
	return rec == r;
}

// 行の有限成分すべてから t を引く（-∞ はそのまま）
Row shifted(Row r, ll t) { for (auto& x : r) if (x > NEG) x -= t; return r; }

// principal solution は窓の外では過大になりうる（最大の解だから）．表現に不要な係数を -∞ に落として疎にする．
void prune(vector<ll>& lam, const Row& r, const vector<Row>& G) {
	int K = sz(G), m = sz(r);
	vector<int> ord; rep(k, K) if (lam[k] > NEG) ord.push_back(k);
	auto wit = [&](int k) { int w = 0; rep(z, m) if (G[k][z] > NEG && addn(lam[k], G[k][z]) == r[z]) w++; return w; };
	vector<int> w(K, 0); for (int k : ord) w[k] = wit(k);
	sort(ord.begin(), ord.end(), [&](int a, int b) { return w[a] < w[b]; }); // 根拠の少ない係数から落としてみる
	for (int k : ord) {
		ll keep = lam[k]; lam[k] = NEG;
		Row rec(m, NEG);
		rep(j, K) if (lam[j] > NEG) rep(z, m) rec[z] = max(rec[z], addn(lam[j], G[j][z]));
		if (rec != r) lam[k] = keep;
	}
}

struct MaxPlusAutoDP {
	int COL;
	vector<string> Z, gs; // 列（接尾辞）の集合，生成元に対応する文字列
	vector<vector<string>> mem; // 生成元と（窓上で）同じ正規化行をもつ文字列の集まり
	vector<Row> G;        // 生成元（行）
	int K = 0;
	vector<vector<vector<ll>>> A; // A[c][i][j]
	vector<ll> u;

	MaxPlusAutoDP(int COL) : COL(COL) {}

	static vector<string> strs(int COL, int len) {
		vector<string> res{ "" };
		int b = 0;
		rep(l, len) { int e = sz(res); for (int i = b; i < e; i++) rep(c, COL) res.push_back(res[i] + char('0' + c)); b = e; }
		return res;
	}
	Row row_of(const string& x) { Row r(sz(Z)); rep(j, sz(Z)) r[j] = H(x + Z[j]); return r; }

	// 候補行を追加（生成系の更新）．冗長になった旧生成元は取り除く．
	void add(const string& x) {
		Row r = row_of(x); vector<ll> lam;
		if (r[0] > NEG) r = shifted(r, r[0]); // 生成元は g(ε)=0 に正規化：g(z) = naive(x+z) - naive(x)
		// 窓上で同じ行（定数差を除く）の生成元が既にあれば，より「飽和した」（長い）文字列を代表にする
		rep(i, sz(G)) if (G[i] == r) { mem[i].push_back(x); if (sz(x) > sz(gs[i]) || (sz(x) == sz(gs[i]) && H(x) > H(gs[i]))) gs[i] = x; return; }
		if (residuate(r, G, -1, lam)) return;
		G.push_back(r); gs.push_back(x); mem.push_back({ x });
		for (int i = sz(G) - 2; i >= 0; i--) if (residuate(G[i], G, i, lam)) { G.erase(G.begin() + i); gs.erase(gs.begin() + i); mem.erase(mem.begin() + i); }
	}

	ll eval(const string& s) const {
		vector<ll> dp = u, nd(K);
		for (char ch : s) {
			int c = ch - '0';
			fill(nd.begin(), nd.end(), NEG);
			rep(i, K) if (dp[i] > NEG) rep(j, K) nd[j] = max(nd[j], addn(dp[i], A[c][i][j]));
			dp.swap(nd);
		}
		ll res = NEG; rep(i, K) res = max(res, dp[i]);
		return res;
	}

	// LZ: 接尾辞の最大長，LX: 候補接頭辞の最大長，LV: 検証する文字列の最大長
	bool build(int LZ, int LX, int LV, int Kmax) {
		Z = strs(COL, LZ); G.clear(); gs.clear(); mem.clear();
		for (auto& x : strs(COL, LX)) add(x);
		// 閉包：各生成元 g と文字 c について g·c の行が生成系で表せるまで繰り返す
		for (;;) {
			bool changed = false;
			for (int i = 0; i < sz(G) && !changed; i++) rep(c, COL) {
				vector<ll> lam;
				string y = gs[i] + char('0' + c);
				if (!residuate(shifted(row_of(y), H(gs[i])), G, -1, lam)) { add(y); changed = true; break; }
			}
			if (sz(G) > Kmax) return false;
			if (!changed) break;
		}
		K = sz(G);
		A.assign(COL, vector<vector<ll>>(K, vector<ll>(K, NEG)));
		// 生成元ごとに，同じ行をもつ文字列のうち遷移が最も疎になる代表を選ぶ（飽和が足りない代表は窓の端で偽の係数を生む）
		rep(i, K) {
			int bestCnt = INT_MAX; vector<vector<ll>> bestA;
			vector<string> cand = mem[i]; cand.push_back(gs[i]);
			sort(cand.begin(), cand.end()); cand.erase(unique(cand.begin(), cand.end()), cand.end());
			for (auto& sc : cand) {
				vector<vector<ll>> cur(COL); int cnt = 0; bool ok = true;
				rep(c, COL) {
					vector<ll> lam; Row t = shifted(row_of(sc + char('0' + c)), H(sc));
					if (!residuate(t, G, -1, lam)) { ok = false; break; }
					prune(lam, t, G); cur[c] = lam; for (ll x : lam) cnt += x > NEG;
				}
				if (ok && cnt < bestCnt) { bestCnt = cnt; bestA = cur; }
			}
			if (bestCnt == INT_MAX) return false;
			rep(c, COL) A[c][i] = bestA[c];
		}
		{ vector<ll> lam; Row t = row_of(""); residuate(t, G, -1, lam); prune(lam, t, G); u = lam; }
		// 正規化により g_i(ε)=0 なので，答えは max_i dp[i] になる（v は不要）
		// 検証
		for (auto& s : strs(COL, LV)) if (eval(s) != H(s)) return false;
		return true;
	}

	void print_code() const {
		auto f = [](ll x) { return x <= NEG ? string("NEG") : to_string(x); };
		printf("constexpr int DIM = %d;\nconstexpr int COL = %d;\n", K, COL);
		printf("const ll matAs[COL][DIM][DIM] = {\n");
		rep(c, COL) {
			printf("{");
			rep(i, K) { printf("{"); rep(j, K) printf("%s%s", f(A[c][i][j]).c_str(), j + 1 < K ? "," : ""); printf("}%s", i + 1 < K ? "," : ""); }
			printf("}%s\n", c + 1 < COL ? "," : "");
		}
		printf("};\nconst ll vecU[DIM] = {");
		rep(i, K) printf("%s%s", f(u[i]).c_str(), i + 1 < K ? "," : "");
		printf("};\n");
	}
};

void embed_coefs_maxplus(int COL, int wmax = 1, int LZmax = 6, int LV = 10, int Kmax = 40) {
	MaxPlusAutoDP dp(COL);
	for (int LZ = 1; LZ <= LZmax; LZ++) {
		int LX = 2 * (LZ + 1) * wmax + 1;
		bool ok = dp.build(LZ, LX, LV, Kmax);
		fprintf(stderr, "LZ=%d LX=%d K=%d %s\n", LZ, LX, dp.K, ok ? "OK" : "NG");
		if (ok) { dp.print_code(); return; }
	}
	fprintf(stderr, "failed: increase LZmax/wmax or the function is not representable\n");
}

// ---------- 提出側のテンプレ：embed_coefs_maxplus の出力を貼って使う ----------
template <class T = long long>
T solve(const string& s) {
	const long long NEG = LLONG_MIN / 4;
	// --- 出力を貼る ---
	constexpr int DIM = 3;
	constexpr int COL = 2;
	const ll matAs[COL][DIM][DIM] = {
	{{0,NEG,NEG},{1,NEG,1},{NEG,NEG,1}},
	{{NEG,1,NEG},{NEG,2,NEG},{NEG,NEG,1}}
	};
	const ll vecU[DIM] = { 0,NEG,NEG };
	// ------------------
	array<long long, DIM> dp;
	rep(i, DIM) dp[i] = vecU[i];
	for (char ch : s) {
		int c = ch - '0';
		array<long long, DIM> nd; nd.fill(NEG);
		rep(i, DIM) if (dp[i] > NEG) rep(j, DIM) if (matAs[c][i][j] > NEG) nd[j] = max(nd[j], dp[i] + matAs[c][i][j]);
		dp = nd;
	}
	long long res = NEG; rep(i, DIM) res = max(res, dp[i]);
	return res; // 最小化問題で符号を反転して学習したなら -res を返す
}
// ---------------------------------------------------------------------- 

int main(int argc, char** argv) {
	int COL = 2;
	//int wmax = NAIVE_ID == 1 ? 1 : (NAIVE_ID == 2 ? 3 : 1);
	int wmax = 1;
//	embed_coefs_maxplus(COL, wmax); return 0;

	int n; string s;
	cin >> n >> s;

	rep(i, sz(s)) {
		if (s[i] == '.') s[i] = '0';
		else if (s[i] == '#') s[i] = '1';
	}

	cout << solve<ll>(s) << endl;
}
/*
引数	既定値	意味
COL	なし（必須）	文字種の数です。文字は '0'〜'0'+COL-1 で表し、愚直解 naive もこの文字で受け取ります。
wmax	1	1文字が答えを変えうる量（重みの絶対値）の最大の見積もりです。候補接頭辞の最大長を LX = 2*(LZ+1)*wmax+1 と決めるのに使います。小さすぎると生成元が飽和せず検証に失敗し、大きすぎると COL^LX 通りの候補で重くなります。
LZmax	6	接尾辞（列）の最大長 LZ を 1 から LZmax まで増やして試します。検証を通った最初の LZ で打ち切り、最後まで通らなければ失敗を報告します。
LV	10	検証する文字列の最大長です。長さ LV 以下の全文字列で、生成したDPと愚直解を照合します。COL^LV 通りなので、COL が大きいときは下げます。
Kmax	40	生成元の数（DPの次元）の上限です。超えたらその LZ は失敗とみなして次へ進みます。状態が非有界な関数では、これが増え続けて失敗の合図になります。
*/
yukicoder

結果

ソースコード
