hogecoder

tsutaj 競技プログラミングの記録

TopCoder SRM 705 Div2 Med (Div1 Easy): AlphabetOrder

(追記: Div1 Easy と Div2 Med が完全に同じ問題なのでタイトルを変更しました)

今回のSRMは大勝利したので嬉しい。Medが個人的に良問だと思ったので記事を書きます。

問題概要

原文 → TopCoder Statistics - Problem Statement

英小文字のみで構成された文字列がいくつか与えられる。各文字列について、先頭から順に見た時にアルファベットが昇順に並んでいるような文字列は「良い文字列」と呼ばれる。アルファベットの順番を適切に定義したとき、全ての文字列を「良い文字列」にできるならば Possible を、できないならば Impossible を出力せよ。

解説

愚直解法 (アルファベットの順番を全て試す) は、 26! 通りもあるため当然試せません。

そこで、グラフに落として考えてみましょう。文字列の  i 文字目から  j 文字目  (i < j) に向かって、有向辺を張ります。これを全ての  (i, j) の組み合わせについて行います。

例えば、文字列 abcd の場合は、以下のようになります。

f:id:tsutaj:20170112153832p:plain

常に左側のノードから右側のノードに向かって辺を張っているため、グラフが DAG になっていることがわかりますね。

さて、このグラフに意地悪をしてみましょう。文字列 ba を考えます。この文字列と abcd の1文字目・2文字目を考慮すると、明らかに全ての文字列を「良い文字列」にすることができませんね。実際に辺を張るとどうなるでしょうか?

f:id:tsutaj:20170112153835p:plain

このように、閉路ができてしまいます。閉路があるということは、アルファベットの順番を指し示していたはずの矢印がぐるぐる回っていることになりますので、Impossible であることと同義ですね。

以上より、この方針で解いていけばよいです。

  • 各文字列に対して、  0 \leqq i < j < 文字数 を満たす全ての  (i, j) の組み合わせを考え、(  i 文字目のアルファベット)  \rightarrow (  j 文字目のアルファベット) の方向に有向辺を張る
  • できたグラフが DAG であれば Possible で、DAG でなければ Impossible

あとは DAG の判定をどうするかですが、これについては過去に @Darsein 先生から教えを受けていたのでした。

トポロジカルソートは入次数0のノードと、そのノードから出ている辺をどんどん消していくことで得られます。閉路があると入次数0 のノードがいずれ出来なくなるので、閉路判定は トポロジカルソートの結果のサイズがグラフの頂点数と等しいかどうか でできるというわけです。今回の問題の場合、連結でないグラフができる場合がありますが、閉路さえなければトポロジカルソートのサイズは頂点数と等しくなるので問題ないです。

ちなみに、ワーシャルフロイドでも閉路判定できるのですが、連結でないグラフの場合少し面倒なことに加え、頂点数が多くなると TLE するのでイマイチです。(この問題の場合は TLE しませんが)

ソースコード

トポロジカルソートのソースコードは省略します。

class AlphabetOrderDiv2 {
    public:
    string isOrdered(vector<string> words) {
        Graph(int) G(26);
        set<int> s;
        rep(i,0,words.size()) {
            rep(j,0,words[i].length()) {
                int d = words[i][j] - 'a';
                s.insert(d);
                rep(k,j+1,words[i].length()) {
                    int d2 = words[i][k] - 'a';
                    if(d != d2) {
                        G[d].pb(Edge<int>(d2, 1));
                    }
                }
            }
        }

        vector<int> v = tpsort_Kahn(G);
        if(v.size() != 26) return "Impossible";
        else return "Possible";
    }
};

次で青になれたらいいなあ・・・