cafelier@SRM

ACM-ICPC 2010 Japan Domestic 問題E

その他 | 02:08 |

ACM-ICPC 2010 国内予選 の問題Eを解いてみたよ。

解法１：最良優先

問題に書いてあることに忠実に、スター(ト)からゴール(ド)に向かって、辞書順で早い方早い方を優先して進んで行く方法です。注意しないといけないのは「何も考えずに、まっしぐらに辞書順で一番早いラベルの矢印だけを選んで進む」のは間違いということです。二つ理由があって…

• 辞書順最小の方に進むとゴールにたどりつけなくなる場合

3 2 0 2
0 1 a
0 2 b

• 答えは "b" ですが、スタート 0 から出てる最速の矢印は "a" だからといってそっちに行っちゃうと未来がありません。行き止まり。
• 解決策としては、本体の探索を始める前に、各節点が「行き止まり」かどうか判定しといて、そっちには決して行かないようにするなど

• 接頭辞に要注意

3 3 0 2
0 1 a
0 2 ab
1 2 c

• 上の例の答えは "ab" ですが、スタート 0 から生えてる矢印のラベルだけで比べると、"a" < "ab" なので、うっかり "a" 方向に突き進んで "ab" のことを忘れてしまうと、間違えて "ac" を答えてしまいます。
• 解決策としては、矢印一本だけ見ると遅くみえるルートでも「探索候補」としてとりあえず覚えておいて、必要になったらとりだす感じ。

言葉で説明するよりもコード見る方がわかりやすいですね。

// Java
import java.util.*;

public class PowerfulSpell
{
   public static void main(String[] arg) throws java.io.IOException
   {
      // データセットを１個読み込んでは solve() を呼び出すループ
      for(Scanner sc = new Scanner(System.in) ;;)
      {
         int N = sc.nextInt();
         int A = sc.nextInt();
         int S = sc.nextInt();
         int G = sc.nextInt();
         if( N==0 && A==0 && S==0 && G==0 )
            break;

         Arrow[] arr = new Arrow[A];
         for(int i=0; i<A; ++i)
            arr[i] = new Arrow(sc);

         System.out.println( solve(N,S,G,arr) );
      }
   }

   // 矢印データ
   static class Arrow
   {
      final int    x;
      final int    y;
      final String lab;

      Arrow(Scanner sc) throws java.io.IOException
      {
         x   = sc.nextInt();
         y   = sc.nextInt();
         lab = sc.next();
      }
   }

   // スタートからの経路を表すデータ
   // どういう文字列で来たか（spell）と、今どの節点にいるか（lastNode）
   static class Path implements Comparable<Path>
   {
      final String spell;
      final int lastNode;
      Path(String s, int n) { spell=s; lastNode=n; }

      // 辞書順で早いほうが「良い」経路
      public int compareTo( Path rhs ) {
         int c = spell.compareTo(rhs.spell);
         return c!=0 ? c : lastNode-rhs.lastNode;
      }
   }

   // 本体
   static String solve(int N, int S, int G, Arrow[] arr)
   {
      // とりあえず、ゴールに着けない節点に迷い込んではいけないので、
      // まず全節点について、ゴールまで行けるかどうか調べておく
      //
      // 方法は、幅優先探索(BFS)でも深さ優先探索(DFS)でも、
      // なんでもお好みの方法でいいと思います。

      boolean[][] reachable = new boolean[N][N];

      for(Arrow a : arr)
         reachable[a.x][a.y] = true;
      for(int k=0; k<N; ++k)
      {
         reachable[k][k] = true;
         for(int i=0; i<N; ++i)
            for(int j=0; j<N; ++j)
               reachable[i][j] |= reachable[i][k] & reachable[k][j];
      }

      // そもそもスタートからゴールに行けない場合は "NO"

      if( !reachable[S][G] )
         return "NO";

      // 行ける場合は、
      // スタートから始めて、「辞書順で早い順に」経路文字列を全探索していきます。

      TreeSet<Path> q = new TreeSet<Path>(); // 探索候補
      q.add( new Path("",S) ); // 「スタート S にいます」状態から探索開始

      for(;;)
      {
         Path p = q.pollFirst(); // 候補のなかから一番早いのを取り出す

         if( p.lastNode == G ) // ゴールについた
            return p.spell;

         if( p.spell.length() >= N*6 ) // ループしてる
            return "NO";

         for(Arrow a : arr) // それ以外：今の節点から一つパス延ばしたものを候補に入れる
            if( p.lastNode==a.x && reachable[a.y][G] )
               q.add( new Path(p.spell+a.lab, a.y) );
          // 本当は、"辞書順で最小の矢印と、それを接頭辞とするもの" だけ
          // 入れれば十分なんですが、コード書くの面倒なので全部入り…
      }
   }
}

