AtCoder ABC 213 F - Common Prefixes (黄色, 500 点)

これを機会に SA-IS を整備した！　今回の記事はあくまで自分が読んでわかる以上を目指さない備忘録として。

• 問題へのリンク

問題概要

2 つの文字列 に対して「先頭何文字が一致しているか」を と表すことにします。

長さ の文字列 が与えられます。 の 文字目以降のみからなる部分文字列を と表すことにします。 のそれぞれに対して

の値を求めてください。

制約

• 
• は英小文字のみからなる文字列

Suffix Array

の suffix (後ろ何文字か) たちについて考える問題自体はよく出題されていて、Suffix Array と呼ばれる配列を作ることで解決できることが多い。

Suffix Array とは、文字列 の suffix たちを辞書順に並べたもののことである。たとえば = "abcababaabc" (11 文字) のとき、suffix を集めると

, c, bc, abc, aabc, baabc, abaabc, babaabc, ababaabc, cababaabc, bcababaabc, abcababaabc

の 12 個となる。これらを辞書順に並べると、

• aabc
• abaabc
• ababaabc
• abc
• abcababaabc
• baabc
• babaabc
• bc
• bcababaabc
• c
• cababaabc

となる。Suffix Array では、次のような配列を管理する。

---

• sa[i] ← の集合の中で辞書順で小さい順に 番目のものは の何文字目から始まるか
• rsa[i] ← 「 の 文字目以降」が Suffix の集合の中で辞書順で何番目か (sa の逆順列)

---

これらはともに、SA-IS と呼ばれるアルゴリズムで、 の計算量で求められる (省略)。上の例では

sa  = {11 7 5 3 8 0 6 4 9 1 10 2}
rsa = {5 9 11 3 7 2 6 1 4 8 10 0}

となる。

高さ配列 LCP

配列 sa を用いていろいろすると、さらに次の高さ配列 lcp が求められる。これが色々と便利なのだ。

---

• lcp[i] ← 文字列 の suffix を辞書順で小さい順に並べたときの、 番目のものと 番目のものについて、先頭が何文字まで一致しているか

---

たとえば今回の = abcababaabc の例でいえば、suffix たちを小さい順に並べると

• aabc
• abaabc
• ababaabc
• abc
• abcababaabc
• baabc
• babaabc
• bc
• bcababaabc
• c
• cababaabc

であり、それぞれの隣接する 2 つの文字列の「先頭が何文字一致しているか」を考えると

lcp = {0 1 3 2 3 0 2 1 2 0 1}

となる。たとえば lcp[2]は、abaabc (辞書順 2 番目) と ababaabc (辞書順 3 番目) の先頭が 3 文字まで一致しているので、lcp[2] = 3 となっている。

さて、上で求めた配列 rsa と、高さ配列 lcp を組み合わせると、次の問に対する見通しがよくなる。

---

文字列 において、 ( は 0-indexed とする) は次のように求められる。

• pi = rsa[i] とする ( が辞書順で何番目かを pi とする)
• pj = rsa[j] とする ( が辞書順で何番目かを pj とする)

として、l = min(pi, pj), r = max(pi, pj) とする。このとき は、配列 lcp において区間 [l, r) の最小値に一致する。

---

たとえば (abaabc) と、 (abcababaabc) について考えてみよう。まず、pi = 2, pj = 5 となる。ここで、辞書順に並べた suffix たちを小さい順に取り出すと

• abaabc (2 番目)
• ababaabc
• abc
• abcababaabc (5 番目)

となる。このとき とは、

• 2 番目と 3 番目の先頭一致度：3 (= lcp[2])
• 3 番目と 4 番目の先頭一致度：2 (= lcp[3])
• 4 番目と 5 番目の先頭一致度：3 (= lcp[4])

の最小値 (最小となるところがボトルネックになる) をとって、2 と求められることがわかる。

もとの問題の言い換え

ここまでくると、元の問題は次のように言い換えられる。

---

サイズ の配列 (高さ配列 lcp のこと) が与えられる。配列 の区間 における最小値を と書くことにする。

各 に対して、

の値を求めよ。

(なお実際の答えは sk = sa[k] として、上記の答えに N - sk を加算した値を res[sk] に格納することに注意)

---

