Hatena::Grouptopcoder

cafelier@SRM

cafelier のSRM参加記録です。コンテスト中に考えてたことを執拗に全部書き残すとどうなるだろうかという試み本番中にこういうコードが書きたかったなあ、という後で書いた反省コードを書き残す試み

スパムが来たのでしばらくコメント欄をはてなユーザ限定にしています、すみません、

 | 

2010-07-03

ACM-ICPC 2010 Japan Domestic 問題E

| 02:08 | はてなブックマーク -  ACM-ICPC 2010 Japan Domestic 問題E - cafelier@SRM

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



解法1:最良優先

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


  • 辞書順最小の方に進むとゴールにたどりつけなくなる場合
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
   {
      // データセットを1個読み込んでは 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 は同じ接点を2回以上通っているからです。

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


解法2:文字列より文字で

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

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

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


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

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

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


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

/* 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()
{
   /* データセットを1個読み込んでは 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;
}

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


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


解法3:最短経路の話

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


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

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

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

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

とか。


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

  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")ので、後ろからダイクストラは使えません。
    • ダイクストラするなら前からですが、接頭辞やサイクルに気をつける必要があります。
    • 気をつけると、要するに解法1になります。

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

cafeliercafelier2010/07/06 14:53解法4:長さ L で行ける辞書順最小路、を各長さ L (≦6N)各ノードについてもとめる動的計画法(あるいは拡張ダイクストラ)
というのがあるらしい。
http://d.hatena.ne.jp/Tayama/20100703/1278141167
http://d.hatena.ne.jp/kusano_prog/20100705/1278361318
http://d.hatena.ne.jp/pes_magic/20100706/1278367137
なるほどなー。

トラックバック - http://topcoder.g.hatena.ne.jp/cafelier/20100703
 | 

presented by cafelier/k.inaba under CC0