質問をすることでしか得られない、回答やアドバイスがある。

15分調べてもわからないことは、質問しよう!

ただいまの
回答率

90.50%

  • C++

    3455questions

    C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。

トポロジカルソートを用いた競技プログラミングの問題

解決済

回答 1

投稿

  • 評価
  • クリップ 0
  • VIEW 137

jellcur

score 2

 現状

トポロジカルソートと呼ばれるアルゴリズムを用いて解くことのできるこの問題(https://beta.atcoder.jp/contests/tenka1-2016-quala/tasks/tenka1_2016_qualA_c)に取り組んでいるのですが行き詰まってしまいました。

 発生している問題・エラーメッセージ

次の1つ目のリンクから飛んで頂いてわかるようにいくつかのテストケース(非公開)に正解できていません。また必要でしたらトポロジカルソートの概要は2つ目のリンクからご覧になれます。自分が用いたのはKahn's algorithmと呼ばれるものです。

https://beta.atcoder.jp/contests/tenka1-2016-quala/submissions/2830453

https://ja.m.wikipedia.org/wiki/トポロジカルソート

 該当のソースコード

#include <bits/stdc++.h> 

using namespace std;

#define rep(i,n) for(int (i) = 0; (i) < (n); ++(i))

template<class Abel> struct D_Graph {
    int V,E;
    bool **exist;
    vector<vector<pair<int,Abel>>> adj;
    vector<vector<pair<int,Abel>>> adj_inv;

    D_Graph(int V_size = 0) : V(V_size)
    {
        init(V);
    }

    void init(int V) {
        exist = (bool**)malloc(sizeof(bool*) * (V + 1));
        for(int i = 0; i <= V; ++i){
            exist[i] = (bool*)malloc(sizeof(bool) * (V + 1));
            fill(exist[i],exist[i] + V + 1,0);
        }
        adj.clear(); 
        adj_inv.clear();
        adj.resize(V + 1);
        adj_inv.resize(V + 1);
        for(int i = 1; i <= V; ++i){
            adj[0].push_back({i,0});
            exist[0][i] = 1;
        }
        E = 0;
    }

    int deg_out(int v) { return adj[v].size(); }

    int deg_in(int v) { return adj_inv[v].size(); }

    bool is_leaf(int v) { return deg_out(v) == 0; }

    bool is_root(int v) { return deg_in(v) == 0; }

    void add_edge(int from, int to, Abel cost = 1) {
        adj[from].push_back({to,cost});
        adj_inv[to].push_back({from,cost});
        exist[from][to] = 1;
        ++E;
    }

    bool tsort(vector<int> &seq, bool idx_ordered = 0) {
        seq.reserve(V);
        vector<int> in(V + 1);
        stack<int> rt;
        for(int i = 1; i <= V; ++i){
            in[i] = deg_in(i); 
            if(!in[i]){
                rt.push(i);
                seq.push_back(i);
            }
        }
        while(!rt.empty()){
            int r = rt.top();
            rt.pop();
            for(auto e : adj[r]){
                int v = e.first;
                --in[v];
                if(!in[v]){
                    rt.push(v);
                    if(idx_ordered){
                        int pos = 0;
                        for(int i = 0; i < seq.size(); ++i) if(seq[i] < v || exist[seq[i]][v]) pos = i + 1;
                        seq.insert(begin(seq) + pos,v);
                    }else{
                        seq.push_back(v);
                    }
                }
            }
        }
        if(seq.size() == V) return 1;
        return 0;
    }    
};

int main(){

    D_Graph<int> G(26);
    int N; cin>>N;
    string a,b;
    rep(j,N){
        cin>>a>>b;
        rep(i,min(a.size(),b.size())){
            if(a[i] != b[i]){
                G.add_edge(a[i] - 'a' + 1,b[i] - 'a' + 1);
                break;
            }
            if(i + 1 == b.size()){ cout<<-1<<endl; return 0; }
        }
    }
    vector<int> seq;
    bool j = G.tsort(seq,1);
    if(j){
        for(int c : seq) cout<<(char)(c - 1 + 'a');
    }else{
        cout<<-1;
    }
    cout<<endl;

    return 0;
}

 補足

D_Graph構造体のメンバ関数tsortが重要な部分になっています。

  • 気になる質問をクリップする

    クリップした質問は、後からいつでもマイページで確認できます。

    またクリップした質問に回答があった際、通知やメールを受け取ることができます。

    クリップを取り消します

  • 良い質問の評価を上げる

    以下のような質問は評価を上げましょう

    • 質問内容が明確
    • 自分も答えを知りたい
    • 質問者以外のユーザにも役立つ

    評価が高い質問は、TOPページの「注目」タブのフィードに表示されやすくなります。

    質問の評価を上げたことを取り消します

  • 評価を下げられる数の上限に達しました

    評価を下げることができません

    • 1日5回まで評価を下げられます
    • 1日に1ユーザに対して2回まで評価を下げられます

    質問の評価を下げる

    teratailでは下記のような質問を「具体的に困っていることがない質問」、「サイトポリシーに違反する質問」と定義し、推奨していません。

    • プログラミングに関係のない質問
    • やってほしいことだけを記載した丸投げの質問
    • 問題・課題が含まれていない質問
    • 意図的に内容が抹消された質問
    • 広告と受け取られるような投稿

    評価が下がると、TOPページの「アクティブ」「注目」タブのフィードに表示されにくくなります。

    質問の評価を下げたことを取り消します

    この機能は開放されていません

    評価を下げる条件を満たしてません

    評価を下げる理由を選択してください

    詳細な説明はこちら

    上記に当てはまらず、質問内容が明確になっていない質問には「情報の追加・修正依頼」機能からコメントをしてください。

    質問の評価を下げる機能の利用条件

    この機能を利用するためには、以下の事項を行う必要があります。

回答 1

check解決した方法

0

自己解決しました(下のコードで通すことができました)。
入次数0の頂点を互いを結ぶ辺がないようにまとめて優先度付き降順キューで持ち、
取り出しながらそこまでのソート列にその時点で辞書順を最小化できるように挿入していくことで実現できました。
予め色々なケース(特に自分のコードが対処を困難とするもの)を想定できるようになることも大切ですね。まだまだ精進が必要だと実感しました。

https://beta.atcoder.jp/contests/tenka1-2016-quala/submissions/2858520

投稿

  • 回答の評価を上げる

    以下のような回答は評価を上げましょう

    • 正しい回答
    • わかりやすい回答
    • ためになる回答

    評価が高い回答ほどページの上位に表示されます。

  • 回答の評価を下げる

    下記のような回答は推奨されていません。

    • 間違っている回答
    • 質問の回答になっていない投稿
    • スパムや攻撃的な表現を用いた投稿

    評価を下げる際はその理由を明確に伝え、適切な回答に修正してもらいましょう。

15分調べてもわからないことは、teratailで質問しよう!

  • ただいまの回答率 90.50%
  • 質問をまとめることで、思考を整理して素早く解決
  • テンプレート機能で、簡単に質問をまとめられる

関連した質問

同じタグがついた質問を見る

  • C++

    3455questions

    C++はC言語をもとにしてつくられた最もよく使われるマルチパラダイムプログラミング言語の1つです。オブジェクト指向、ジェネリック、命令型など広く対応しており、多目的に使用されています。