なお、rsa はかならず最後尾が 0 になる。なので、もとの文字列での に関する問題は、rsa による変換をかましたあとの配列 L に関する問題では、 について解いていくことになる。この辺の添字ガチャを合わせるの、苦労した...

言い換え後の問題

このように言い換えたあとも普通に難しい。区間の min をとるのは Sparse Table などを用いて でできるようにしたとしても、愚直に の総和を求めると の計算量となってしまう。

ここではとりあえず、各 に対して

を求めていくことにする。反対側の も同様に求められる。

たとえば として様子を観察してみよう。各 に対して、ベクトル は次のようになる。

• のとき、 なので、
• のとき、 なので、
• のとき、 なので、
• のとき、 なので、
• のとき、 なので、
• のとき、 なので、
• のとき、 なので、
• のとき、 なので、
• のとき、 なので、

つまり、 の要素が新しく増えるとき、過去へ過去へと「その値よりも小さいところ」にぶつかるまで遡って、その値に書き換えてしまうような操作に対応することがわかる。このような操作は stack を用いてシミュレーションすることができる。

よって、全体をとおして計算量は となる。

コード

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

// SA-IS (O(N))
template<class Str> struct SuffixArray {
    // data
    Str str;
    vector<int> sa, rsa, lcp;
    int& operator [] (int i) {
        return sa[i];
    }

    // constructor
    SuffixArray(const Str& str_) : str(str_) {
        build_sa();
    }
    void init(const Str& str_) {
        str = str_;
        build_sa();
    }
    void build_sa() {
        int N = (int)str.size();
        vector<int> s;
        for (int i = 0; i < N; ++i) s.push_back(str[i] + 1);
        s.push_back(0);
        sa = sa_is(s);
        rsa.assign(N + 1, 0);
        for (int i = 0; i <= N; ++i) rsa[sa[i]] = i;
        calc_lcp(s);
    }

    // SA-IS
    // upper: # of characters 
    vector<int> sa_is(vector<int> &s, int upper = 256) {
        int N = (int)s.size();
        if (N == 0) return {};
        else if (N == 1) return {0};
        else if (N == 2) {
            if (s[0] < s[1]) return {0, 1};
            else return {1, 0};
        }

        vector<int> isa(N);
        vector<bool> ls(N, false);
        for (int i = N - 2; i >= 0; --i) {
            ls[i] = (s[i] == s[i + 1]) ? ls[i + 1] : (s[i] < s[i + 1]);
        }
        vector<int> sum_l(upper + 1, 0), sum_s(upper + 1, 0);
        for (int i = 0; i < N; ++i) {
            if (!ls[i]) ++sum_s[s[i]];
            else ++sum_l[s[i] + 1];
        }
        for (int i = 0; i <= upper; ++i) {
            sum_s[i] += sum_l[i];
            if (i < upper) sum_l[i + 1] += sum_s[i];
        }

        auto induce = [&](const vector<int> &lms) -> void {
            fill(isa.begin(), isa.end(), -1);
            vector<int> buf(upper + 1);
            copy(sum_s.begin(), sum_s.end(), buf.begin());
            for (auto d: lms) {
                if (d == N) continue;
                isa[buf[s[d]]++] = d;
            }
            copy(sum_l.begin(), sum_l.end(), buf.begin());
            isa[buf[s[N - 1]]++] = N - 1;
            for (int i = 0; i < N; ++i) {
                int v = isa[i];
                if (v >= 1 && !ls[v - 1]) {
                    isa[buf[s[v - 1]]++] = v - 1;
                }
            }
            copy(sum_l.begin(), sum_l.end(), buf.begin());
            for (int i = N - 1; i >= 0; --i) {
                int v = isa[i];
                if (v >= 1 && ls[v - 1]) {
                    isa[--buf[s[v - 1] + 1]] = v - 1;
                }
            }
        };
            
        vector<int> lms, lms_map(N + 1, -1);
        int M = 0;
        for (int i = 1; i < N; ++i) {
            if (!ls[i - 1] && ls[i]) {
                lms_map[i] = M++;
            }
        }
        lms.reserve(M);
        for (int i = 1; i < N; ++i) {
            if (!ls[i - 1] && ls[i]) {
                lms.push_back(i);
            }
        }
        induce(lms);

        if (M) {
            vector<int> lms2;
            lms2.reserve(isa.size());
            for (auto v: isa) {
                if (lms_map[v] != -1) lms2.push_back(v);
            }
            int rec_upper = 0;
            vector<int> rec_s(M);
            rec_s[lms_map[lms2[0]]] = 0;
            for (int i = 1; i < M; ++i) {
                int l = lms2[i - 1], r = lms2[i];
                int nl = (lms_map[l] + 1 < M) ? lms[lms_map[l] + 1] : N;
                int nr = (lms_map[r] + 1 < M) ? lms[lms_map[r] + 1] : N;
                bool same = true;
                if (nl - l != nr - r) same = false;
                else {
                    while (l < nl) {
                        if (s[l] != s[r]) break;
                        ++l, ++r;
                    }
                    if (l == N || s[l] != s[r]) same = false;
                }
                if (!same) ++rec_upper;
                rec_s[lms_map[lms2[i]]] = rec_upper;
            }
            auto rec_sa = sa_is(rec_s, rec_upper);

            vector<int> sorted_lms(M);
            for (int i = 0; i < M; ++i) {
                sorted_lms[i] = lms[rec_sa[i]];
            }
            induce(sorted_lms);
        }
        return isa;
    }

    // prepair lcp
    vector<int> calc_lcp(const vector<int> &s) {
        int N = (int)s.size();
        lcp.assign(N - 1, 0);
        int h = 0;
        for (int i = 0; i < N - 1; ++i) {
            int pi = sa[rsa[i] - 1];
            if (h > 0) --h;
            for (; pi + h < N && i + h < N; ++h) {
                if (s[pi + h] != s[i + h]) break;
            }
            lcp[rsa[i] - 1] = h;
        }
        return lcp;
    }
};