複数の候補をためておいて、良い方から順に探索の舌を伸ばしていく、いわゆる

　　最良優先探索

の一種になります。最良の候補を管理するデータ構造として、PriorityQueue ではなく TreeSet を使っているのは、こうしないと「経路は違うけど文字列は同じでlastNodeも同じ」なパスが大量にありえるため。TreeSet なら重複を自動的に除いてくれます。

「文字列の長さが 6N を超えたらループしてる」というのは、節点数 N で、ラベルの長さの最大が 6 なので、文字列の長さが 6N ということは、少なくともこの経路 p は同じ接点を２回以上通っているからです。

辞書順最小のループからは、すぐ抜け出すよりも１周回ってから抜け出す方が、それよりも２周回ってから抜け出す方が（以下略）お得なので、これが出てきた時点で "NO" が確定。

解法２：文字列より文字で

ちょっと考えてみると、解法１の面倒な部分は、ほとんどすべて「ラベルが文字列」だったことに起因していることがわかります。もし仮にラベルが全部一文字だったら、

3 3 0 2
0 1 a
0 2 ab
1 2 c

こんなデータで「うっかり接頭辞だから辞書順で早そうに見える方に突き進む」こともありません。全部１文字なので接頭辞だったりそうじゃなかったりしませんので。

つまり１文字なら TreeSet を用意して最良優先…のようなことを考えなくてよくなります。常に辞書順最小の矢印を進めばよい。ただし、最小ならどれも良いわけではなく

4 4 0 3
0 1 a
0 2 a
1 3 c
2 3 b

こんなデータで、0 から 1 と 2 どっちに行こうかなーと思って 1 だけに進んで 2 を忘れてしまうと "ab" が見つからずアウトです。ここは幅優先探索的に「最小矢印で行ける先は全部見る」とすればＯＫです。

というわけで、入力を無理矢理１文字ラベルに変換してから解く方法です。

/* C */
#include <stdio.h>
#include <memory.h>
typedef enum { false, true } bool;

enum { MAX_LAB  = 6 };
enum { MAX_EDGE = 400*MAX_LAB };
enum { MAX_NODE = 40+MAX_EDGE };
enum { MAX_ANS  = MAX_NODE };

/* 矢印データ */
typedef struct { int x, y; char lab; } arrow;

/* とりあえず、ゴールに着けない節点に迷い込んではいけないので、
 * まず全節点について、ゴールまで行けるかどうか調べておく */
void compute_reachabilty(arrow arr[], int N, int A, int G, bool r[])
{
   bool changed;

   r[G] = true;
   do {
      int i;
      changed = false;
      for(i=0; i<A; ++i)
         if( !r[arr[i].x] && r[arr[i].y] )
            r[arr[i].x] = changed = true;
   } while( changed );
}

