Min String Query

動的計画法を利用します。

今、各クエリに$O(N)$で回答することを考えます。

明らかに、$(X,Y)$を通る文字列は

$(1)$ $(X,Y)$に辿り着くまでの文字列の最小化

$(2)$ $(X,Y)$に辿り着いた後の文字列の最小化

の二つに分けられます。$(1),(2)$を独立に求めて結合することで解答を行えないでしょうか。

(STEP1)

$(1)$のクエリに回答するためには$(i,j)$へ辿り着くまでの文字列の最小化を効率的に求めたいです。

以下のような$DP$テーブルを定義しておきます。

$dp(i,j) := (i,j)までの最小の文字列を得るために、その文字列は直前の文字が上から来たか、下から来たか$

このテーブルが生成できれば$(i,j)$へ辿り着くまでの文字列の最小化は以下のように$DP$テーブルに従って復元を行う

ことで$O(N)$で回答できます。

    auto restore_head_string = [&](int i,int j){
        string res; //返される文字列
        for (int x = i,y = j;;){
            if (x < 0 || y < 0){break;}
            res.push_back(a[x][y]); //(x,y)における文字列
            //(上に行くべきか,下に行くべきかで遷移をする)
            if (direction1[x][y] == 1){x--;}
            else{y--;}
        }
        reverse(res.begin(),res.end());
        return res;
    };

(STEP2)

上記の更新を行う上で別の補助$DP$テーブルを定義します。

$priority(i,j) :=$

$X_0 + Y_0 = i + j$を満たす　全ての$(X_0,Y_0)$に対してそこに辿り着くまでの最小の文字列を列挙する。

この時、これらを辞書順にソートした時、$(i,j)$に対してそこに辿り着くまでの最小の文字列は何番目の大きさか(同列の場合同数を割り振る)

この$DP$の更新を行うことを考えましょう。これは$i + j$の値に応じて昇順に更新をしてゆくことでO$(N^2logN)$で更新ができます。

$・i + j = 0$のケースは自明です。比較対象が一つしかないため $priority[0,0] = 0$とします。

$・i + j = k$の時まで更新を終え$i + j = k + 1$の更新を行います。

(i,j)に辿り着くまでの文字列は

$(X) : (i,j - 1)までの文字列+ char[i][j]$

$(Y) : (i - 1,j) までの文字列+ char[i][j]$

のいずれかです。当然$priority$テーブルの定義より、$priority(i,j - 1),priority(i - 1,j)$のうち小さくなるような方を直前に選択するべきです。

これより$DP(i,j)$の更新を行えます。

次に$i + j = k + 1$における$DP$テーブルの更新を考えます。

こうしてそれぞれの$(i,j)$に対して直前の位置$(prev_i,prev_j)$がわかりました。

この時$priority(i,j)$は以下に等しいです。

・$i + j = k + 1$をみたす$(i,j)$の中で$(priority(prev_i,prev_j),char[i][j])$の大きさは何番目か

(同列のものには同数を割りふる)

これは、それぞれの$(i,j)$に対して配列のソートを行えば$O(NlogN)$で更新でき、$DP$全体の更新を通じて$i + j$の値は高々$O(N)$なので全体$O(N^2logN)$で更新できます。

以上より、$(i,j)$に辿り着くまでの文字列の復元を前計算$(O^2logN)$のもと$O(N)$で行うことができました。

(STEP3)

ここまで、

$(1)$ $(X,Y)$に辿り着くまでの文字列の最小化

を行いましたが、

$(2)$ $(X,Y)$に辿り着いた後の文字列の最小化

も同じ要領で$O(N^2logN)$で前計算の下各クエリごと$O(N)$で復元可能です。

(STEP4)

従って、全体で$O(N^2logN)$で前計算の下、各クエリごと$O(N)$で回答することができました。

$Python$などの低速な言語だと実行時間に間に合わせるのが難しいかもしれません。

解答例(C++/233ms)