void solve(int N, const string &S) {
    vector<long long> res(N, 0), left(N + 1, 0), right(N + 1, 0);
    SuffixArray<string> sa(S);
    auto lcp = sa.lcp;

    // (値, index)
    using pll = pair<long long,long long>;
    
    // 左から右へ
    stack<pll> st;
    for (int k = 2; k <= N; ++k) {
        long long val = lcp[k - 1];
        
        // stack から val 以上である限り削除
        while (!st.empty() && st.top().first >= val) st.pop();

        // 答え
        int id = !st.empty() ? st.top().second : 1;
        left[k] = left[id] + val * (k - id);

        // stack に push
        st.push(pll(val, k));
    }

    // 右から左へ
    while (!st.empty()) st.pop();
    for (int k = N - 1; k >= 1; --k) {
        long long val = lcp[k];

        // stack から val 以上である限り削除
        while (!st.empty() && st.top().first >= val) st.pop();

        // 答え
        int id = !st.empty() ? st.top().second : N;
        right[k] = right[id] + val * (id - k);

        // stack に push
        st.push(pll(val, k));
    }

    // 答え
    for (int k = 1; k <= N; ++k) {
        res[sa[k]] = left[k] + right[k] + (N - sa[k]);
    }
    for (auto v: res) cout << v << endl;
}

int main() {
    int N;
    string S;
    while (cin >> N >> S) solve(N, S);
}

AtCoder ABC 213 E - Stronger Takahashi (水色, 500 点)

かの有名な「器物損壊！高橋君」の類題ですね。

drken1215.hatenablog.com

• 問題へのリンク

問題概要