void solve(arrow arr[], int N, int A, int S, int G, int SpellLimit)
{
   int  i,j,k;
   char answer[MAX_ANS+1] = {};
   bool cur[MAX_NODE] = {};
   bool r[MAX_NODE] = {};

   /* そもそもスタートからゴールに行けない場合は "NO" */
   compute_reachabilty(arr, N, A, G, r);
   if( !r[S] ) {
      puts("NO");
      return;
   }

   /* 「スタート S にいます」状態から探索開始 */
   cur[S] = true;

   for(i=0; i<SpellLimit; ++i) {
      if( cur[G] ) {
         /* ゴールについた */
         puts(answer);
         return;
      }

      /* 今の節点から辞書順最小の矢印で行けるところ全部に並列に進む */
      bool next[MAX_NODE] = {};
      char nextLab = 127;
      for(k=0; k<A; ++k)
         if( cur[arr[k].x] && r[arr[k].y] && arr[k].lab<=nextLab ) {
            if( arr[k].lab < nextLab ) {
               memset(next, 0, sizeof(next));
               nextLab = arr[k].lab;
            }
            next[arr[k].y] = true;
         }
      answer[i] = nextLab;
      memcpy(cur, next, sizeof(cur));
   }

   /* ループしてる */
   puts("NO");
}

int main()
{
   /* データセットを１個読み込んでは solve() を呼び出すループ */
   int N,A,S,G;
   while( scanf("%d%d%d%d",&N,&A,&S,&G), N|A|S|G ) {
      int i,j,ai=0,SpellLimit = MAX_LAB*N;
      arrow arr[MAX_EDGE];

      for(i=0; i<A; ++i) {
         int  fr, to;
         char lab[99];
         scanf("%d %d %s", &fr, &to, lab);

         /* 文字列ラベルを文字ラベルに分解。
          * つまり
          *    ・---abc--->・
          * のかわりに、新しく節点を二つ導入して
          *    ・---a--->・---b--->・---c--->・
          * という魔法の紋様と思い込むことにします。 */

         for(j=0; lab[j]; ++j) {
            int   x = j==0 ? fr : N-1;
            int   y = lab[j+1] ? N++ : to;
            arrow a = {x, y, lab[j]};
            arr[ai++] = a;
         }
      }
      solve(arr, N, ai, S, G, SpellLimit);
   }
   return 0;
}

ところで、ラベルを全部１文字に分解したものは、正規表現の実装に使われる 非決定性オートマトン によく似ています。実はそのものです。

上記のコードの cur や next のように「ある文字をたどって行ける先の節点を全部覚えておいて、全節点並列に１文字１文字進んでいく」方法で非決定性オートマトンを動かすやり方は、最近公開された Google 発の正規表現ライブラリ RE2 の中の人が、ちょっと昔に "Regular Expression Matching Can Be Simple And Fast" という記事で大プッシュしていました。読んでみると面白いかも。

解法３：最短経路の話

この問題はグラフの最短経路問題に見える…という見方もあります。

ふつう、最短経路というとグラフで

　　「辺の重み⇔自然数や実数、最短⇔経路の重みの和が最小」

という場合ですが、それ以外の構造でも同じ問題を考えることができます。

　　「辺の重み⇔文字列、最短⇔経路の重みの結合が辞書順最小」

とか。

大雑把に言うと、最短経路の有名アルゴリズムである ダイクストラ法 や ベルマン・フォード法 は

　　min(x,y) + z = min(x+z, y+z)

を満たすような min 演算と + 演算が辺の重みに対して定義できれば、使えます。数値であることが本質ではなくて、最小値を選ぶ演算と、重みを結合する演算が存在して分配則を満たすことが、このあたりのアルゴリズムの本質です。日本語でいうと「v1→v2→...→vkの最短経路は、v1→...→v[k-1]の最短経路に辺を継ぎ足した形に必ずなってる」。ダイクストラは追加で

　　min(x,x+z) = x

が必要だったかも。いわゆる「辺の重みが負でない」という。

と、えらそーに書いておきながら、文字列の辞書順の場合

