結果

問題 No.1370 置換門松列
コンテスト
ユーザー mai
提出日時 2026-01-31 16:42:55
言語 C++17
(gcc 15.2.0 + boost 1.89.0)
結果
AC  
実行時間 26 ms / 2,000 ms
コード長 3,763 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,046 ms
コンパイル使用メモリ 107,932 KB
実行使用メモリ 8,960 KB
最終ジャッジ日時 2026-01-31 16:42:58
合計ジャッジ時間 3,143 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 25
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

// Gemimi 3 Pro preview

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

// トポロジカルソートを用いて値を構築する関数
// mode == 0: a1 < a2 > a3 < a4 ... (谷, 山, 谷...)
// mode == 1: a1 > a2 < a3 > a4 ... (山, 谷, 山...)
bool solve(int N, int M, const vector<int>& A, bool mode, vector<int>& result_vals) {
    vector<vector<int>> adj(M + 1);
    vector<int> in_degree(M + 1, 0);
    
    // 不等式制約をグラフの辺に変換
    for (int i = 0; i < N - 1; ++i) {
        int u = A[i];
        int v = A[i+1];
        
        int from, to;
        if (mode == 0) { 
            // パターン: 低, 高, 低, 高...
            // i=0 (偶数): 低 -> 高 なので u < v (辺 u -> v)
            // i=1 (奇数): 高 -> 低 なので u > v (辺 v -> u)
            if (i % 2 == 0) {
                from = u; to = v;
            } else {
                from = v; to = u;
            }
        } else {
            // パターン: 高, 低, 高, 低...
            // i=0 (偶数): 高 -> 低 なので u > v (辺 v -> u)
            // i=1 (奇数): 低 -> 高 なので u < v (辺 u -> v)
            if (i % 2 == 0) {
                from = v; to = u;
            } else {
                from = u; to = v;
            }
        }
        
        adj[from].push_back(to);
        in_degree[to]++;
    }
    
    // Kahnのアルゴリズムによるトポロジカルソート
    queue<int> q;
    for (int i = 1; i <= M; ++i) {
        if (in_degree[i] == 0) {
            q.push(i);
        }
    }
    
    vector<int> topo_order;
    topo_order.reserve(M);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        topo_order.push_back(u);
        
        for (int v : adj[u]) {
            in_degree[v]--;
            if (in_degree[v] == 0) {
                q.push(v);
            }
        }
    }
    
    // 閉路がある場合は全てのノードを訪問できない
    if (topo_order.size() < M) return false;
    
    // トポロジカル順序に従って値を割り当て (小さい順に 1, 2, ..., M)
    result_vals.assign(M + 1, 0);
    for (int i = 0; i < M; ++i) {
        // topo_order[i] は i+1 番目に小さい値を持つべき変数
        result_vals[topo_order[i]] = i + 1;
    }
    return true;
}

int main() {
    // 高速化
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int N, M;
    if (!(cin >> N >> M)) return 0;
    
    vector<int> A(N);
    for (int i = 0; i < N; ++i) {
        cin >> A[i];
    }
    
    // 門松列の定義「3つの要素は全て異なる」ための事前チェック
    
    // 隣り合う要素が同じだと、x_a = x_b となり条件を満たせない
    for (int i = 0; i < N - 1; ++i) {
        if (A[i] == A[i+1]) {
            cout << "No" << endl;
            return 0;
        }
    }
    // 1つ飛ばしの要素が同じだと、(x, y, x) となり条件を満たせない
    for (int i = 0; i < N - 2; ++i) {
        if (A[i] == A[i+2]) {
            cout << "No" << endl;
            return 0;
        }
    }
    
    vector<int> res;
    // パターンA (谷・山・谷...) を試す
    if (solve(N, M, A, 0, res)) {
        cout << "Yes" << endl;
        for (int i = 1; i <= M; ++i) {
            cout << res[i] << (i == M ? "" : " ");
        }
        cout << endl;
    } 
    // パターンB (山・谷・山...) を試す
    else if (solve(N, M, A, 1, res)) {
        cout << "Yes" << endl;
        for (int i = 1; i <= M; ++i) {
            cout << res[i] << (i == M ? "" : " ");
        }
        cout << endl;
    } 
    // どちらも不可能
    else {
        cout << "No" << endl;
    }
    
    return 0;
}
0