結果
| 問題 |
No.2332 Make a Sequence
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:06:50 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 10,590 bytes |
| コンパイル時間 | 2,742 ms |
| コンパイル使用メモリ | 128,840 KB |
| 実行使用メモリ | 76,696 KB |
| 最終ジャッジ日時 | 2025-05-14 13:08:53 |
| 合計ジャッジ時間 | 31,610 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 WA * 1 |
| other | WA * 45 TLE * 1 -- * 15 |
ソースコード
#include <iostream>
#include <vector>
#include <string>
#include <numeric>
#include <algorithm>
#include <map>
#include <queue>
#include <limits>
#include <vector>
// Try to include AtCoder library string header for suffix array utilities.
// If building locally without AtCoder library, provide basic placeholders.
#if __has_include(<atcoder/string>)
#include <atcoder/string>
#else
// Provide placeholder implementations if AtCoder library is not available.
// Warning: These placeholders might be too slow or incorrect for competitive programming.
#warning "AtCoder String Library not found, using basic placeholder implementations. This might TLE or WA."
namespace atcoder {
// Basic O(N^2 logN) Suffix Array - Too slow for constraints
std::vector<int> suffix_array(const std::vector<int>& s) {
int n = s.size();
std::vector<int> sa(n);
std::iota(sa.begin(), sa.end(), 0);
std::sort(sa.begin(), sa.end(), [&](int i, int j) {
int k = 0;
while (i + k < n && j + k < n) {
if (s[i + k] != s[j + k]) return s[i + k] < s[j + k];
k++;
}
return i + k == n; // If i suffix is prefix of j suffix, i comes first
});
return sa;
}
// Basic O(N^2) LCP Array - Too slow
std::vector<int> lcp_array(const std::vector<int>& s, const std::vector<int>& sa) {
int n = s.size();
if (n == 0) return {};
std::vector<int> rank(n);
for (int i = 0; i < n; ++i) rank[sa[i]] = i;
std::vector<int> lcp(n); // acl returns size n, lcp[0]=0
int h = 0;
for (int i = 0; i < n; ++i) {
if (rank[i] > 0) {
int j = sa[rank[i] - 1]; // previous suffix in sorted order
// Compute LCP between suffix i and suffix j
while (i + h < n && j + h < n && s[i + h] == s[j + h]) {
h++;
}
lcp[rank[i]] = h;
if (h > 0) h--; // Kasai's algorithm optimization
}
}
return lcp;
}
} // namespace atcoder
#endif
// RMQ structure using Sparse Table for O(1) minimum queries on LCP array.
template <typename T>
struct SparseTable {
std::vector<std::vector<T>> st; // Sparse table storage
std::vector<int> log_table; // Precomputed logarithms base 2
T identity; // Identity element for the query operation (minimum -> infinity)
SparseTable() {} // Default constructor
// Constructor builds the sparse table from a vector v.
SparseTable(const std::vector<T>& v, T id) : identity(id) {
int n = v.size();
if (n == 0) return; // Handle empty vector case
// Precompute logs base 2
log_table.assign(n + 1, 0);
for (int i = 2; i <= n; ++i) log_table[i] = log_table[i / 2] + 1;
int max_log = (n == 0) ? 0 : log_table[n]; // Max power of 2 needed
st.assign(n, std::vector<T>(max_log + 1));
// Initialize base level (k=0) of sparse table
for (int i = 0; i < n; ++i) st[i][0] = v[i];
// Build sparse table layers
for (int k = 1; k <= max_log; ++k) {
for (int i = 0; i + (1 << k) <= n; ++i) {
st[i][k] = std::min(st[i][k - 1], st[i + (1 << (k - 1))][k - 1]);
}
}
}
// Query the minimum value in the range [l, r] (inclusive).
T query(int l, int r) {
// Check for invalid range. Use identity value if invalid.
if (l > r || l < 0 || r >= (int)st.size()) {
// If using outside ACL context, check size. If st empty, this might error.
if (st.empty()) return identity;
return identity;
}
// Use precomputed log to find largest power of 2 less than or equal to range length.
int k = log_table[r - l + 1];
// The minimum is the minimum of two overlapping intervals covering [l, r].
return std::min(st[l][k], st[r - (1 << k) + 1][k]);
}
};
// Use long long for costs to prevent overflow, as total cost can be large.
using CostType = long long;
// Define a large value to represent infinity, carefully chosen to avoid overflow during additions.
const CostType INF = std::numeric_limits<CostType>::max() / 3;
int main() {
// Faster I/O
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int N, M; // Lengths of sequences A and B
std::cin >> N >> M;
std::vector<int> A(N); // Sequence A
for (int i = 0; i < N; ++i) std::cin >> A[i];
std::vector<int> B(M); // Target sequence B
for (int i = 0; i < M; ++i) std::cin >> B[i];
std::vector<CostType> C(M); // Costs C_0, C_1, ..., C_{M-1}
for (int i = 0; i < M; ++i) std::cin >> C[i];
// Coordinate compression: Map original values to smaller integer ranks [1..k]
// This is necessary for suffix array algorithms that work on integer alphabets.
std::map<int, int> val_map;
std::vector<int> all_vals;
all_vals.reserve(N + M);
for (int x : A) all_vals.push_back(x);
for (int x : B) all_vals.push_back(x);
std::sort(all_vals.begin(), all_vals.end());
all_vals.erase(std::unique(all_vals.begin(), all_vals.end()), all_vals.end());
int rank_val = 1; // Start ranks from 1
for (int x : all_vals) {
val_map[x] = rank_val++;
}
int max_char_val = rank_val; // Keep track of the largest rank used
// Construct the combined sequence S = A' #1 B' #2 using compressed ranks
// Use unique separator characters with values larger than any rank.
std::vector<int> S_vec;
S_vec.reserve(N + M + 2);
for (int x : A) S_vec.push_back(val_map[x]);
S_vec.push_back(max_char_val++); // Separator 1
int B_start_idx_in_S = S_vec.size(); // Store start index of B' within S
for (int x : B) S_vec.push_back(val_map[x]);
S_vec.push_back(max_char_val++); // Separator 2
int S_len = S_vec.size(); // Total length of combined sequence S
// Compute Suffix Array (SA) and LCP Array using AtCoder Library functions
// These are efficient implementations (typically O(N log N) or O(N)).
std::vector<int> sa = atcoder::suffix_array(S_vec);
std::vector<int> lcp = atcoder::lcp_array(S_vec, sa); // lcp[i] = LCP(SA[i], SA[i-1])
// Compute Rank array (inverse of SA): rank[i] = position of suffix S[i..] in SA
std::vector<int> rank(S_len);
for (int i = 0; i < S_len; ++i) rank[sa[i]] = i;
// Build RMQ structure on the LCP array for O(1) LCP queries
// Use S_len + 1 as identity (infinity) for min operation, as max LCP value is S_len.
SparseTable<int> rmq(lcp, S_len + 1);
// Lambda function to compute LCP between suffix starting at index i and suffix starting at index j in S
auto get_lcp = [&](int i, int j) -> int {
// Handle boundary cases
if (i < 0 || i >= S_len || j < 0 || j >= S_len) return 0;
if (i == j) return S_len - i; // LCP of a suffix with itself is its length
// Get ranks of suffixes i and j in the suffix array
int rank_i = rank[i];
int rank_j = rank[j];
// Ensure rank_i < rank_j for RMQ query range
if (rank_i > rank_j) std::swap(rank_i, rank_j);
// LCP(S[i..], S[j..]) = min(LCP(SA[k], SA[k-1])) for k from rank_i+1 to rank_j
// Query RMQ on LCP array over the range [rank_i + 1, rank_j]
return rmq.query(rank_i + 1, rank_j);
};
// Dijkstra's algorithm to find the minimum cost path
std::vector<CostType> dist(M + 1, INF); // dist[i] = min cost to form prefix B[0..i-1] (length i)
dist[0] = 0; // Base case: cost to form empty prefix is 0
// Priority Queue stores pairs {cost, node_index}, ordered by minimum cost
std::priority_queue<std::pair<CostType, int>, std::vector<std::pair<CostType, int>>, std::greater<std::pair<CostType, int>>> pq;
pq.push({0, 0}); // Start Dijkstra from state 0 (empty sequence)
while (!pq.empty()) {
CostType d = pq.top().first; // Current minimum cost
int u = pq.top().second; // Current node (length of constructed prefix)
pq.pop();
// If we found a shorter path to u already, ignore this entry
if (d > dist[u]) continue;
// If we reached the target length M, we are done (since Dijkstra finds shortest path first)
if (u == M) break;
// Compute the Longest Common Prefix (LCP) between sequence A and the suffix of B starting at index u.
// This determines the maximum length k such that A[0..k-1] matches B[u..u+k-1].
int l = 0;
int B_suffix_start_idx = B_start_idx_in_S + u; // Index in combined string S
if (B_suffix_start_idx < S_len) { // Check bounds before querying LCP
l = get_lcp(0, B_suffix_start_idx); // LCP of A (starts at S[0]) and B[u..] (starts at S[B_suffix_start_idx])
}
// Determine the maximum valid k for the current operation
// k must be at most LCP length l, the length N of A, and the remaining length M-u needed.
int K_u = std::min({l, N, M - u});
// Explore all possible operations: append A[0..k-1] for k from 1 to K_u
for (int k = 1; k <= K_u; ++k) {
int v = u + k; // The resulting length will be v
// The cost depends on the length 'u' *before* the operation. C is 0-indexed.
CostType current_C = C[u];
// Calculate the cost of this operation: k * C[u]
CostType weight = (CostType)k * current_C;
// Check for potential overflow before adding weights
// If dist[u] + weight would exceed INF, this path is too costly.
if (dist[u] >= INF - weight) {
continue;
}
// Calculate the new total cost to reach state v via state u
CostType new_dist = dist[u] + weight;
// If this path is shorter than the current known shortest path to v...
if (new_dist < dist[v]) {
dist[v] = new_dist; // Update the minimum distance to v
pq.push({dist[v], v}); // Add the updated state to the priority queue
}
}
}
// After Dijkstra finishes, check if the target state M is reachable
if (dist[M] == INF) {
std::cout << -1 << std::endl; // Not reachable
} else {
std::cout << dist[M] << std::endl; // Output the minimum cost
}
return 0;
}