　　min(x,y) + z = min(x+z, y+z)

これ、成り立ちません。接頭辞の呪い。

　　min("a","ab")+"c"＝"ac" ≠ "abc"＝min("a"+"c","ab"+"c")

でも、逆から足すと

　　z + min(x,y) = min(z+x, z+y)

これは成り立ちます。

というわけで、逆から、つまりスタートからゴールに向かってではなく、ゴールからスタートに向かって最短路を探すアルゴリズムが使えます。

// C++
#include <iostream>
#include <vector>
#include <string>
using namespace std;

struct arrow { int x, y; string lab; };
static const string INF = "NO";

string bwd_bellman_ford(const vector<arrow>& arr, int N, int A, int S, int G, int LOOP)
{
   vector<string> d(N, INF);
   d[G] = "";
   for(int t=0; t<N*LOOP; ++t)
   {
      vector<string> d2 = d;
      for(int i=0; i<A; ++i)
         if( d[arr[i].y]!=INF && (d2[arr[i].x]==INF || d2[arr[i].x]>arr[i].lab+d[arr[i].y]) )
         {
            d2[arr[i].x] = arr[i].lab + d[arr[i].y];
            if( arr[i].x==S && t>=N )
               return "NO"; // スタートからの最短経路にサイクルがある
         }
      d.swap(d2);
   }
   return d[S];
}

int main()
{
   for(int N,A,S,G,maxLab=0; cin>>N>>A>>S>>G, N|A|S|G;)
   {
      vector<arrow> arr(A);
      for(int i=0; i<A; ++i)
      {
         cin >> arr[i].x >> arr[i].y >> arr[i].lab;
         maxLab = max<int>(maxLab, arr[i].lab.size());
      }
      cout << bwd_bellman_ford(arr, N, A, S, G, 1+maxLab) << endl;
   }
}

結構これで挑んだチームは多いんじゃないかと思うんですが、ハマりどころがあるとすれば、

• 最外周ループ for(int t=0; t＜N*LOOP; ++t) のループ回数が足りない

40 41 0 39
0 1 x
1 1 x
1 39 y
0 2 xxxxxx
2 3 xxxxxx
(略)
37 38 xxxxxx
38 39 xxxxxz

• 回れば回るほど辞書順でよくなるサイクル（最短経路のたとえで言えば"負の"サイクル）の検出は N 回まわせばいい、という知識を元に N 回で止めて "NO" を返してしまうと、「スタートからゴールへの辞書順最小経路とは関係ないところにあるサイクル」を検出して間違えて "NO" にしてしまう可能性があります。
• 「負のサイクルの影響がスタートからの最短路まで波及した」ことを検知してはじめて "NO" を返す方が安全
  • N回目までにどっかでサイクルができて、N本矢印をたどればスタートにそのサイクルの影響が来るから 2N 回で安全！？
  • というのは間違いで、上の例のように、できた負のサイクルを何周かしないとスタートに影響できない場合があります。
  • これもループしない呪文の長さの上限 6N まで回してみればわかるので、そのくらいで打ち切ります。

• 非負制約の「逆バージョン」 min(x,z+x)=x は文字列では成り立たない（min("z","a"+"z")="az"≠"z"）ので、後ろからダイクストラは使えません。
  • ダイクストラするなら前からですが、接頭辞やサイクルに気をつける必要があります。
  • 気をつけると、要するに解法１になります。

• 「前からベルマン・フォード」を殺す入力例としては

3 3 0 2
0 1 a
0 1 ab
1 2 c

• こんなものがあります。
• 0 から 1 への最短路は常に "a" なので、何周更新しても 1 への最短路は "a" のまま変わりません。ですが、0 から 1 を経由して 2 に行く最短路の時には "ab" を経由する必要があって、困ります。
• 「最短路と、それを接頭辞として持つもの全部」を記憶しておく形に変えた「前からベルマン・フォード」なら上手く行くかも。