結果
| 問題 |
No.1370 置換門松列
|
| コンテスト | |
| ユーザー |
 mai
|
| 提出日時 | 2024-11-24 12:27:58 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 6,777 bytes |
| コンパイル時間 | 1,028 ms |
| コンパイル使用メモリ | 83,372 KB |
| 最終ジャッジ日時 | 2025-02-25 06:02:21 |
|
ジャッジサーバーID （参考情報） |
judge5 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 5 |
| other | AC * 21 WA * 4 |
コンパイルメッセージ
In file included from /usr/include/c++/13/string:51,
from /usr/include/c++/13/bits/locale_classes.h:40,
from /usr/include/c++/13/bits/ios_base.h:41,
from /usr/include/c++/13/ios:44,
from /usr/include/c++/13/ostream:40,
from /usr/include/c++/13/iostream:41,
from main.cpp:100:
In function ‘typename __gnu_cxx::__enable_if<std::__is_scalar<_Tp>::__value, void>::__type std::__fill_a1(_ForwardIterator, _ForwardIterator, const _Tp&) [with _ForwardIterator = int*; _Tp = int]’,
inlined from ‘void std::__fill_a(_FIte, _FIte, const _Tp&) [with _FIte = int*; _Tp = int]’ at /usr/include/c++/13/bits/stl_algobase.h:977:21,
inlined from ‘void std::fill(_ForwardIterator, _ForwardIterator, const _Tp&) [with _ForwardIterator = int*; _Tp = int]’ at /usr/include/c++/13/bits/stl_algobase.h:1007:20,
inlined from ‘bool two_sat(int)’ at main.cpp:137:9:
/usr/include/c++/13/bits/stl_algobase.h:931:18: warning: ‘void* __builtin_memset(void*, int, long unsigned int)’ specified bound between 18446744065119617024 and 18446744073709551612 exceeds maximum object size 9223372036854775807 [-Wstringop-overflow=]
931 | *__first = __tmp;
| ~~~~~~~~~^~~~~~~
ソースコード
/*
2024/11/24
ChatGPT 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 3
1 2 3 1
```
出力
```
Yes
2 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 3
1 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 graph
vector<int> rgraph[2 * MAXM]; // Reverse implication graph
vector<int> order; // For order in DFS
bool visited[2 * MAXM]; // For DFS
int component[2 * MAXM]; // Component ID for each node
int assignment[MAXM]; // Truth assignment for variables
void 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; // Unsatisfiable
assignment[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 ⇒ b
int 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 indexing
unique_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 index
vector<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 3
for (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 clauses
for (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_va
add_clause(vb, false, va, true);
// x_vb ⇒ ¬x_vc
add_clause(vb, false, vc, true);
// ¬x_vb ⇒ x_va
add_clause(vb, true, va, false);
// ¬x_vb ⇒ x_vc
add_clause(vb, true, vc, false);
}
// Step 3: Solve the 2-SAT instance
if (!two_sat(num_vars)) {
cout << "No" << endl;
return 0;
}
// Step 4: Assign numeric values to X_i
vector<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 result
cout << "Yes" << endl;
for (int i = 0; i < M; ++i) {
cout << X[i] << (i + 1 < M ? ' ' : '\n');
}
return 0;
}