のグリッドがあって、各マスは通路マス (.) か壁マス (#) のいずれかです。

今、左上のマス から右下のマス へと移動したいです。上下左右に移動することができます。通路マスは自由に通ることができますが、壁マスには入れません。

ただし、1 回パンチをすることで、任意の場所の のマスを選んで、その区画内にある壁をすべて破壊することができます。

スタートからゴールまで行けるようにするためには、最低何回パンチを繰り出せばよいか求めてください。

制約

• 

パンチを言い換える

「器物損壊！高橋君」では、「1 回のパンチで 1 個の壁を壊せる」という設定でした。その場合は次のようなグラフを考えればよかったです。各マスを頂点としたグラフ (有向) において

• 任意のマスから通路マスへの辺の重みは 0
• 任意のマスから壁マスへの辺の重みは 1

としたグラフの最短路長を求めればよいということになりました。今回の問題では「1 回のパンチで の範囲の壁を壊せる」という設定になります。その場合は次のように考えましょう。おそらくこの言い換えが難しいと思われます。

---

• 任意のマスから通路マスへ、重み 0 の辺を張る
• 任意のマス (下図の T マス) から、下図の A マスへ、重み 1 の辺を張っておく
  • T マスから 1 回のパンチで行けるマスを A で示しています
  • 上下左右へのマスのみに辺を張るわけではないことに注意

.......
..AAA..
.AAAAA.
.AATAA.
.AAAAA.
..AAA..
.......

---

つまり、今いるマスから 1 回の魔法で行ける範囲が広がったことになります。

一つ注意したいのは、T マスから A マスへの移動のうち、実際には壁がないマスへの移動も含まれる可能性があることです。そのような移動には無駄にコスト 1 をかけることになります。しかし、通路間の移動にはコスト 0 の辺が他で張られていますので、実際に最短路を求めるときにはそっちが使われることになります。よって気にしなくてよいです。

0-1 BFS へ

こうして、辺の重みが 0 または 1 であるようなグラフができましたので、0-1 BFS を用いて解くことができます。このようなグラフにおいても、各頂点から伸びる辺の本数は高々定数ですので、辺数は と評価できます。よって計算量は となります。

0-1 BFS については、次の記事にて。

drken1215.hatenablog.com

コード

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

// 四方向への移動
const vector<int> dx = {1, 0, -1, 0};
const vector<int> dy = {0, 1, 0, -1};

// 無限大
const int INF = 1<<29;

// マスを表す構造体
using pint = pair<int,int>;

int main() {
    // 入力
    int H, W;
    cin >> H >> W;
    vector<string> fi(H);
    for (int i = 0; i < H; ++i) cin >> fi[i];

    // deque
    deque<pint> que;
    vector<vector<int>> dp(H, vector<int>(W, INF));
    que.push_back({0, 0});
    dp[0][0] = 0;

    // 0-1 BFS
    while (!que.empty()) {
        // que の先頭要素を取り出す
        auto [x, y] = que.front();
        que.pop_front();

        // 通路マスへの移動
        for (int dir = 0; dir < 4; ++dir) {
            int nx = x + dx[dir], ny = y + dy[dir];
            if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;
            if (fi[nx][ny] == '#') continue;

            // 移動コストは 0 なので que の front に push
            if (dp[nx][ny] > dp[x][y]) {
                dp[nx][ny] = dp[x][y];
                que.push_front({nx, ny});
            }
        }

        // 魔法を唱えて移動
        for (int nx = x - 2; nx <= x + 2; ++nx) {
            for (int ny = y - 2; ny <= y + 2; ++ny) {
                if (abs(nx - x) + abs(ny - y) == 4) continue;
                if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;

                // 壁だろうが通路だろうがコスト 1 の辺を張る
                // コスト 1 なので que の back に push
                if (dp[nx][ny] > dp[x][y] + 1) {
                    dp[nx][ny] = dp[x][y] + 1;
                    que.push_back({nx, ny});
                }
            }
        }
    }
    cout << dp[H-1][W-1] << endl;
}

AtCoder ABC 213 D - Takahashi Tour (茶色, 400 点)

DFS (深さ優先探索) の動きをシミュレーションする問題。

• 問題へのリンク

問題概要

頂点番号が であるような木が与えられます。

今このグラフにおいて、頂点 1 から出発して、次の動きを繰り返します。

• いまいる頂点に隣接する頂点のうち、まだ訪れたことがない頂点が存在するとき、そのような頂点のうち番号が最も小さいところへ移動する
• そのような頂点が存在しないとき
  • いまいる頂点が頂点 1 であるとき、終了する
  • そうでないとき、いまいる頂点を初めて訪れたときに直前にいた頂点へ移動する

このシミュレーションの過程で訪れる頂点の番号の過程を答えてください。

制約

• 

考えたこと

この問題のシミュレーションは、木において、頂点 1 を根として深さ優先探索を実施することを意味しています。

探索された順に頂点を出力すればよいでしょう。なお、この頂点順のことを特に Euler ツアーとよびます。今後さまざまな、より高度な問題で活躍するものとなっています。

計算量は となります。

コード

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

// グラフ構造体
using Graph = vector<vector<int>>;

// DFS
void rec(const Graph &G, int v, int p = -1) {
    // 行きがけ順の頂点出力
    cout << v+1 << " ";

    for (int ch: G[v]) {
        // 親へは遡らない
        if (ch == p) continue;

        // 再帰的に
        rec(G, ch, v);

        // 戻ってきたらまた出力
        cout << v+1 << " ";
    }
}

int main() {
    // 入力
    int N;
    cin >> N;
    Graph G(N);
    for (int i = 0; i < N-1; ++i) {
        int a, b;
        cin >> a >> b;
        --a, --b;
        G[a].push_back(b);
        G[b].push_back(a);
    }

    // 各頂点の隣接頂点を番号が小さい順に
    for (int v = 0; v < N; ++v) {
        sort(G[v].begin(), G[v].end());
    }

    // DFS
    rec(G, 0);
    cout << endl;
}

AtCoder ABC 213 C - Reorder Cards (茶色, 300 点)

一見いかめしい問題だけど、単に座標圧縮するかどうかだと気づけるかですね。

• 問題へのリンク

問題概要

のグリッドが与えられます。数 はそれぞれマス に書かれています。それ以外の マスには何も書かれていません。

このグリッドに対して、次の操作を可能な限り繰り返し行います。

• 数の書かれたカードを含まない行が存在するとき、その行のカードを全て取り除き、残りのカードを上へ詰める
• 数の書かれたカードを含まない列が存在するとき、その列のカードを全て取り除き、残りのカードを左へ詰める

操作が終了したとき、数が書かれたカードがそれぞれどこにあるか求めてください。なお、答えは操作の仕方に依らず一意に定まることが証明されます。

制約

• 
• 

整理する

問題内容がいかめしいけど、実はやるべきことはとても単純だ。たとえば マスが

(100, 674), (1, 76000), (50, 2), (10000, 16)

であった場合には、答えは

(3, 3), (1, 4), (2, 1), (4, 2)

になる。つまり、

• 座標方向の値：
• 座標方向の値：

のそれぞれ独立に、「それぞれの値が全体の中で何番目に小さい数か」を求めればよいということだ。これはまさに、座標圧縮に他ならない。座標圧縮については次の記事に詳しく書いた。

drken1215.hatenablog.com

今回は結局、2 つの数列について座標圧縮するだけなので、計算量は となる。

コード

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

int main() {
    // 入力
    int H, W, N;
    cin >> H >> W >> N;
    vector<int> X(N), Y(N);
    for (int i = 0; i < N; ++i) cin >> X[i] >> Y[i];

    // 座標圧縮の準備
    auto nX = X, nY = Y;
    sort(nX.begin(), nX.end());
    nX.erase(unique(nX.begin(), nX.end()), nX.end());
    sort(nY.begin(), nY.end());
    nY.erase(unique(nY.begin(), nY.end()), nY.end());

    // 座標圧縮
    for (int i = 0; i < N; ++i) {
        int xres = lower_bound(nX.begin(), nX.end(), X[i]) - nX.begin();
        int yres = lower_bound(nY.begin(), nY.end(), Y[i]) - nY.begin();
        cout << xres+1 << " " << yres+1 << endl;
    }
}

EDPC (Educational DP Contest) W - Intervals

まさに、「DP 配列をセグメント木に載せる」というセグ木上の in-place DP ですね！！！

• 問題へのリンク

問題概要

0 と 1 のみからなる長さ の文字列を 0-1 文字列と呼ぶことにします。

今、文字列中の 個の連続する区間 ( 番目の区間を とします) が与えられます。これらの区間を用いて、0-1 文字列 のスコアは次のように計算されます。

• 各 について
• 文字列 の区間 の内部に 1 が一個でも存在するならば、スコアに を加算する

0-1 文字列のスコアとして考えられる最大値を求めてください。

制約

• 
• 

解法

もし がすべて非負であったならば、 = 111...1 が最適でしょう (その場合のスコアは となります)。

実際には が負値となることもありますので、その場合は区間内部はすべて 0 にしておきたいところです。しかしそうしますと、他の正値なスコアを取りこぼしてしまう可能性もあります。このように「全体のバランス」を考えないといけない場合は、DP で解決できる場合が多々あります。

さてこの問題は、結果的に DP 配列自体をセグメント木 (特に Starry Sky Tree) に載せて in-place に更新するような解法で解けます。in-place DP について特集した次の記事で詳しく解説しました。

qiita.com