天下一プログラマーコンテスト2016予選A C - 山田山本問題

http://tenka1-2016-quala.contest.atcoder.jp/tasks/tenka1_2016_qualA_c

問題概要

英小文字のみからなる2つの文字列のペア(Ai, Bi)がN個与えられる。ここで26個のアルファベットの順番を並べ替え、AiがBiより辞書順で小さくなるようにしたい。そのような並べ替えが存在するか判定し、存在する場合はそのうち元々の辞書順で最小のものを求めよ。

解法

英小文字26文字を頂点とし、「文字αが文字βより先でなければならない」という関係が成り立つときα -> βに辺を張る。このグラフにサイクルがなければ解が存在し、サイクルがあれば解が存在しない。サイクルが存在するということは「この文字より先じゃないと駄目」という関係をたどっていくと「自分自身より先じゃないと駄目」という矛盾した結論になる頂点が存在するということになるからである。

解が存在する場合、グラフのトポロジカルソートのうち辞書順最小が出力すべき解となる。普通のトポロジカルソートは 1.入ってくる辺がない頂点を選ぶ 2.その頂点を解の末尾に追加する 3.その頂点から出ている辺をすべて削除する の繰り返しで求めることができる。これを少し改変し、入ってくる辺がない頂点を選ぶパートで、選んだ頂点を優先度付きキューに溜めておき、辞書順で小さいものから取り出すようにすると最終的なトポロジカルソートも辞書順最小になる。（なおこの操作の結果すべての辺を削除することができなければトポロジカルソートは存在せず、解なしということになる）。

コーナーケースとして、AiかBiのどちらかがどちらかの接頭辞になっている場合がある。サンプルにもある通りBがAの接頭辞の場合どう順序を変えてもAを前にはできないので、解なしになる。逆にAがBの接頭辞の場合絶対にAが前に来るので、無意味な制約ということになる。

感想

思ったより時間かかったので記事を書きました

コード (D言語)

import std.stdio, std.array, std.string, std.conv, std.algorithm;
import std.typecons, std.range, std.random, std.math, std.container;
import std.numeric, std.bigint, core.bitop;
     
void main() {
    auto N = readln.chomp.to!int;
    auto edges = new bool[][](26, 26);
 
    foreach (i; 0..N) {
        auto s = readln.split;
        auto A = s[0];
        auto B = s[1];
        bool found = false;
        
        foreach (j; 0..min(A.length, B.length)) {
            if (A[j] != B[j]) {
                edges[B[j]-'a'][A[j]-'a'] = true;
                found = true;
                break;
            }
        }
 
        if (!found && B.length < A.length) {
            writeln(-1);
            return;
        }
    }
 
 
    auto q = new BinaryHeap!(Array!int, "a > b")();
    int[] toposo;
    foreach (i; 0..26) if (edges[i].sum == 0) q.insert(i);
 
    while (!q.empty) {
        int n = q.front;
        q.removeFront;
        toposo ~= n;
        foreach (m; 0..26) {
            if (edges[m][n]) {
                edges[m][n] = false;
                if (edges[m].sum == 0) q.insert(m);
            }
        }
    }
 
    
    if (26.iota.map!(i => edges[i].any).any) {
        writeln(-1);
    } else {
        char[] ans;
        foreach (c; toposo) ans ~= c.to!char + 'a';
        foreach (i; 0..26.to!char) if (ans.map!(a => a != i + 'a').all) ans ~= i + 'a';
        ans.writeln;
    }
}