【AtCoder】ABC 394 E - Palindromic Shortest Path | 緑コーダーが解くAtCoder

配点: 450 点 / 実行時間制限: 2 sec / メモリ制限: 1024 MB / Difficulty: 1403

問題概要
制約
考察
実装例
コメント

問題概要

$N$ 頂点の有向グラフがあり、頂点には $1, 2, \cdots, N$ の番号が付いている。辺の情報は英小文字、-のいずれかである $N^2$ 個の文字 $C_{1, 1}, C_{1, 2}, \cdots, C_{1, N}, C_{2, 1}, \cdots, C_{N, N}$ によって与えられ、 $C_{i, j}$ が英小文字のとき頂点 $i$ から頂点 $j$ へ向かう辺がちょうど1つ存在してラベル $C_{i, j}$ が付いており、-のときそのような辺は存在しない。

このとき、 $1 \leq i, j \leq N$ を満たす各整数組 $(i, j)$ について、以下のクエリに対する答えを求めよ。

頂点 $i$ から頂点 $j$ に向かうパスのうち、辺に付けられたラベルの文字を順に結合した文字列が回文となるようなものの中で、最も短いものの長さを求めよ。ただし、そのようなパスがない場合は答えは $-1$ とせよ。

制約

$1 \leq N \leq 100$
$N$ は整数。

考察

とりあえず、回文の性質(というか定義？)について考えよう。これは以前、回文判定アルゴリズムを考えたときにも述べたが、簡単にまとめておく。

yuulis.hatenablog.com

空文字列や1つの文字も回文として認める。
既に回文である文字列 $S$ の前後に、任意の文字 $c$ を結合した文字列 $cSc$ も回文である。

つまり、ある文字 $c$ から始めて、その前後に同じ文字をくっつけていくことで、自動的に回文を構築することができるということだ( $c$ が空文字列なら偶数の長さ、そうでなければ奇数の長さの回文ができる)。

本問の本質はここにある。

これを与えられたグラフ上で行ってみよう。サンプルケース1で与えられた有向グラフを図に示すと以下のようになる。

このグラフでは、頂点ではなく辺に文字のラベルが付与されているので、文字を2頂点間のパスに置き換えて考えることにする。

例えば、以下のようになる。

文字cから始める。このときのパスは、 $4 \rightarrow 1$ 。
頂点 $1$ および $4$ に接続している辺で、ラベルの文字が同じものをたどると、それぞれ $1 \rightarrow 1$ (自己ループ) 、 $4 \leftarrow 3$ となる。したがって、この段階での回文はacaとなり、パスは $3 \rightarrow 4 \rightarrow 1 \rightarrow 1$ 。
頂点 $1$ および $3$ に接続している辺で、ラベルの文字が同じものをたどると、それぞれ $1 \rightarrow 2$ 、 $3 \leftarrow 2$ となる。したがって、この段階での回文はbacabとなり、パスは $2 \rightarrow 3 \rightarrow 4 \rightarrow 1 \rightarrow 1 \rightarrow 2$ 。

もう一つ。今度は空文字列から始めてみる。

空文字列を示すパスの一つとして、 $2 \rightarrow 2$ がある。
頂点 $2$ に接続している辺で、ラベルの文字が同じものをたどると、それぞれ $2 \rightarrow 3$ 、 $2 \leftarrow 1$ となる。したがって、この段階での回文はbbとなり、パスは $1 \rightarrow 2 \rightarrow 3$ 。
頂点 $1$ および $3$ に接続している辺で、ラベルの文字が同じものをたどると、それぞれ $1 \leftarrow 1$ (自己ループ) 、 $3 \rightarrow 4$ となる。したがって、この段階での回文はabbaとなり、パスは $1 \rightarrow 1 \rightarrow 2 \rightarrow 3 \rightarrow 4$ 。

さて、上記の例では2つの頂点(パスの先端と終端の頂点)から伸びる辺を同時に考えていた。ただ、これは実装のことを考えると少々面倒なので、簡易化したい。

そこで、この2つの頂点をペアにして、1つの頂点としてみなすことにする。

頂点 $(i, j) :=$ 頂点 $i$ から $j$ までのパス

この表記で先ほどの例を書き換えると、

例1 :
1. c : $(4, 1)$
2. aca : $(3, 1)$
3. bacab : $(2, 2)$
例2 :
1. (空文字列) : $(2, 2)$
2. bb : $(1, 3)$
3. abba : $(1, 4)$

というような頂点の遷移として捉えることができるようになった。

注目したいのは、遷移のスタート地点は

タイプ1 : 頂点 $(i, i) \: (i = 1, 2, \cdots, N)$
タイプ2 : 頂点 $(i, j)$ ただし、 $i, j$ は $C_{i, j} \neq$ -を満たす。

の2種類であるということだ。前者は長さ $0$ の回文、後者は長さ $1$ の回文に当たる。

遷移の様子を図に表すと以下のようになる。

頂点が全部で $N^2$ 個存在することもポイント。

ここで、問題文中におけるクエリを言い換えると、以下のようになる。

$1 \leq i, j \leq N$ を満たす各整数組 $(i, j)$ について、上述した2種類の頂点のいずれかからスタートして、頂点 $(i, j)$ へ到達する経路として最短のものの長さを求めよ。ただし、到達できない場合は $-1$ とせよ。

...最短経路問題に帰着できた。この問題を、上図の新しく作ったグラフ上で多始点 BFS を行うことで解くことにしよう。

答えは $\mathrm{dist}_{i, j}$ という二次元配列に格納することにして、各要素を BFS で最小化していく。各辺のコストは、遷移の過程で回文が2文字ずつ増えていくことから、 $2$ であることに注意しよう。

計算量について。

BFS のqueueには $N^2$ 個の頂点が高々1回挿入・取り出しされ、その各頂点に対して $O(N^2)$ の二重forループが行われるので、全体としては $O(N^4)$ となる。

実装例

#include <bits/stdc++.h>
using namespace std;

#define rep(i, start, end) for (auto i = (start); (i) < (end); (i)++)

constexpr int INF = 1e+9;

using Pair_int = pair<int, int>;

template <typename T>
inline bool chmin(T &a, T b) { return ((a > b) ? (a = b, true) : (false)); }

// ======================================== //

int main()
{
    int N;
    cin >> N;
    vector<string> C(N);
    rep(i, 0, N) cin >> C[i];

    vector<vector<int>> dist(N, vector<int>(N, INF));
    queue<Pair_int> que;
    rep(i, 0, N)
    {
        dist[i][i] = 0;
        que.push({i, i});
    }

    rep(i, 0, N) rep(j, 0, N)
    {
        if (i != j && C[i][j] != '-')
        {
            chmin(dist[i][j], 1);
            que.push({i, j});
        }
    }

    while (!que.empty())
    {
        auto [i, j] = que.front();
        que.pop();
        int d = dist[i][j];

        rep(u, 0, N) rep(v, 0, N)
        {
            if (C[u][i] != '-' && C[j][v] != '-' && C[u][i] == C[j][v])
            {
                if (dist[u][v] != INF)
                    continue;

                dist[u][v] = d + 2;
                que.push({u, v});
            }
        }
    }

    rep(i, 0, N)
    {
        rep(j, 0, N)
        {
            if (dist[i][j] == INF)
                cout << -1 << ' ';
            else
                cout << dist[i][j] << ' ';
        }
        cout << endl;
    }

    return 0;
}