結果
問題 | No.1370 置換門松列 |
ユーザー |
|
提出日時 | 2024-11-24 12:27:58 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 6,777 bytes |
コンパイル時間 | 1,212 ms |
コンパイル使用メモリ | 84,804 KB |
実行使用メモリ | 35,076 KB |
最終ジャッジ日時 | 2024-11-24 12:28:02 |
合計ジャッジ時間 | 4,914 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 5 |
other | AC * 21 WA * 4 |
ソースコード
/*2024/11/24ChatGPT o1-preview*//*次の競技プログラミングの問題を解いてください。問題を解くときは以下のステップにしたがってください。1. 全体的な方針の説明。どのアルゴリズムを使うか。2. 具体的な実装方針3. C++ によるソースコード。ただし、"具体的な実装方針" に関連したコメントを記載すること- - -## 問題文3つの要素から成る数列 $B = (B_1,B_2,B_3)$ が次の条件を満たす時、 $B$ は門松列であると言い伝えられています。* $B_1,B_2,B_3$ は全て異なる* 3つの要素のうち $B_2$ が最も大きい、あるいは最も小さい標準入力から N 要素から成る数列 $A_1,...,A_N$ と $M$ が与えられます。数列 $X_{A_1}, X_{A_2}, ..., X_{A_N}$ が以下の条件を満たすような、$X_1, X_2, ..., X_M$の割り当てが存在するかどうか判定し、存在するならば1つ出力してください。* どの連続した長さ 3 の部分列を取り出しても門松列である。## 入力制約$3 \le N \le 10^5$$1 \le M \le 10^5$$1 \le A_i \le M$## 出力条件を満たす割り当てが存在しないなら、Noを出力してください。存在するならば、Yesを出力後、半角スペース区切りで $X_1, X_2, \ldots, X_M$ を出力してください。$X_i$ は $1 \le X_i \le 10^9$の制約を満たす整数とします。## サンプル### サンプル1入力```4 31 2 3 1```出力```Yes2 3 1```$A = (1, 2, 3, 1)$ です。出力は、$X = (2, 3, 1)$ を解としています。これらを $X_{A_1}, X_{A_2}, X_{A_3}, X_{A_N}$ に割り当てると、$2, 3, 1, 2$です。この数列のうち、連続した長さ3の部分列は $(2, 3, 1)$ と $(3, 1, 4)$ ですが、どちらも門松列となります。解は複数存在しますが、どれを出力しても構いません。例えば、$X = (3, 4, 2)$ も同様に条件を満たします。### サンプル2入力```5 31 3 3 3 1```出力```No```解は存在しないため、No と出力します。- - -*/// Step 1: Overall Strategy// We model the problem as a 2-SAT problem. Each unique value in A corresponds to a variable that can be true (High) or false (Low).// Constraints are derived from the Kadomatsu condition on every continuous subsequence of length 3 in A.// The problem reduces to checking if the 2-SAT instance is satisfiable, and if so, assigning values to variables accordingly.// Step 2: Specific Implementation Plan// - For every length-3 subsequence in A, ensure all elements are distinct; if not, output "No".// - Map each unique A_i to a variable x_i (True or False).// - For each subsequence (A_i, A_{i+1}, A_{i+2}), add implications based on the Kadomatsu condition:// - x_{A_{i+1}} ⇒ ¬x_{A_i}// - x_{A_{i+1}} ⇒ ¬x_{A_{i+2}}// - ¬x_{A_{i+1}} ⇒ x_{A_i}// - ¬x_{A_{i+1}} ⇒ x_{A_{i+2}}// - Build the implication graph and run a 2-SAT solver using SCCs.// - Assign actual numeric values to X_i based on the variables' assignments.// - Ensure assigned values satisfy the Kadomatsu condition.#include <iostream>#include <vector>#include <algorithm>using namespace std;const int MAXM = 100005;vector<int> graph[2 * MAXM]; // Implication graphvector<int> rgraph[2 * MAXM]; // Reverse implication graphvector<int> order; // For order in DFSbool visited[2 * MAXM]; // For DFSint component[2 * MAXM]; // Component ID for each nodeint assignment[MAXM]; // Truth assignment for variablesvoid dfs1(int v) {visited[v] = true;for (int u : graph[v]) {if (!visited[u])dfs1(u);}order.push_back(v);}void dfs2(int v, int label) {component[v] = label;for (int u : rgraph[v]) {if (component[u] == -1)dfs2(u, label);}}bool two_sat(int num_vars) {fill(visited, visited + 2 * num_vars, false);order.clear();for (int i = 0; i < 2 * num_vars; ++i) {if (!visited[i])dfs1(i);}fill(component, component + 2 * num_vars, -1);int label = 0;for (int i = 2 * num_vars - 1; i >= 0; --i) {int v = order[i];if (component[v] == -1) {dfs2(v, label++);}}for (int i = 0; i < num_vars; ++i) {if (component[2 * i] == component[2 * i + 1])return false; // Unsatisfiableassignment[i] = component[2 * i] > component[2 * i + 1];}return true;}void add_implication(int u, int v) {graph[u].push_back(v);rgraph[v].push_back(u);}void add_clause(int a, bool neg_a, int b, bool neg_b) {// (¬a ∨ b) corresponds to a ⇒ bint u = 2 * a + (neg_a ? 1 : 0);int v = 2 * b + (neg_b ? 1 : 0);add_implication(u, v);}int main() {int N, M;cin >> N >> M;vector<int> A(N);vector<int> unique_values;for (int i = 0; i < N; ++i) {cin >> A[i];--A[i]; // 0-based indexingunique_values.push_back(A[i]);}sort(unique_values.begin(), unique_values.end());unique_values.erase(unique(unique_values.begin(), unique_values.end()), unique_values.end());int num_vars = M;// Map from value to indexvector<int> value_to_index(M);for (int idx = 0; idx < M; ++idx) {value_to_index[idx] = idx;}// Step 1: Check for duplicates in any subsequence of length 3for (int i = 0; i + 2 < N; ++i) {int a = A[i], b = A[i + 1], c = A[i + 2];if (a == b || b == c || a == c) {cout << "No" << endl;return 0;}}// Step 2: Build the 2-SAT clausesfor (int i = 0; i + 2 < N; ++i) {int a = A[i], b = A[i + 1], c = A[i + 2];int va = value_to_index[a];int vb = value_to_index[b];int vc = value_to_index[c];// x_vb ⇒ ¬x_vaadd_clause(vb, false, va, true);// x_vb ⇒ ¬x_vcadd_clause(vb, false, vc, true);// ¬x_vb ⇒ x_vaadd_clause(vb, true, va, false);// ¬x_vb ⇒ x_vcadd_clause(vb, true, vc, false);}// Step 3: Solve the 2-SAT instanceif (!two_sat(num_vars)) {cout << "No" << endl;return 0;}// Step 4: Assign numeric values to X_ivector<int> X(M);for (int i = 0; i < M; ++i) {if (assignment[i]) {X[i] = 200000000 + i; // High} else {X[i] = 100000000 + i; // Low}}// Output resultcout << "Yes" << endl;for (int i = 0; i < M; ++i) {cout << X[i] << (i + 1 < M ? ' ' : '\n');}return 0;}